Le problème des tours de Hanoï

Le but du problème est de déplacer tous les disques de la première tige vers la dernière en ne mettant jamais un disque plus grand sur un plus petit.

Grace à la méthode diviser pour régner et la récursivité, nous allons coder la solution en quelques lignes. Cela serait plus complexe avec un code itératif.

La fonction permet de trouver les déplements nécessaire pour déplacer une tour de n disques de la tige A vers la tige C en utilisant la tour annexe B.

L'idée principale de la méthode diviser pour régner est dans ce problème de se concentrer sur une pile de disque de taille n - 1.

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def hanoi(n:int, depart: str = 'A', dest: str = 'C', interm: str = 'B') -> None:
    '''
    Utilise la récursivité et la méthode diviser pour régner
    en divisant le problème tour de n A -> C
    1) tour de n - 1 de A vers B
    2) disque de taille n de A vers C

    Puis en combinant en re déplaçant
    tour de n - 1 disques de B vers C

    '''

    if n == 1:
        print(f" DĂ©place disque 1 de {depart} vers {dest}")
        return None

    # Diviser
    hanoi(n - 1, depart, interm, dest)
    print(f" DĂ©place disque {n} de {depart} vers {dest}")

    # Combiner
    hanoi(n - 1, interm, dest, depart)

voici l'affichage

Python
1
2
3
4
5
6
7
8
>>>hanoi(3)
 DĂ©place disque 1 de A vers C
 DĂ©place disque 2 de A vers B
 DĂ©place disque 1 de C vers B
 DĂ©place disque 3 de A vers C
 DĂ©place disque 1 de B vers A
 DĂ©place disque 2 de B vers C
 DĂ©place disque 1 de A vers C