Résoudre le problème de la tour de Hanoï en Python

Le problème de la tour de Hanoï est un casse-tête mathématique fondamental qui est présenté aux nouveaux programmeurs au début pour qu’ils amplifient leur quiz de résolution de problèmes.

Le problème est simple, impliquant trois tiges. Une tige contient plusieurs disques dans l’ordre décroissant, avec le plus grand disque en bas et le plus petit en haut. Nous devons transférer cela de la tige une à la tige trois en utilisant la deuxième tige.

Nous devons garder certaines règles à l’esprit. On ne peut déplacer qu’un seul disque à la fois et on doit prendre le disque en haut de la tige. De plus, nous ne pouvons pas placer un disque plus grand sur un disque plus petit.
En gardant tout cela à l’esprit, nous devons résoudre ce problème et calculer le nombre total de mouvements effectués pour le résoudre.

Dans ce tutoriel, nous allons vous présenter comment résoudre ce problème. Nous utiliserons une méthode récursive pour résoudre le problème de la tour de Hanoï en Python.

Cette méthode créera une fonction qui s’appellera récursivement en fonction de certaines conditions pour résoudre le problème de la tour de Hanoï.
Nous implémentons la logique pour cela dans le code suivant.

def ToH(n, A, B, C):
    if n == 1:
        print("Disk 1 from", A, "to", B)
        return
    ToH(n - 1, A, C, B)
    print("Disk", n, "from", A, "to", B)
    ToH(n - 1, C, B, A)


ToH(3, "A", "B", "C")

Production:

Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C
Disk 3 from A to B
Disk 1 from C to A
Disk 2 from C to B
Disk 1 from A to B

Dans l’exemple ci-dessus, nous déplaçons trois disques de la tige A à la tige B à l’aide de la tige C.

Comme vous pouvez le voir, le nombre total de coups effectués dans l’exemple ci-dessus est de 7. Pour un nombre n de disques, le nombre total de coups effectués à l’aide de cette méthode est toujours égal à 2^n -1.

Au fil du temps, quelques autres solutions ont émergé pour résoudre le problème de la tour de Hanoï à l’aide de piles. Pourtant, il n’est pas recommandé de les utiliser car de telles méthodes sont très inefficaces en termes de temps et de rapidité.