Prolog - Multiplikation durch Addition

Question

Ich brauche einfache Funktion in SWI-Prolog, die durch Addition multipliziert. Etwas wie m (X, Y, Z), wo zum Beispiel X = 5, Z = 3 < ==> 5 * 3. Y ist das Ergebnis: Y = 5, Y = 10, Y = 15 [Stopp]. Ich dachte über so etwas nach:

m(X,Y,Z):- Z>0, /*when Z reaches 0 you stop */ I=X+X, W=Z-1, m(I,Y,W). 

Aber es immer wieder "falsch" und weiß nicht warum.

Answer 1

Beginnen wir damit, darüber nachzudenken, was das Prädikat beschreiben sollte: Es ist eine Beziehung zwischen drei Zahlen, wobei die dritte das Produkt der ersten beiden ist. Da Sie die Multiplikation beschreiben wollen, indem Sie das zweite Argument auf Null reduzieren, während Sie das erste Argument mehrmals addieren, sprechen wir von natürlichen Zahlen. Ein schön beschreibender Name wäre also nat_nat_prod/3. Als nächstes betrachten Sie die möglichen Fälle:

1. Das zweite Argument kann Null sein. Dann muss das Produkt auch Null sein, da X * 0 = 0 ist. Das ist also der Grundfall.

2. Ansonsten ist das zweite Argument größer als Null. Dann wollen Sie es um eins dekrementieren und das Produkt des ersten Arguments und dieser neuen Zahl berechnen. Da das Prädikat sich dazu verwenden kann, dies zu beschreiben, ist dies ein rekursives Ziel. Anschließend fügen Sie dem durch die Rekursion beschriebenen Zwischenprodukt das erste Argument hinzu.

Dies kann wie so in Prolog geschrieben werden:

nat_nat_prod(_X,0,0).   % case 1) 
nat_nat_prod(X,Y1,P1) :-  % case 2) 
    Y1 > 0, 
    Y0 is Y1-1, 
    nat_nat_prod(X,Y0,P0), 
    P1 is P0+X. 

Lassen Sie uns jetzt einige Abfragen versuchen:

?- nat_nat_prod(5,3,P). 
P = 15 ; 
false. 

?- nat_nat_prod(5,4,P). 
P = 20 ; 
false. 

?- nat_nat_prod(5,0,P). 
P = 0 ; 
false. 

?- nat_nat_prod(1,0,P). 
P = 0 ; 
false. 

?- nat_nat_prod(1,1,P). 
P = 1 ; 
false. 

Wenn jedoch um mit dem Prädikat spielen, werden Sie feststellen, dass Die ersten beiden Argumente müssen instanziiert werden, sonst erhalten Sie einen Fehler:

?- nat_nat_prod(1,Y,3). 
ERROR: >/2: Arguments are not sufficiently instantiated 
?- nat_nat_prod(X,1,3). 
ERROR: is/2: Arguments are not sufficiently instantiated 

Dies geschieht aufgrund der Verwendung von>/2 und is/2. Sie könnten dieses Problem umgehen, indem Sie CLP (FD) verwenden, aber ich denke, das ist nebensächlich. Auf diese Weise Multiplikation der Definition ist offensichtlich sehr ineffizient im Vergleich zu der Standard-Rechenfunktion */2, zB:

?- time(nat_nat_prod(2,1000000,P)). 
% 3,000,000 inferences, 33.695 CPU in 33.708 seconds (100% CPU, 89035 Lips) 
P = 2000000 ; 
% 3 inferences, 0.031 CPU in 0.031 seconds (100% CPU, 97 Lips) 
false. 

?- time(P is 2*1000000). 
% 1 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 82325 Lips) 
P = 2000000. 

Wie bereits von @False in den Kommentaren angedeutet, es häufiger ist es, Menschen zu successor arithmetics zuerst einführen und dann um auf diese Weise Addition/Multiplikation von zwei Zahlen in s (X) -Notation zu definieren. Da Sie die arithmetischen Standardfunktionen nicht mit s (X) -Zahlen verwenden können, stoßen Sie auch nicht auf die zugehörigen Instanziierungsfehler.