Пролог: уменьшение переменной в аргументе

Я новичок в Прологе, и мне поручили использовать предикат Фибонначи fib( N, F), где N — число в последовательности, а F — значение. То, что я придумал, не работает, но решение, которое я нашел, кажется мне идентичным... Я не могу понять разницу.

Моя версия:

/* MY VERSION, DOES NOT WORK */
fib( 0, 0).
fib( 1, 1).
fib(N,F) :-
    N > 1,
    fib(N-1,F1),
    fib(N-2,F2),
    plus(F1,F2,F).

Рабочая версия:

/* FOUND SOLUTION, DOES WORK */
fib( 0, 0).
fib( 1, 1).
fib(N,F) :-
    N > 1,
    N1 is N-1,
    N2 is N-2,
    fib(N1,F1),
    fib(N2,F2),
    plus(F1,F2,F).

Очевидно, проблема связана с тем, что я использую «N-1» и «N-2» в качестве аргументов, а не сначала присваиваю эти значения новым переменным. Но я этого не понимаю... потому что в других рекурсивных кодах Пролога я успешно сделал именно это (уменьшил переменную прямо в слоте аргумента). Имеет ли это смысл?

Спасибо!

Ниже приведен пример, когда «Н-1» действительно работал.

line( N, _, _) :-
    N =:= 0.

line( N, M, Char) :-
    N > 0,
    N mod M =\= 1,
    write( Char), write( ' '),
    line( N-1, M, Char).

line( N, M, Char) :-
    N > 0,
    N mod M =:= 1,
    write( Char), write( '\n'),
    line( N-1, M, Char).

square( N, Char) :-
    N > 0,
    line( N*N, N, Char).

Новая версия fib/2, которая тоже работает!

/* NEW VERSION, CHANGED TRIVIAL CASES TO EVALUATE N */
fib( N, 0) :-
    N =:= 0.

fib( N, 1).
    N =:= 1.

fib(N,F) :-
    N > 1,
    fib(N-1,F1),
    fib(N-2,F2),
    plus(F1,F2,F).

fibonacci prolog
person The111    schedule 25.08.2011    source источник
comment
Мне было бы любопытно посмотреть, как вы успешно уменьшили переменную прямо в аргументе — я не думал, что это возможно.   -  person Owen    schedule 26.08.2011
comment
Я не знал этого раньше, но, по-видимому, > похож на is в том, что он оценивает арифметику (я хочу разместить здесь ссылку, но ТАК интерпретирует скобки - добавит к моему ответу). Очень аккуратный.   -  person Owen    schedule 26.08.2011
comment
Крутая штука (спасибо за ссылку), но не уверен, что трюк с оценкой ‹ или › объясняет, почему мой предикат line/3 успешно работает с аргументом N-1. Странный.   -  person The111    schedule 26.08.2011

Ответы (2)


arrow_upward
5
arrow_downward

В прологе

1 - 2

На самом деле не выполняет никакой арифметики (я знаю, верно?), Он создает структуру:

-(1, 2)

И is — это предикат, который оценивает эту структуру:

is(X, -(1, 2))

Объединит X с -1.

Также очевидно < и > (и им подобные) похожи на is тем, что оценивают выражения.

Итак, это означает, что разница между вашим предикатом fib и вашим предикатом line заключается в том, что

fib(0, 0).

использует унификацию, т. е. проверяет, равны ли сами термины:

foo(0).

?- foo(1 - 1).
false

В то время как тест типа =:= проверяет числовое равенство:

foo(X) :- X =:= 0.

?- foo(1 - 1).
yes
person Owen    schedule 25.08.2011
comment
Это имеет смысл, но почему N-1 работает в моем квадратном предикате ниже? Гах, кажется, я не могу добавить код в этот ответ, поэтому я отредактировал его в своем OP. - person The111; 26.08.2011
comment
Хорошо, я думаю, я понял. Так что это действительно связано с ›... в частности, строки N›0 и N=:=0 в моих трехстрочных предикатах являются причиной оценки N-1. Спасибо, что объяснили... Сам бы никогда не догадался. - person The111; 26.08.2011
comment
Ладно... подожди минутку. Теперь я снова путаюсь. Моя версия предиката fib имеет N ›= 0 в качестве первой строки. Так не должно ли это привести к тому, что N-1 и N-2 будут оцениваться так же, как в очереди??? И кстати, N ›= 0 было чрезмерным… на самом деле нужно N › 1. Обновление OP. Ааааааааааааааааааааааааааааааааааааааааа... отредактируй... неважно. Я думаю, что это тривиальные случаи (0,0) и (0,1), которые вызывают проблему... как вы на самом деле указали. :-) - person The111; 26.08.2011
comment
@Johnson Да, это приведет к его оценке. Но он также использует fib(0, 0)., которого не будет. Вы можете использовать fib(X, 0) :- X =:= 0. - person Owen; 26.08.2011
comment
Ха! Я сам придумал такое же решение несколько минут назад, проверьте редактирование OP. :-) Еще раз спасибо, теперь я точно это понимаю. Отметив свой как решение. - person The111; 26.08.2011

arrow_upward
0
arrow_downward

Я бы, вероятно, написал предикат примерно так.

fib/2 — это внешний «общедоступный» интерфейс. N — позиция в последовательности (относительно нуля). F объединяется со значением последовательности Фибоначчи в этой позиции.

fibonacci/5 — это внутреннее «ядро», которое выполняет всю работу.

  • 1-й аргумент - счетчик
  • 2-й аргумент - предел
  • 3-й/4-й аргументы — это скользящий кадр, необходимый для вычисления следующего элемента в последовательности. Следует отметить, что для последовательности Фибоначчи не требуется начинать с {1, 1}. Подойдут любые два целых числа.
  • 5-й аргумент объединяется с желаемым результатом.

Каждое предложение в ядре работает следующим образом:

  • Если N равно 0, F объединяется с «1».
  • Если N равно 1, F объединяется с «1».
  • Если предел достигнут, мы закончили. Объедините F с суммой двух предыдущих элементов в последовательности.
  • Если счетчик меньше предела, вычислите следующий элемент в последовательности и рекурсивно вытащите самое старое значение из скользящего окна.

Вот код:

fib( N , F ) :-
  N >= 0 ,
  fibonnaci( 0 , N , 1 , 1 , F ).

fibonacci( 0     , 0     , F , _ , F ).
fibonacci( 1     , 1     , _ , F , F ).
fibonacci( Limit , Limit , X , Y , F ) :-
  F is X + Y
  .
fibonacci( Current , Limit , X , Y , F ) :-
  Current < Limit ,
  Next is Current + 1 ,
  Z is X + Y ,
  fibonacci( Next , Limit , Y , Z , F )
  .
person Nicholas Carey    schedule 26.08.2011