Tours de Hanoï
Algorithmique classique
Enonce
Résoudre le problème des tours de Hanoï pour n disques. Retourner la liste des mouvements sous forme de tuples (source, destination).
Signature attendue
def hanoi(n: int, source: str, auxiliaire: str, destination: str) -> list:Exemples
hanoi(2, 'A', 'B', 'C')→[('A','B'),('A','C'),('B','C')]len(hanoi(3, 'A', 'B', 'C'))→7len(hanoi(4, 'A', 'B', 'C'))→15
📖 Rappel de cours
Pour déplacer n disques : on déplace les n−1 du dessus vers la tige auxiliaire, on bouge le plus grand vers la destination, puis on ramène les n−1 par-dessus.
⚠ Le piège : Le nombre de déplacements est 2n − 1 : la croissance est exponentielle. Le cas de base — zéro disque, on ne fait rien — est ce qui fait terminer la récursion.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Écart-Type d'une Liste
- Mode (Élément le Plus Fréquent)
- Histogramme de Fréquences
- Permutations d'une Liste
- Combinaisons de k parmi n
- Flocon de Koch (coordonnées)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.