# Les Tours de Hanoï
## 🎯 Objectif
Mettre en œuvre une **fonction récursive** permettant de résoudre un problème par **décomposition en sous-problèmes similaires**.
## 📄 Énoncé
On dispose de **trois tiges** :
- `A` : tige de départ
- `B` : tige intermédiaire
- `C` : tige d’arrivée
et de `n` disques empilés sur la tige `A`, du plus grand (en bas) au plus petit (en haut).
### Règles
- On ne déplace **qu’un disque à la fois**.
- On ne peut jamais poser un disque **plus grand sur un disque plus petit**.
👉 L’objectif est de **déplacer toute la pile de la tige A vers la tige C**.
## 🧩 Travail demandé
1. Écrire une fonction récursive `hanoi(n, debut, inter, fin)` qui affiche les déplacements.
2. Tester la fonction pour `n = 3`.
3. (Bonus) Modifier la fonction pour **compter le nombre total de déplacements**.
## 📎 Support de travail
- 💾 **Notebook – Exercice**
🔗 https://github.com/unilasalle-apex/Python/blob/main/Les_tours_de_Hanoi.ipynb
## ✅ Corrigés
>[!success]- ✅ Corrigé 1 — Version simple
>```python
>def hanoi(n, debut, inter, fin):
> if n == 1:
> print(debut, fin)
> else:
> hanoi(n-1, debut, fin, inter)
> hanoi(1, debut, inter, fin)
> hanoi(n-1, inter, debut, fin)
>
>hanoi(3, 'A', 'B', 'C')
>```
>[!success]- ✅ Corrigé 2 — Avec comptage des déplacements
>```python
>def hanoi(n, debut, inter, fin):
> if n == 1:
> print(debut, fin)
> return 1
> else:
> return (
> hanoi(n-1, debut, fin, inter)
> + hanoi(1, debut, inter, fin)
> + hanoi(n-1, inter, debut, fin)
> )
>
>print(hanoi(3, 'A', 'B', 'C'))
>```
## 🧠 À retenir
- Une fonction récursive repose toujours sur :
- un **cas de base**,
- un **appel à elle-même** sur un problème plus simple.
- Pour `n` disques, le nombre minimal de déplacements est :
**2ⁿ − 1**.
## 🗓️ Historique
- **Créé le :** 05 février 2026
- **Auteur :** [[Julien DUQUENNOY]]