Tours de Hanoï

Tours de Hanoï

Algorithme récursif

On admet que vous connaissez les règles du jeu

un petit avertissement pour être sûr

Mais comment réussir ce jeu ?

Certes, vous connaissez les règles mais est-ce que vous connaissez l'astuce pour gagner à chaque coup. Pour atteindre cet objectif, une chose à réfléchir avant de commencer, est-ce que votre nombre de palais est pair ou impair ? Combien de coups faut-il au minimum ?

Pair ou impair ?

Nombre de coups minimum

Début

Jeu à 2 disques sur la tour du milieu

Juste quatre étapes à retenir :-> Début (0 coup) -> Nombre de coups correspondant au jeu de disque précédent -> Déplacement du nouveau disque (+1) -> Nombre de coups correspondant au jeu de disque précédent = (2**n) - 1

0 coups

+3 coups

Jeu à 2 disques sur la tour du droite

Déplacement du gros dique

Rappel

+3 coups (fin = 7 coups)

+1 coups (=> 4 coups)

Par exemple : 4 palets (7 + 1 + 7 = 15), 5 palets (15 + 1 + 15 = 31)

Récursivité ave Python

def hanoi(n, start=1, fin=3, aux=2): if n==1: print("T", start, "-->T", fin) else: hanoi(n-1, start, aux, fin) print("T", start, "-->T", fin) hanoi(n-1, aux, fin, start)

Initialisation de la fonction avec ses paramètres d'entrées

Condition de la récursive pour éviter la boucle infinie

Déplacement du disque le plus petit

Premier rappel récursif : n-1 (échangeant les dernières deux tours)

Déplacement des disques : n-1 (sauf le plus petit)

Deuxième différent rappel récursif : n-1 (échangeant les premières deux tours)

Pour finir, une petite astuce pour gagner à chaque coup

en utilisant le binaire Par exemple, on doit finir par obtenir avec 3 disques :

Plus grand disque

Moyen disque

Plus petit disque

Merci de m'écouter

et je retourne me coucher☺

Déplacement du disque à la tour de droite

Début

0 coups

+1 coups (fin)

Début

Jeu à 1 disque sur la tour du milieu

Déplacement du gros dique

Jeu à 1 disque sur la tour du droite

0 coups

+1 coups

+1 coups (=> 2 coups)

+1 coups (fin = 3 coups)

RETOUR