Discussion :

[patrick974]

Bonjour tout le monde.
Je suis en train de bosser sur un tp de Prolog intitulé "Arithmétique de Péano". Je vous donne l'introduction du tp, au cas où vous ne sauriez pas de quoi il s'agit ...

On code les entiers naturels à l'aide des entiers de Péano :

* la constante 0 et de
* la fonction unaire s.

Par exemple, 3 est codé s(s(s(0))). Proposer et discuter, suivant l'instanciation des arguments, les différentes définitions sous forme de clauses de Horn définies (i.e. en Prolog pur) des relations suivantes :
...

J'ai déjà codé plusieurs relations. Je suis bloqué à celle du pgcd.
J'ai bien réussi à pondre quelque chose, mais ce code marche uniquement pour des nombres qui ne sont pas premier entre eux, comme par exemple 6 et 3, 4 et 2 (il ne marche pas pour 3 et 2 par exemple ...). Je voudrais avoir votre aide pour coder la fonction pgcd.

Voilà ce que j'ai fait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
----------------------------------------
add(0,X,X).
add(X,0,X).
add(s(X), Y, s(Z)) :-
	add(X, Y, Z).
----------------------------------------
----------------------------------------
% Division euclidienne entre deux entiers
div(A,B,0,A) :-
	inf(A,B).
div(A, B, s(Q), R) :-
	div(Aa, B, Q, R),
	add(Aa, B, A).
-----------------------------------------
-----------------------------------------
% PGCD de deux entiers de Peano
pgcd(X,Y,Z) :-
	div(X,Y,Z,0).
pgcd(X,Y,P) :-
	div(X,Y,_Q,R),
	pgcd(Y,R,P).
------------------------------------------
 
add(0,X,X).
add(X,0,X).
add(s(X), Y, s(Z)) :-
	add(X, Y, Z).

Voilà, j'espère avoir été assez clair. Si vous voulez savoir autre chose, je suis à votre disposition. Merci de vous être donné la peine de lire ma discussion.

[Trap D]

Tu es sûr de la division ?
J'ai teste

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

	div(s(s(s(s(0)))), s(s(s(0))), X, Y).

et ça plante alors que celà devrait donner X = s(0) et Y = s(0) si je ne m'abuse.

D'autre part, tu te plantes dans les clauses du PGCD, réfléchis à ce que tu écris.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
pgcd(X,Y,Z) :-
    div(X,Y,Z,0).

Le PGCD de X et Y n'est pas Z lorsque le reste de la division euclidienne est 0 !

Il faut aussi montrer comment tu définis inf.

[patrick974]

bonjour,

ok pour div. j'ai tester sur plusieurs nombres et ça marchait. Je me suis trompé. C'est sur que je pourai pa faire le pgcd sans la division euclidiennne, donc je vais revoir la division avant.

Voila pour la definition de inf :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
inf(0,X) :-
	X \= 0.
inf(s(X), s(Y)) :-
	inf(X, Y).

Pour les clauses du pgcd :
le pgcd est le dernier reste non nul. Sachant que a chaque fois, je remplace le diviseur par le reste, la bonne clause devrai être :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
pgcd(X,Y,Z) :-
	div(X,Z,_,0).

J'ai peut etre ecri des betises. Je vais me remettre au travail ...
Merci.

[patrick974]

La clause du pgcd est fausse, j'ai posté sans reflechir.
desolé.

[patrick974]

Il suuffisait de traduire bêtement la division euclidienne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
div(A,B,Q,R) :-
	mul(B, Q, M),
	add(M, R, A),
	inf(R,B).

[Trap D]

Pour la division, tu n'as pas besoin de définir mul il me semble.
Il est vrai que je l'ai définie de manière récursive, j'ai repris ton premier code en le corrigeant.

[patrick974]

Ok, ça me rassure un peu : mon premier code n'était pas bon a rien. Je vais le corriger aussi, mais avant je vais essayez de trouver quelquechose pour pgcd ...

Je sens que le partiel de prolog va fun !!

[patrick974]

Bon, me revoila a la charge.
J'ai une nouvelle version du pgcd, mais rien a faire, pas de terminaison pour les nombres premiers entre eux.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
pgcd(X,Y,Y) :-
	div(X,Y,_,0).
pgcd(X,Y,Z) :-
	div(X,Y,_,R),
	pgcd(Y,R,Z).

Je n'en peux plus, si quelqu'un a une solution, je suis preneur !!
Merci.

[Trap D]

Ton code me paraît correct, j'ai le même que toi pour le PGCD et ça fonctionne chez moi.
Peut-être ton div est-il incorrect, moi je n'utilise pas mult.

Au fait, si le nombres sont premiers entre eux, le PGCD doit être s(0), on est bien d'accord ?

[patrick974]

Oui, "deux nombres sont premiers entre si leur pgcd est 1". On est bien d'accord.
Si on a le meme code, c'est que j'ai compri pour le pgcd.
Bien, je vais essayer de coder la division de façon récursive. et voir ce que ça donne pour le pgcd apres.
Merci.

[patrick974]

Bon, alors voila.
j'ai finalement redefini la fonction div de façon récursive.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
div(A,B,0,A) :-
	inf(A,B).
div(A,B,s(Q),R) :-
	add(B,Q1,A),
	div(Q1,B,Q,R).

L'ennui, c'est que cette fonction n'est pas robuste. Elle ne gere pas certaines erreurs... Mais elle marche.
Finalement, ma fonction pgcd est valide, que ce soit avec des nombres premier entre eux ou pas. Toujours le même code ...
Donc là, ça va.

j'ai fait une autre fonction, premier qui teste la primarité d'un nombre (mais il ne faut pas faire attention a la complexité, c'est du code naif !). Pour ceux que ça interesse :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
% Test de primarité de deux entiers de Peano
divisible(_, s(0)) :-
	!, fail.
divisible(X,Y) :-
	div(X,Y,Q,0),
	inf(Q,X).
divisible(X, s(Y)) :-
	divisible(X,Y).
 
premier(s(0)) :-
	!, fail.
premier(0) :-
	!, fail.
premier(s(X)) :-
	\+ divisible(s(X), X).

J'ai testé cette fonction. Elle a l'air de marcher, mais je me trompe peut être (cf plus haut, avec la fonction div que je pensais correcte).
Ben voila !!
Merci pour ton aide Trap D.

[Trap D]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
div(A,B,0,A) :-
	inf(A,B).
div(A,B,s(Q),R) :-
	add(B,Q1,A),
	div(Q1,B,Q,R).

Quelles erreurs ne gère-elle pas ?
J'avoue que je n'ai pas bien compris tes prédicats pour la prilmarité.
Quel est le sens exact du prédicat divisible ?

[patrick974]

Bonjour,
oui c'est vrai, j'ai pas mi de commentaire donc c'est pas facile.
Admettons que je teste la primarité de s(X).
En fait je cherche un diviseur de s(X) a partir de X dans le sens descendant.
Je commence a partir de X car je cherche les diviseurs autres que s(X) et s(0). Le premier predicat divisble, empeche que le diviseur trouvé soit s(0).
Le deuxieme prédicat, indique que X est un diviseur, si le reste de la division euclidienne par X est nul.
Le predicat divisible est vrai si X admet un diviseur strictement plus petit que X et autre que s(0) et 0.
Et finalement, pour premier ça coule de source.

Et pour div, la fonction est robuste, tu as raison. Mais le truc, c que quand je demande d'autre réponse à prolog, il me sort la meme réponse que la premiere. Il y a bien unicité de la réponse, mais il fait des recherche pour rien... Enfin, c'est 3 fois rien.