Пролог; попытаться сделать фибоначчи более эффективным?

Это логическое программирование действительно заставляет меня танцевать на коленях с моими императивными навыками программирования. Это домашнее задание, поэтому, пожалуйста, не присылайте мне ответ. Вот что у меня есть:

fibo(N,1) :-
   N < 2,
   !. 
fibo(N,R) :-
   N1 is N-1,
   N2 is N-2,
   fibo(N1,R1),
   fibo(N2,R2),
   R is R1+R2.

Я предполагаю создать другую функцию, которая выглядит так: fib(N,Value,LastValue). N - это n-е число, а значение - это возвращаемое значение. Я не понимаю, как это можно переписать с помощью накопления. И поскольку он считает в обратном порядке, я не понимаю, как он может «узнать» последнее значение, прежде чем что-либо вычислит. : s Любой вклад приветствуется.


fibonacci prolog clpfd
person Algific    schedule 23.11.2010    source источник
comment
См. Ответ Bobby Tables. Не уверен, что это вас сбивает, но помните, что в Прологе входные и выходные аргументы для предиката могут быть в любом порядке, и в некоторых случаях это всего лишь различия в вашей голове или способе использования предиката.   -  person aschepler    schedule 23.11.2010

Ответы (5)


arrow_upward
5
arrow_downward

Я мог бы опубликовать здесь решение, но, поскольку это домашнее задание, оно будет контрпродуктивным. Вместо этого вот зацепка:

Проблема с версией Фибоначчи, которую вы указали, в том, что она неэффективна. Каждый вызов fibo/2 вызывает еще два вызова, но некоторые из этих вызовов вычисляют значения одних и тех же чисел Фибоначчи. Например, в псевдокоде:

(a) fibo(4) -> fibo(3), fibo(2)
(b) fibo(3) -> fibo(2), fibo(1)
(c) fibo(2) -> fibo(1), fibo(0) % called from (a)
(d) fibo(2) -> fibo(1), fibo(0) % called from (b), redundant

Чтобы преодолеть этот недостаток, вас попросили перефразировать Фибоначчи с точки зрения возврата не только последнего значения, но и двух последних значений, чтобы каждый вызов fib/3 вызывал только один рекурсивный вызов (следовательно, вычислять ряд Фибоначчи за линейное время) . Вам нужно будет изменить базовые случаи на:

fib(1,1,0).
fib(2,1,1).

Я оставлю вам рекурсивный случай.

Для нетерпеливых

Вот и рекурсивный случай:

fib(N, Val, Last) :-
  N > 2,
  N1 is N - 1,
  fib(N1, Last, Last1), % single call with two output arguments, 
                        % instead of two calls with one output argument
  Val is Last + Last1.
person Little Bobby Tables    schedule 23.11.2010
comment
Согласитесь со всем здесь, за исключением того, что я думаю, что вам действительно нужен только один базовый факт, когда все сделано таким образом. - person aschepler; 23.11.2010
comment
Его очень скоро. Могу ли я найти решение? Если я не отдам это, я даже не смогу сдать экзамен. Я избавлю вас от отговорок, но один совет; В Uni не составляйте свое расписание, потому что все рушится. - person Algific; 24.11.2010
comment
Интересно, что я не думал, что у самого вызова есть 2 предыдущих значения. Я думал с точки зрения запоминания. - person Paul Nathan; 24.11.2010

arrow_upward
2
arrow_downward

См. Соответствующее обсуждение:

Обобщение последовательности Фибоначчи с помощью SICStus Prolog

и рассмотрим очень хорошее решение ony с использованием ограничений конечной области оттуда.

person mat    schedule 23.11.2010

arrow_upward
1
arrow_downward

Возможно, использование хвостовой рекурсии - хороший вариант

изменить: вместо того, чтобы разбивать fib (6) на fib (5) + fib (4), вы можете попробовать что-то вроде fib (6) = fib (6,0,0), первым параметром является количество шагов, когда оно достигает 0 вы останавливаетесь, второй параметр - это последнее вычисленное вами значение, а третий параметр - это значение для вычисления, которое равно сумме текущих второго и третьего параметров (за исключением первого шага, на котором 0 + 0 будет 1 )

Итак, чтобы вычислить, вы устанавливаете второй параметр при каждом вызове и накапливаете в третьем, поэтому fib (6,0,0) => fib (5,0,1) => fib (4,1,1) => fib (3 , 1,2) => fib (2,2,3) => fib (1,3,5) => fib (0,5,8), тогда вы вернете 8

В этом методе вам фактически не нужно сохранять в стеке возвращаемый адрес, избегая переполнения стека.

person rpfaraco    schedule 23.11.2010

arrow_upward
0
arrow_downward

Помните, что есть еще один способ вычислить последовательность Фибоначчи: начать с базового случая и двигаться вверх.

Прямо сейчас, чтобы вычислить fib(n), вы складываете fib(n-1) и fib(n-2). Вместо этого переверните это и вычислите fib(0) и fib(1) на основе определения последовательности Фибоначчи и начните с этого.

person Paul    schedule 23.11.2010

arrow_upward
-1
arrow_downward

Он у вас почти уже есть. Просто перепишите:

fibo(N, Value) :-
N1 is N-1, N2 is N-2,
 fibo(N1, LastValue),fibo(N2, SecondToLastValue),
 Value is LastValue + SecondToLastValue.

с точки зрения

fibo2(N, Value, LastValue):- ...

Я не понимаю, как это переписать с помощью накопления

Только не надо, это не нужно (хотя это возможно).

person jpalecek    schedule 23.11.2010
comment
Помните, что это домашнее задание. Хотя у него не этого делать, вопрос определенно сформулирован таким образом, что маркер ищет другой метод вычисления последовательности Фибоначчи, как указано в моем ответе. - person Paul; 23.11.2010
comment
@Paul: В вопросе OP конкретно заявляет, что он должен написать функцию fib(N,Value,LastValue). Это не означает, что он хочет сделать что-то радикальное. В конце концов, то, что я описал в своем посте, является линейным и действует точно так же, как и другой метод. - person jpalecek; 23.11.2010
comment
Смысл использования накопления состоит в том, чтобы сделать его более эффективным с точки зрения памяти, когда n-е число fib становится большим, теперь я получаю глобальное переполнение стека для чисел, которые на самом деле не такие большие. - person Algific; 23.11.2010