Пролог: Уменьшение переменной в аргументе - PullRequest
Новая
       23

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

2 голосов
/ 26 августа 2011

Я новичок в Прологе, и мне было поручено предикат Фибоначчи 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» в качестве аргументов, вместо того, чтобы сначала присвоить эти значения новым переменным. Но я не понимаю ... потому что в других рекурсивных кодах Пролога я успешно сделал именно это (уменьшил значение переменной прямо в слоте аргумента). Имеет ли это смысл?

Спасибо!

Ниже приведен пример, где "N-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).

Ответы [ 2 ]

5 голосов
/ 26 августа 2011

В прологе 

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
0 голосов
/ 26 августа 2011

Вероятно, я бы написал предикат примерно так:

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

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

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

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

  • Если 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 )
  .
...