Tours de Hanoi

Les Tours de Hanoi, c'est un puzzle classique. Tu as trois tiges (A, B, C) et n disques de tailles differentes empiles sur la tige A, du plus grand en bas au plus petit en haut. L'objectif : deplacer tous les disques de A vers C, en respectant deux regles :
1. Tu ne peux deplacer qu'un seul disque a la fois
2. Un disque ne peut jamais etre pose sur un disque plus petit

La solution récursive est elegante :
- Pour deplacer n disques de A vers C :
1. Deplace n-1 disques de A vers B (en utilisant C comme intermediaire)
2. Deplace le plus grand disque de A vers C
3. Deplace n-1 disques de B vers C (en utilisant A comme intermediaire)

Le nombre minimal de deplacements est 2 puissance n - 1. Pour 3 disques, ca fait 7 deplacements.

Écris deux fonctions :
- hanoi_deplacements(n) qui retourne le nombre de deplacements
- hanoi_sequence(n, source, cible, intermediaire) qui retourne la liste des deplacements sous forme de tuples (depuis, vers)

Exemple :
hanoi_deplacements(3) renvoie 7
hanoi_sequence(2) renvoie [('A', 'B'), ('A', 'C'), ('B', 'C')]

Tests (4/5)

3 disques

assert hanoi_deplacements(3) == 7

0 disque

assert hanoi_deplacements(0) == 0

1 disque

assert hanoi_deplacements(1) == 1

Sequence 2 disques

assert hanoi_sequence(2) == [('A', 'B'), ('A', 'C'), ('B', 'C')]

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def hanoi_deplacements(n):
    if n == 0:
        return 0
    return 2 * hanoi_deplacements(n - 1) + 1

def hanoi_sequence(n, source='A', cible='C', intermediaire='B'):
    if n == 0:
        return []
    étape1 = hanoi_sequence(n - 1, source, intermediaire, cible)
    étape2 = [(source, cible)]
    étape3 = hanoi_sequence(n - 1, intermediaire, cible, source)
    return étape1 + étape2 + étape3

← Aplatir une liste imbriquee Recherche binaire récursive →

solution.py

Bravo!

Tours de Hanoi

Tests (4/5)

Indices (3 disponibles)

Solution officielle