Prolog: Multiplication récursive de 2 nombres

Question

Je ne comprends pas pourquoi cette définition récursive d'une multiplication fonctionne.
Je reçois la partie add, mais comment est la valeur de "A" dans ce contexte. Le code est le suivant:

add(0,X,X). 
add(s(X),Y,Z):-add(X,s(Y),Z). 

mult(0,X,0). 
mult(s(X),Y,Z):-mult(X,Y,A), add(Y,A,Z). 

Answer 1

Pour comprendre les prédicats, essayez de « lire » ce qu'ils disent.

Lire la définition add/3 premier ...

add(0,X,X). 

Ajout 0 à X résultats dans X.

add(s(X),Y,Z):-add(X,s(Y),Z). 

Ajout s(X) (le successeur de X) à Y résultats dans Zsi ajoutant X à s(Y) (le successeur de Y) se traduit par Z.

Si nous considérons successeur que l'ajout de 1, alors cela veut dire (X + 1) + Y résultats dans Z si X + (Y + 1) résultats en Z. C'est logique, mais ça ne semble aller nulle part. Cependant, nous noterons que cette logique est étroitement liée au cas de base de add(0,X,X) puisque le cas récursif réduira le premier argument en supprimant une seule succession à chaque itération jusqu'à ce que le premier argument devienne 0.

Maintenant, nous allons essayer mult/3 ...

mult(0,X,0). 

Multipliant 0 par X résultats dans 0

Cela semble être évident.

mult(s(X),Y,Z):-mult(X,Y,A), add(Y,A,Z). 

multipliant le successeur de XY par les résultats dans Zsi multipliant par XY résultats dans A, et ajoutant Y à A résultats dans Z.

Si vous pensez à successeur en ajoutant 1, cela dit que (X+1)*Y est Z si X*Y est A et A+Y est Z. Cela aurait du sens puisque (X+1)*Y est (X*Y)+Y qui serait A+Y.

Answer 2

Dans ce contexte, A est la valeur de (X-1) * Y. Vous trouvez cette valeur récursivement avec la règle mult, puis ajoutez-la à Y dans la règle add pour obtenir votre résultat final. Il est en train d'écrire la multiplication comme X * Y = (X - 1) * Y + Y

vraiment ce qui finit par se produire est-il appelle addX fois, et chacun de ces moments, il ajoute Y au résultat final (à partir de zéro). Ceci exploite la multiplication comme addition répétée. Voici une trace à la main:

1. mult(3, 2, Z)
   appel initial

2. mult(2, 2, A_1), add(2, A_1, Z)
   Soustraire 1 FRAM X

3. mult(1, 2, A_2), add(2, A_2, A_1)
   Encore une fois.

4. mult(0, 2, A_3), add(2, A_3, A_2)
   Une dernière fois

5. mult(0, 2, A_3)
   Une seule possibilité, zéro ne peut pas correspondre s(x). A_3 est réglé sur 0.

6. mult(0, 2, 0), add(2, 0, A_2)
   étape 4, mais avec A_3 substitué. Nous savons maintenant que A_2 doit être 2.

7. mult(1, 2, 2), add(2, 2, A_1)
   Etape 3, mais avec A_2 substitué. Nous savons maintenant A_1 doit être 4.

8. mult(2, 2, 4), add(2, 4, Z)
   Étape 2, mais avec A_1 substitué. Nous savons maintenant Z doit être 6, le résultat final.

Pour les étapes 2 à 4, vous comptez vers le bas pour trouver le nombre de fois où vous devez répéter l'opération d'addition. L'étape 5 est le cas de base, en commençant le résultat final à zéro. Aux étapes 6 à 8, vous effectuez l'ajout. Cela donne le résultat de Z = 6 = 2 + 2 + 2