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

Question

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

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 Любой вклад приветствуется.

Answer 1

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

Проблема с версией Фибоначчи, которую вы перечислили, заключается в том, что она неэффективна.Каждый вызов 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.

Answer 2

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

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

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

Answer 3

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

edit: вместо разбиения 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

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

Answer 4

У вас почти уже есть это. Просто переписать:

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):- ...

Я не понимаю, как я могу переписать это с использованием накопления

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

Answer 5

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

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