Блог

Главная - Вопросы по программированию - Вычислить серию Фибоначчи в Prolog, хвостовая рекурсия

Вычислить серию Фибоначчи в Prolog, хвостовая рекурсия

#prolog #fibonacci #tail-recursion

#пролог #фибоначчи #хвостовая рекурсия

Вопрос:

Я хочу вычислить ряд Фибоначчи в Prolog, в режиме рекурсивного хвоста.

 fibonacci(0,0).
fibonacci(1,1).
fibonacci(N,Result) :-
   fibonacci(N,1,0).

fibonacci(N,Result,Count) :-
   Count < N,
   !,
   Count1 is Count   1,
   Result1 is  Result   Count,
   fibonacci(N,Result1,Count1).  
fibonacci(N,Count,Count).

но результат неверен, в чем проблема?

Ответ №1:

В строке Result1 is Result Count вы добавляете только подсчет переменной Result и добавляете 0,1,2, … но в фибоначчи вам нужно добавить два предыдущих, например 0,1,(1 0=1),(1 1=2),…. Я предлагаю такую реализацию:

 fib(0, 0).
fib(1, 1).
fib(N,Result):-fibonacci(N,0,1,Result).

fibonacci(0,N,_,N).
fibonacci(N, Prev1,Prev2,Result):-
   N>0,
   New_Prev2 is Prev1 Prev2,
   N1 is N-1,
   fibonacci(N1,Prev2,New_Prev2,Result).

Комментарии:

1. Это хвостовая рекурсия?

2. Отредактировал ответ с помощью хвостовой рекурсивной версии, еще раз спасибо!

3. Потрясающая работа! 🙂

4. Спасибо за ободряющие слова!!

5. какой пример вы пробовали?? Кроме того, каков был ваш результат и желаемый результат??

Ответ №2:

Вот хвостовое рекурсивное решение.Вам нужно использовать накопитель. По сути, вы вычисляете Фибоначчи в обратном направлении. Когда вы дойдете до 1, вы остановитесь.

фибоначчи (0,0).
фибоначчи (N, результат):-
N> 0,
fib(N, 0,1, результат).

fib(1,_,Accum, Accum).
fib(N, значение, накопление, результат): —
N1 равно N-1,
накопление нового равно значению накопление,
fib (N1, накопление, накопление нового, результат).

Метки: ,