Les tours de Hanoï

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 6 — Fonctions récursives

Énoncé

Écrire la fonction récursive hanoi(n, depart, via, arrivee) affichant les étapes de déplacement de $n$ disques de la tige de départ à la tige d'arrivée. Déterminer le nombre exact de déplacements et prouver son optimalité.

Corrigé

def hanoi(n: int, depart: str, via: str, arrivee: str) -> None:
    if n == 0:
        return
    hanoi(n - 1, depart, arrivee, via)
    print(depart, "->", arrivee)
    hanoi(n - 1, via, depart, arrivee)

Le nombre de déplacements $D (n)$ obéit à la relation de récurrence $D (n) = 2 D (n - 1) + 1$ , avec $D (0) = 0$ , ce qui donne $D (n) = 2^{n} - 1$ déplacements. Preuve d'optimalité : Pour dégager le disque le plus grand, les $n - 1$ disques supérieurs doivent impérativement être empilés sur la tige intermédiaire, nécessitant au moins $M (n - 1)$ mouvements. Après le déplacement du grand disque ( $1$ mouvement), il faut déplacer à nouveau les $n - 1$ disques de la tige intermédiaire vers la tige finale ( $M (n - 1)$ mouvements). On a donc $M (n) \geq 2 M (n - 1) + 1$ , ce qui démontre qu'aucun algorithme ne peut effectuer moins de $2^{n} - 1$ déplacements.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.