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.

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.

Python

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

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