Prolog - TD 1 - Exercices corriges

Prolog - TD 2
Opérations et récursivité Expressions Arithmétique La semaine dernière « TD1 », nous avons vu l'expression Y is X-1. Cette
expression est un prédicat particulier qui permet une opération
arithmétique. De la même manière, on peut utiliser les opérateurs
. + addition
. - soustraction
. * multiplication
. / division réelle
. // division entière
. mod reste de la division entière
. ** puissance
Attention, Prolog n'est pas capable d'inverser les opérations arithmétiques
! Exemple :
?- Y is 5+2.
Y = 7
?- 7 is X+2.
ERROR: Arguments are not sufficiently instantiated Booléens
. A=B cherche à rendre A et B égaux.
o 3=1+2 est No
o X=1+2 est Yes avec X=1+2 (si, si, vous pouvez essayer)
. A==B A et B sont-ils identiques ?
o 3==1+2 est No
o X==1+2 est No
. A=:=B A et B ont-ils la même valeur ?
o 3=:=1+2 est Yes
o X=:=1+2 provoque une erreur
. AB supériorité (numérique)
Opérateurs logiques Pour modifier le fonctionnement d'une règle de déduction, on peut employer
des opérateurs logiques :
. a :- b si b est vrai, alors a est vrai
. a :- b,c si b et c sont vrais, alors a est vrai
. a :- b;c si b ou c est vrai, alors a est vrai
. a :- \+ b si b est faux, alors a est vrai
. a :- b -> c;d si b est vrai, si c est vrai, alors a est vrai - de
plus, si b est faux, alors si d est vrai, alors a est vrai
Exercices utilisant les opérateurs
Parité, imparité
Méthode récursive
Vous allez définir les règles nécessaires pour que la requête
?-pair(X)
réponde Yes lorsque X est pair, No dans le cas contraire et pour que la
requête
?-impair(X)
réponde Yes lorsque X est impair, No dans le cas contraire.
Bien entendu, il doit y avoir une manière de faire cela en utilisant des
divisions, mais vous allez faire cela en utilisant la récursivité.
1. Écrivez une règle qui précise que 0 est pair.
2. Écrivez une règle qui précise que si X est pair, alors X+2 est pair.
3. Écrivez les règles correspondantes pour les impairs.
4. Votre programme fonctionne-t-il dans le cas des nombres négatifs ?
Dans le cas contraire, modifiez-le pour qu'il fonctionne.
Méthode mutuellement récursive
Pour ne pas confondre, nous allons maintenant définir des règles pour les
prédicats odd/1 et even/1. En version sous-titrée, odd = impair et even =
pair. Cette fois, nous allons employer la récursivité mutuelle.
1. Écrivez une règle qui précise que 0 est even.
2. La règle suivante précise que si Y est impair, Y+1 est pair
even(X) :- Y is X-1, odd(Y).
3. Écrivez une règle qui précise que si Y est pair, alors Y+1 est impair.
4. Votre programme fonctionne-t-il dans le cas des nombres négatifs ?
Dans le cas contraire, modifiez-le pour qu'il fonctionne.
Les tours de Hanoi (plus difficile).
Les tours de Hanoi (aussi appelées Tours de Brahma ou Puzzle de la fin de
fin du monde) ont été inventées par un mathématicien Français, Edouard
Lucas, en 1883. Il a été inspiré par une légende. Dans un temple Hindou,
les prêtres reçurent une pile de 64 disques d'or, chacun un peu plus petit
que celui d'en-dessous, empilés sur un poteau, et deux poteaux vides. Ils
devaient transférer les 64 disques d'un poteau à un autre, avec une seule
règle : Un disque ne peut pas être placé sur un autre disque plus petit. La
fin du monde arrivera lorsqu'ils finiront leur travail. Comme je n'ai pas particulièrement l'intention de détruire le monde, nous
nous contenterons de N disques avec N