Tour de Hanoi

Bonsoir, Qqun connait il le principe du jeu : "la tour de Hanoi"?

Bonjour

Forum Algo.
Pour l'implémentation en C tu pourras revenir si tu as des problèmes.
Sinon le prinicpe c'est déplacer la tour A vers la tour B en utilisant la tour C, en ne déplacant à chaque fois qu'un seul disque.
Il y a trois méthodes, la récursive, la dérécursivée utilisant une pile et l'itérative.

Merci :wink:

voilà pour t'entrainer un peu,

Je te conseille fortement d'utiliser les piles.

Pourquoi ????
Il faut savoir utiliser aussi la récursivité, même si c'est le compilo qui fait le travail.

Citation:

---

Envoyé par Trap D

Pourquoi ????
Il faut savoir utiliser aussi la récursivité, même si c'est le compilo qui fait le travail.

---

Je trouve plus simple avec les piles et la recursivité (on peut comparer une tour a une pile [on empile, on depile])

Je ne suis pas sûr d'avoir bien compris :cry: (les piles et la récursivité).

La recursivite je pense que c est le mieux si tu n es pas trop regardant a la performance.
Avec un nombre de palets consequents ca devient vite cauchemardesque...

Mais au niveau ecriture, c'est le plus simple (pour peu qu on soit a l aise avec la recursivite).

En faisant un truc tres compact tu arrive a une fonction d'une dizaines de lignes.

Sinon pour une version plus "lisible" :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

void move_hanoi(int nb_disk, int src, int dst) { if (nb_disk > 1) { move_hanoi(nb_disk - 1, src, get_free(src, dst)); move_hanoi(1, src, dst); move_hanoi(nb_disk - 1, get_free(src, dst), dst); } if (nb_disk == 1) { put_nbr(src); putchar('-'); putchar('>'); put_nbr(dst); putchar('\n'); } }   int my_hanoi(int nb_disk) { move_hanoi(nb_disk, 1, 3); return (0); }

---

Explication rapide :
dans ton main tu appelle my_hanoi.
put_nbr je fais pas un dessin ca affiche un nombre.
get_free non plus ca te retourne la troisieme tour : get_free(2, 3) -> 1

C'est pas le plus court, mais c'est relativement clair. Et ca marche.
Vive la recursivite.

Mais encore une fois, si tu fais un hanoi consequent tu va avoir un nombre de fonctions creees enorme.

au fait, le fameux get_free(src, dest), tu peut être simplement implémenté ainsi:

Code:

---

int get_free(int src, int dst) { return (6 - src - dst); }

---