Prolog :: f (x) Rekursion

Question

Ich bin ein Anfänger in Prolog und zwei Anforderungen:

1. f(1) = 1

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

Regeln:

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

query:

f(4,X).

Ausgang:

ERROR: is/2: Arguments are not sufficiently instantiated

Wie kann ich Wert von f (X-1)?

Answer 1

Das Problem ist, dass Sie versuchen, f (X-1, Y) zu bewerten, als ob es eine Zahl wäre, aber natürlich ist es ein Prädikat, das wahr oder falsch sein kann. Nach einigem Tüfteln fand ich diese Lösung:

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

Der Trick ist es seinen Weg finden zu lassen, bis f(1,N) ersten, ohne irgendetwas zu bewerten; dann lassen Sie die Ergebnisse wieder durch die Erfüllung Y is 5*X + X*X + N blasen. In Prolog, ordnen Sie Angelegenheiten für seine Suche an. Er muss f(Z,N) erfüllen, um einen Wert von N für die Anweisung Y is 5*X + X*X + N zu haben.

Beachten Sie auch die Bedingung X > 0, um eine unendliche Rekursion zu vermeiden.

Answer 2

Dies kann einfach mit Hilfsvariablen gelöst werden.

Betrachten wir zum Beispiel:

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

Dies ist eine straight-forward Übersetzung der Regeln, die Sie geben, mit Hilfsvariablen T1 und T2, die für die Teilausdrücke f stehen (X-1) und X-1 bzw.. Wie @BallpointBen richtig feststellt, reicht es nicht aus, die Terme selbst zu verwenden, da sich diese Terme von ihrer arithmetischen Auswertung unterscheiden. Insbesondere -(2,1) ist nicht die ganze Zahl   1, aber 2 - 1 #= 1tut halten!

Je nach Prolog-System, können Sie zur Zeit noch ned, um eine Bibliothek importieren(#=)/2 das Prädikat zu verwenden, dieGleichheit von integer expressesions zum Ausdruck bringt.

Ihr Beispiel Abfrage jetzt ergibt bereits eine Lösung:

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

Beachten Sie, dass das Prädikat nicht nicht universell in diesem Fall beenden:

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

Wir können es leicht machen, so mit einem zusätzlichen Bedingung:

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

Nr w haben wir:

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

beachten Sie, dass wir dies als eine echte Beziehung, auch im allgemeinsten Fall verwenden können: Arithmetik

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

Versionen basierend auf niedrigerer Ebene typischerweise nur Abdeckung eine sehr begrenzte Teilmenge von Instanzen solcher Abfragen. Ich empfehle daher, dass Sie (#=)/2statt(is)/2 verwenden. Gerade für Anfänger ist die Verwendung von (is)/2 zu schwer zu verstehen. Nehmen Sie die vielen verwandten Fragen unter   instantiation-error als Beweis, und siehe clpfd für deklarative Lösungen.