Corrigé

On suppose que l'on a les trois emplacements de tours A, B et C ; et que l'on veuille déplacer les disques de la tour A vers la tour C.

1. pour pouvoir déplacer le plus grand disque de la tour A, il faut avoir déplacé tous les disques au-dessus de lui. Comme c'est le plus grand disque, il est de plus seul sur son emplacement
2. une fois le plus grand disque seul sur sa tour, il faut le déplacer en C (ce disque peut être en B ou en A)
3. une fois le plus grand disque à sa place, il convient de déplacer la tour formée des autres disques sur l'emplacement C.

Si $C(n)$ est le nombre de déplacements pour résoudre le problème de la tour de Hanoï, il faut donc au moins :

1. déplacer une tour de $n-1$ éléments : de complexité $C(n-1)$
2. déplacer un disque : de complexité $1$
3. re-déplacer une tour de $n-1$ éléments : de complexité $C(n-1)$

On a donc l'inégalité : $C(n) \leq 1 + 2 \cdot C(n-1)$. On peut avoir égalité si on possède un algorithme optimal, disons hanoï(départ, arrivée, intermédiaire, n-1) pour une tour de taille $n-1$, et que l'on procède ainsi pour déplacer une tour de taille $n$ de A à C sera :

1. hanoï(A, B, C, n-1)
2. déplace le disque restant en A sur l'emplacement C
3. hanoï(B, C, A, n-1)

On obtient alors l'algorithme optimal suivant, en considérant que les tours sont des listes :

A = list(range(5, -1, -1))
B = []
C = []

def hanoi(départ, arrivée, intermédiaire, n):
    if n == 0:
        return
    hanoi(départ, intermédiaire, arrivée, n-1)
    disque = départ.pop()
    arrivée.append(disque)
    print(A, B, C)
    hanoi(intermédiaire, arrivée, départ, n-1)

print(A, B, C)
hanoi(A, C, B, len(A))

On a montré que notre stratégie était optimale. Le nombre d'opérations de déplacement suit alors l'équation de récurrence :

Et la terminaison : $C(0) = 0$

On obtient facilement l'expression, pour $n\geq 1$ :

La somme des $n>0$ premières puissances de 2 est à savoir facilement retrouver (c'est une série géométrique) et vaut $2^{n}-1$.