Tours de Hanoï — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 4)

Tours de Hanoï

Méthodes · niveau 3 (difficile)

Énoncé

Trois piquets A, B, C ; $n$ disques de tailles différentes sont empilés sur A, du plus grand en bas au plus petit en haut. Il faut les déplacer sur C, un disque à la fois, sans jamais poser un disque sur un plus petit.

Expliquer pourquoi, pour déplacer $n$ disques de A vers C, il suffit de déplacer $n - 1$ disques de A vers B, puis le plus grand de A vers C, puis les $n - 1$ disques de B vers C.
Écrire la méthode récursive static void hanoi(int n, char depart, char arrivee, char intermediaire) qui affiche les déplacements, et l'exécuter pour $n = 3$ .
Combien de déplacements pour $n$ disques ? Le vérifier par le programme pour $n = 1, \dots, 10$ .

Corrigé

Pour poser le plus grand disque sur C, il faut que C soit vide et que ce disque soit seul sur A : les $n - 1$ autres sont donc tous sur B. On les y amène (problème de taille $n - 1$ , B jouant le rôle d'arrivée), on déplace le grand disque, puis on ramène les $n - 1$ disques de B sur C (encore un problème de taille $n - 1$ ). Le grand disque, en bas, ne gêne jamais. -


static void hanoi(int n, char depart, char arrivee, char intermediaire) {
    if (n == 0) return;                                  // rien à déplacer
    hanoi(n - 1, depart, intermediaire, arrivee);
    System.out.println("  disque " + n + " : " + depart + " -> " + arrivee);
    hanoi(n - 1, intermediaire, arrivee, depart);
}


  disque 1 : A -> C
  disque 2 : A -> B
  disque 1 : C -> B
  disque 3 : A -> C
  disque 1 : B -> A
  disque 2 : B -> C
  disque 1 : A -> C

Si $D (n)$ est le nombre de déplacements, $D (0) = 0$ et $D (n) = 2 D (n - 1) + 1$ , d'où $D (n) = 2^{n} - 1$ . Le programme compte $1, 3, 7, 15, 31, 63, 127, 255, 511, 1023$ pour $n = 1, \dots, 10$ . Pour $64$ disques, à un déplacement par seconde, il faudrait près de $585$ milliards d'années.