Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Tours de Hanoï en caml

Posté par
Vladi
13-04-10 à 17:36

Bonjour,
j'ai un petit problème pour la résolution du jeu des tours de hanoï (en caml).
Le programme est composé de deux parties:
(*Une fonction auxiliaire pour  imprimer les mouvements*)
let mouvement de vers =
print_string
("Deplace un disque de la tige " ^ de ^ "à la tige"^ vers);
print_newline ();;
(*Je ne comprends pas très bien la syntaxe en gras quand je compare à l'exemple pour n=3*)
(*La procédure principale*)
let rec hanoi depart milieu arrivee = function
|0->()
|n->hanoi depart arrivee milieu (n-1);
mouvement depart arrivee;
hanoi milieu depart arrivee (n-1
);;
(*... et la partie récursive est un peu obscure pour moi...*)

Un exemple pour n =nbre de disques=3:
hanoi "A" "B" "C" 3;;
#Deplace un disque de la tige Aà la tigeC
Deplace un disque de la tige Aà la tigeB
Deplace un disque de la tige Cà la tigeB
Deplace un disque de la tige Aà la tigeC
Deplace un disque de la tige Bà la tigeA
Deplace un disque de la tige Bà la tigeC
Deplace un disque de la tige Aà la tigeC
- : unit = ()


Y-a-il qn qui puisse m'éclairer?
Merci!

Posté par
jtorresm
re : Tours de Hanoï en caml 14-04-10 à 13:01

Salut!

Comme informaticien, je connais très bien le problème des tours de Hanoi. C'est l'exemple classique pour apprendre la recursivité dans les langages comme Pascal, Algol, etc.

Pourtant, je ne comprends pas exactement quelles sont tes questions.

C'est quoi "caml"? Je pourrais te décrire l'algoritme dans un language structuré comme ALGOL, PASCAL, C.

Johnny

Posté par
Vladi
re : Tours de Hanoï en caml 14-04-10 à 15:43

Caml est le langage que j'utilise. Mes problèmes sont:
- je ne comprends très bien la partie récursive du programme
let rec hanoi depart milieu arrivee = function
|0->()
|n->hanoi depart arrivee milieu (n-1);
mouvement depart arrivee;
hanoi milieu depart arrivee (n-1);;
bien que je comprenne la récursivité en général (si on arrive à résoudre le problème pour n disques on peut le résoudre pour n-1 etc...)
- je ne comprends pas bien la syntaxe en gras:
let mouvement de vers =
print_string
("Deplace un disque de la tige " ^ de ^ "à la tige"^ vers);
print_newline ();;
car lorsque je regarde ce que renvoit l'ordi:
Deplace un disque de la tige Cà la tigeB par exemple
la terme "de" entre les guillemets a disparu
Merci!

Posté par
le_chat
re : Tours de Hanoï en caml 26-04-10 à 02:47

Le truc pour comprendre le mécanisme: si on sait deplacer n-1 pieces du jeu, et qu'on dispose de n pieces en A.
On déplace les n-1 pièces en B.
Ensuite on déplace la dernière pièce en C
Puis on redeplace n-1 pieces en C.

Donc hanoi n pour faire A->C (A vers C) correspond à :
hanoi n-1 A->B
la dernière pièce fait A->C
hanoi n-1 B->C

voila



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !