Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Prolog > Вычмсление чисел Фибоначчи

Автор: Smasher 22.3.2009, 18:02

Вот так вот я вычисляю числа Фибоначчи, но мне надо их вычислять при помощи рекурсии в конце, чтобы это сделать надо раскоментить 2 строчку в clauses, но если это сделать то прога перестаёт работать и как бы пропускает вычисление, подскажите пожалуйста как это это сделать или предложите другой вариант вычислений чисел Фибоначчи, но только с рекурсией в конце

class predicates
fib:(integer,integer) nondeterm anyflow.
fib:() nondeterm anyflow.

clauses
fib():-fib(1,1).
%fib(M,N):-!.
fib(M,N):-M1=N,N1=N+M,stdIO::write(M," "),fib(M1,N1).

Заранее благодарен

Автор: t_gran 24.3.2009, 08:36

Цитата

прога перестаёт работать и как бы пропускает вычисление

Правильно, ведь prolog твои значения подставляет в fib(M,N):-!. и сразу выходит.

Братко предлагает следующее:

Код


фиб(1, 1).    % 1-е число Фибоначчи

фиб(2, 1).    % 2-е число Фибоначчи

фиб(N, F) :-  % N-е число Фиб., N > 2
   N > 2,
   N1 is N-1, фиб(N1, F1),
   N2 is N-2, фиб(N2, F2),
   F is F1+F2.                        % N-e число есть сумма двух предыдущих

А вот, к примеру, моя модификация

Код


fib(0,1,1).

fib(D,M,N):-
   D > 0,
   D1 is D-1,
   fib(D1,M1,N1),
   N is M1,
   M is M1 + N1.

где, D-порядковый номер, а M и N-соседние числа. Тест:

Код


?- fib(10,N,M).
N = 144,
M = 89 .

Автор: Smasher 24.3.2009, 17:41

t_gran,
да но мне надо с хвостовой рекурсией

Автор: t_gran 27.3.2009, 03:31

Пардон!

Код


myfib(D,P,D,P,_) :- !.

myfib(D,P,I,N,M) :-
   I1 is I+1,
   N1 is N+M,
   M1 is N,
   myfib(D,P,I1,N1,M1).

fib(D,P) :-
   myfib(D,P,1,1,1).

Вот хвостовая. smile

Тест думаю не надо писать.

Автор: Винитарх 16.2.2010, 12:31

Дааа. Как всё здесь запущено!
Вот прога Фибоначчи на Visual Prolog 7.2 согласно математическому определению:

Код

fib(0)=1:-!.
fib(1)=1:-!.
fib(N) = fib(N-1)+fib(N-2).

А вот эффективная прога на том же Visual Prolog 7.2 (третий аргумент - индекс искомого члена, способ вызова 46-го члена: N=fib(1,1,46) ):

Код

fib(X,Y,3)=X+Y:-!.
fib(X,Y,N) = fib(Y,X+Y,N-1).

Приходите к нам на progz.ru. Мы Вам покажем современный П Р О Л О Г!!!