Prolog

TD n°2

Préliminaires

?- M=1+1, N is 1+1.
M = 1+1
N = 2 ;
No
?- N is 1+1, M is N+3, P = N+M.
N = 2
M = 5
P = 2+5 ;
No

?- write('bonjour'),nl,write('toi').
bonjour
toi
Yes
?- X is 2, write(X).
2
X = 2 ;
No

1. Comment exprimer qu'on veut calculer la somme de deux nombres ?

   somme(X,Y,S) :- S is X+Y.

2. Comment exprimer qu'on veut connaître le plus grand parmi 2 nombres ? parmi 3 ?

   max2(X,Y,X) :- X>=Y.
   max2(X,Y,Y) :- X<Y.
   
   max3(X,Y,Z,M) :- max2(X,Y,MM),max2(MM,Z,M).

   Que produit max2(X,1,3) ? Pourquoi ? Même question avec max2(1,X,3).

Exercices sur la récursivité

1. Afficher N fois 'bonjour'. (Ou : ecrit(N) est vrai si le message 'bonjour' est écrit N fois.)

   ecrit(0).
   ecrit(N) :- N>0, write('bonjour'), nl, N1 is N-1, ecrit(N1).

2. Afficher les nombres de 1 à N.

   /* de N à 1 */
   decroissant(0).
   decroissant(N) :- N>0, write(N), nl, N1 is N-1, decroissant(N1).
   /* de 1 à N */
   croissant(0).
   croissant(N) :- N>0, N1 is N-1, croissant(N1), write(N), nl.
   

   On pourrait penser que la virgule, qui est la traduction en prolog du ET logique, devrait être commutative. Or il est évident dans cet exemple que ce n'est pas le cas (sinon les deux prédicats seraient identiques).
   Ceci est dû à ce qu'on appelle des effets de bord : si on reste dans le domaine de l'évaluation d'expressions logiques, c'est bien commutatif, mais l'ordre d'évaluation sera différent, et comme ici on produit des affichages en cours d'évaluation, le résultat obtenu est différent.

Exercices sur la récursivité, suite

1. Dire si un nombre est pair.

   pair(0).
   pair(X) :- X>0, X2 is X-2, pair(X2).

2. Trouver la somme des N premiers entiers. (Ou : som(N,X) est vrai si X est la somme des entiers de 1 à N.)

   som(0,0).
   som(N,X) :- N>0, N1 is N-1, som(N1,X1), X is N+X1.

3. Trouver la factorielle d'un nombre. (Ou : fact(N,X) est vrai si X vaut N!.)

   fact(0,1).
   fact(N,X) :- N>0, N1 is N-1, fact(N1,X1), X is N*X1.

4. fibo(N,X) est vrai si X est la valeur de la suite de Fibonacci au rang N.

   fibo(1,1).
   fibo(2,1).
   fibo(N,X) :- N>2, U is N-1, V is N-2, fibo(U,U1), fibo(V,V1),
            X is U1+V1.

5. coef(N,P,C) a un sens si N>P et est vrai si C vaut N!/((N-P)!P!) ; utiliser la relation de Pascal.
   On demande de calculer les C(n,p), coefficients du binôme :

   (a+b)ⁿ = C(n,0)aⁿb⁰ + C(n,1)a^n-1b¹ +...+ C(n,p)a^n-pb^p +...+ C(n,n-1)a¹b^n-1 + C(n,n)a⁰bⁿ

   où C(n,p) = n! / ( n!×(n-p)! ).
   Ce qui donne par exemple : (a+b)³ = a³ + 3a²b + 3ab² + b³.
   La relation de Pascal nous dit que C(n,p) = C(n-1,p) + C(n-1,p-1). Ce qui permet de représenter les C(n,p) ainsi :

   	p=0	p=1	p=2	p=3	p=4	p=5	p=6	p=7	p=8
   n=0	1
   n=1	1	1
   n=2	1	2	1
   n=3	1	3	3	1
   n=4	1	4	6	4	1
   n=5	1	5	10	10	5	1
   n=6	1	6	15	20	15	6	1
   n=7	1	7	21	35	35	21	7	1
   n=8	1	8	28	56	70	56	28	8	1

   La relation de Pascal énonce que chaque case est la somme de celle immédiatement au-dessus et de celle au-dessus à gauche. Par exemple le 70 de la dernière ligne est la somme des deux 35 de la ligne du dessus. (Vous pouvez vérifier, ça marche partout !)

   coeff(_,0,1).
   coeff(P,P,1).
   coeff(N,P,C) :- N>P, P>0, N>0, N1 is N-1, P1 is P-1,
           coeff(N1,P1,C1), coeff(N1,P,C2),
           C is C1+C2.