Пролог :: е (х) рекурсии

Question

Я новичок в Прологе и два требования:

1. f(1) = 1

2. f(x) = 5x + x^2 + f(x - 1)

правила:

f(1,1). f(X,Y) :- Y is 5 * X + X * X + f(X-1,Y).

запрос:

f(4,X).

Выход:

ERROR: is/2: Arguments are not sufficiently instantiated

Как я могу добавить значение F (X-1)?

Answer 1

Проблема в том, что вы пытаетесь оценить f (X-1, Y), как если бы это было число, но, конечно, это предикат, который может быть истинным или ложным. Через какое-то мастерить, я нашел это решение:

f(1,1). 
f(X,Y) :- X > 0, Z is X-1, f(Z,N), Y is 5*X + X*X + N. 

Хитрость заключается в том, чтобы позволить ему найти свой путь вниз к f(1,N) первых, без оценки ничего; затем пусть результаты будут возвращены, удовлетворяя Y is 5*X + X*X + N. В Prolog порядок имеет значение для его поиска. Он должен удовлетворять f(Z,N), чтобы иметь значение N для справки Y is 5*X + X*X + N.

Также обратите внимание на условие X > 0, чтобы избежать бесконечной рекурсии.

Answer 2

Это можно легко решить, используя вспомогательные переменные .

Для примера рассмотрим:

 
f(1, 1). 
f(X, Y) :- 
     Y #= 5*X + X^2 + T1, 
     T2 #= X - 1, 
     f(T2, T1). 

Это прямолинейный перевод правил, которые вы даете, используя вспомогательные переменные T1 и T2, которые стоят за частичные выражения F (X-1) и X-1, соответственно. Поскольку @BallpointBen правильно отмечает, недостаточно использовать сами термины, поскольку эти термины отличаются от их арифметики оценка. В частности, -(2,1) является не целое число   1, но 2 - 1 #= 1 удержание!

В зависимости от системы Prolog, вы можете определяется в настоящее время по-прежнему импортировать библиотеку использовать предикат (#=)/2, выражающий равенство из целочисленных expressesions.

Ваш пример запроса уже сейчас дает решение:

 
?- f(4, X). 
X = 75 . 

Обратите внимание, что предикат делает не прекращать универсально в этом случае:

 
?- f(4, X), false. 
nontermination 

Мы можем легко сделать так, с дополнительным ограничение:

 
f(1, 1). 
f(X, Y) :- 
     X #> 1, 
     Y #= 5*X + X^2 + T1, 
     T2 #= X - 1, 
     f(T2, T1). 

Нет ж мы имеем:

 
?- f(4, X). 
X = 75 ; 
false. 

Обратите внимание, что мы можем использовать это в качестве истинного отношения, а также в наиболее общем случае:

 
?- f(X, Y). 
X = Y, Y = 1 ; 
X = 2, 
Y = 15 ; 
X = 3, 
Y = 39 ; 
X = 4, 
Y = 75 ; 
etc. 

версии основаны на более низком уровне арифметики обычно только крышка очень ограниченное подмножество экземпляров таких запросов. Поэтому я рекомендую вам использовать (#=)/2вместо от (is)/2. Специально для новичков, использование (is)/2 слишком сложно понять. Возьмите много связанных вопросов, поданных под номером   instantiation-error в качестве доказательств, и см. clpfd для декларативных решений.