|
% naive_reverse/2 : retourner/inverser récursivement une
liste sur elle même .
naive_reverse([],[]).
naive_reverse([X|Xs],Zs) :- naive_reverse(Xs,Ys), append(Ys,[X],Zs).
% on "dérécursive" ce prédicat en rendant l'appel récursif
terminal et en se servant d'un "accumulateur" pour %faire les calculs
"en marchant"
% reverse/2 : retourner/inverser une liste de manière
itérative. % prédéfini SWI
renverse(L1,L2):- renverse(L1,[],L2). %remarque
: renverse/2 est un prédicat différent de renverse/3
renverse([],L,L). % le travail est terminé : le
contenu de l'accumulateur est retourné comme résultat.
renverse([X|L1],Acc,L2) :- renverse(L1,[X|Acc],L2). %on pose un
élément de la liste à inverser sur l'accumulateur.
QUESTION 1 : Vérifier que ces deux prédicats
retournent/inversent correctement la liste [a,z,e,r,t,y,u,i,o,[a,z,e,r,t,y,u,i,o,p]]
.
QUESTION 2 : Ces prédicats sont-ils réversibles
? i.e. peut-on inverser une liste en la proposant en deuxième paramètre
et en attendant le résultat en premier paramètre ?
En arithmétique de Peano nous avons écrit en ED :
:- op(800 , fy , s). %pour moins de parenthèses
%On spécifie les entiers naturels par :
nat(z).
nat(s(N)) :- nat(N).
% Donc, 5 s'écrit maintenant : s s s s s z
% Mais cela fait encore beaucoup de symbole alors on
spécifie les prédicats de transformation des entiers décimaux en nat %"(int2nat/2)" et de transformation des nat en entiers décimaux
nat2int/2.
%A cause de la particularité de 'is' on doit écrire 2
prédicats
int2nat(0 , z).
int2nat(INT , s(NAT)) :- IN is INT-1 , int2nat(IN,NAT).
nat2int(z, 0).
nat2int(s(NAT),INT) :- nat2int(NAT , IN) , INT is IN+1.
% l'addition de 2 entiers: addi/3
addi(z,X,X) :- nat(X).
addi(s(X),Y,s(Z)):- addi(X,Y,Z).
%la multiplication de 2 entiers : mult/3
mult(z,X,z) :- nat(X).
mult(s(X),Y,Z) :- mult(X,Y,W), addi(W,Y,Z).
%fact/2 : factorielle (!)
fact(z, s(z)).
fact(s(N),F) :- fact(N,FF), mult(s(N),FF,F).
Après avoir charger tout ce qui précède
sous Prolog répondre aux questions suivantes.
QUESTION 3 : Constater que 5 ! =120 , et que ce
résultat est unique.
QUESTION 4 : Constater que fact/2 est réversible
(cf. ci dessus , 120=5!)
on dérécusive fact/2 pour "calculer en marchant" : fac/3
(cf. renverse)
fac(z, F , F).
fac(s(N),Acc , R) :- mult(s(N),Acc,F) , fac(N,F , R).
QUESTION 5 : Spécifier fac/2 qui permet d'appeler
fac/3 dans les conditions telles que le résultat soit correct. Et
constater que fac/2 est toujours réversible.
En arithmétique en Prolog sur les "vrais" entiers la spécification
correspondant à fact/2 s'écrit
facti(0, 1).
facti(N,F) :- N >0 %ATTENTION nécessaire pour avoir une seule
solution et pas de branche infinie
NN is N-1 , facti(NN,FF), F is FF*N.
QUESTION 6 : Dérécursiver ce prédicat en donnant
les spécifications de faci/3 et faci/2 sur le modèle de fac/3 et
fac/2 ci dessus et vérifier qu'on a toujours 5!=120 (?- faci(5 ,
F). ==> F=120 %solution unique)
|
Question 1: |
| |
Les 2 prédicats renversent
bien la liste suivante : [a,z,e,r,t,y,u,i,o,
[a,z,e,r,t,y,u,i,o,p] ]
(note: le dernier element est lui meme une liste, qui
n'a pas elle, a être renversée)
?- naive_reverse([a,z,e,r,t,y,u,i,o,[a,z,e,r,t,y,u,i,o,p]],L).
L = [[a, z, e, r, t, y, u, i, o, p], o, i, u, y, t, r, e, z, a]
Yes
?- renverse( [a,z,e,r,t,y,u,i,o,[a,z,e,r,t,y,u,i,o,p]] ,L).
L = [[a, z, e, r, t, y, u, i, o, p], o, i, u, y, t, r, e, z, a]
Yes
|
|
|
|
Question 2:Les 2
prédicats sont réversibles |
| |
?- naive_reverse(L , [a,b,c,d,e] ).
L = [e, d, c, b, a]
Yes
?- renverse(L, [a,b,c,d,e]).
L = [e, d, c, b, a]
Yes
|
|
|
|
Question 3:5! =
120 : |
| |
(On utilise les predicats
int2nat/2 et nat2int/2 afin de faciliter la lecture du
résultat)
?- int2nat( 5,NAT), fact( NAT , F), nat2int( F, INT).
NAT = s s s s s z
F = s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s z
INT = 120
Yes
%Solution unique ?
?- fact( s s s s s z , F).
F = s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s z ;
No
|
120 est seule solution de 5! |
|
|
Question 4:On
constate que fact/2 est réversible: 120=5! |
| |
?- int2nat( 120, F ), fact( NAT, F), nat2int( NAT, INT).
F = s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s z
NAT = s s s s s z
INT = 5
Yes.
|
|
|
|
Question 5: |
| |
Nouveau prédicat fac/2 :
fac(N, F) :- fac(N, s(z), F).
On constate que fac/2 est toujours réversible :
?- int2nat( 5,NAT), fac( NAT , F), nat2int( F, INT).
NAT = s s s s s z
F = s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s z
INT = 120
Yes
?- int2nat( 120, F ), fac( NAT, F), nat2int( NAT, INT).
F = s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s z
NAT = s s s s s z
INT = 5
|
|
|
|
Question 6: |
| |
Soit facti/2 le prédicat
prolog de Factorielle sur les vrais entiers:
facti(0, 1).
facti(N,F) :- N >0 , NN is N-1 , facti(NN,FF), F is
FF*N.
La version "Dérécursivée" :
faci(0, F, F).
faci(N, Acc, F):- N>0, P is N*Acc, NN is N-1 , faci(NN,
P, F).
faci(N, F) :- faci(N, 1, F).
On teste si 5!=120 est solution unique:
?- faci(5,F).
F = 120 ;
No
?-
|
|
|