Последовательность номеров Fibonnaci - Prolog

Question

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

Например вход:

?- fib_sequence(2,5,Output). 

дает выход:

?- Output = [1,1,2,3] 

Я с трудом, однако, найти хорошую отправную точку. Это то, что я до сих пор:

fib(0, 0). 
fib(1, 1). 
fib(N, F) :- X is N - 1, Y is N - 2, fib(X, A), fib(Y, B), F is A + B. 

fib_sequence(A,B,R) :- fib(A,Y) , fib(B,Z). 

Я знаю, что я должен присвоить значение R, но я не уверен, как назначить несколько значений. Любая помощь приветствуется.

Answer 1

Обратите внимание, что ваш fib_sequence не может быть сделано в одном предложении предиката: вам нужно по крайней мере два, чтобы держать вещи рекурсивными - один, чтобы произвести пустой список, когда A больше B (т.е. мы исчерпали диапазон от А до B), а другой - для добавления X из fib(A,X) в список, который вы строите, увеличивайте A на 1 и вызывайте fib_sequence рекурсивно для получения остальной последовательности.

Первый пункт предиката будет выглядеть следующим образом:

fib_sequence(A,B,[]) :- A > B. 

Второго условие предикат является немного сложнее:

fib_sequence(A,B,[H|T]) :- 
    A =< B     /* Make sure A is less than or equal to B */ 
, fib(A, H)    /* Produce the head value from fib(A,...) */ 
, AA is A + 1    /* Produce A+1 */ 
, fib_sequence(AA, B, T). /* Produce the rest of the list */ 

Answer 2

Пролога имеет некоторую вспомогательную встроенную команду для обработки числовых последовательностей, то в качестве альтернативы to dasblinkenlight ', вот идиоматический запрос:

fib_sequence(First, Last, Seq) :- 
    findall(F, (between(First,Last,N), fib(N,F)), Seq). 

примечание t шляпа не будет работать из-за коробки с вашим фидом/2, потому что есть ошибка: я добавил условие, которое избегает бесконечного цикла, который вы испытаете при попытке backtrack на решениях fib/2:

fib(N, F) :- N > 1, % added sanity check 
    X is N - 1, Y is N - 2, fib(X, A), fib(Y, B), F is A + B. 

Answer 3

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

fib(N, F) :- 
    fib(N, F, _). 
fib(N, F, F1) :- 
    N > 2, 
    N1 is N-1, 
    fib(N1, F1, F0), 
    F is F0 + F1. 
fib(1, 1, 0). 
fib(2, 1, 1). 

Для получения последовательности, я выбрал алгоритм с расчетом Фибоначчи встроенной, так что это Безразлично Не нужно звонить fib O (n^2) раза. Это, однако, необходимо обратить список, когда полный:

fib_sequence(A, B, FS) :- 
    fib_seq_(A, B, FSR), 
    reverse(FSR, FS). 

fib_sequence_(A, B, []) :- 
    A > B. 
fib_sequence_(A, B, [F]) :- 
    A =:= B, 
    fib(A, F, _). 
fib_sequence_(A, B, [F1,F0]) :- 
    1 is B - A, 
    fib(B, F1, F0). 
fib_sequence_(A, B, [F2,F1,F0|FT]) :- 
    B > A, 
    B1 is B - 1, 
    fib_sequence_(A, B1, [F1,F0|FT]), 
    F2 is F1 + F0. 

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

fib_sequence_dl(A, B, F) :- 
    fib_sequence_dl_(A, B, F, [_,_|[]]). 

fib_sequence_dl_(A, B, [], _) :- 
    A > B, !. 
fib_sequence_dl_(A, B, [F], _) :- 
    A =:= B, 
    fib(A, F, _), !. 
fib_sequence_dl_(A, B, [F0,F1|T], [F0,F1|T]) :- 
    1 is B - A, 
    fib(B, F1, F0), !. 
fib_sequence_dl_(A, B, F, [F1,F2|T]) :- 
    A < B, 
    B1 is B - 1, 
    fib_sequence_dl_(A, B1, F, [F0,F1|[F2|T]]), 
    F2 is F0 + F1.