Exercice : Les tours de Hanoï

En cours, nous avons vu que le problème des tours de Hanoï peut être résolu simplement à l’aide d’une procédure récursive :

Pour déplacer N disques du pilier 1 au pilier 3 :

• Si N=1, déplacer le disque ;

• Sinon :

  • Déplacer récursivement N-1 disques du pilier 1 vers le pilier 2 ;

  • Déplacer le disque restant du pilier 1 vers le pilier 3 ;

  • Déplacer récursivement N-1 disques du pilier 2 vers le pilier 3.

Cette description permet de comprendre facilement l’intuition du principe de résolution mais ne donne pas les détails permettant de l’implémenter.

Écrivez un programme utilisant une fonction récursive qui demande à l’utilisateur le nombre de disques présents sur le premier pilier et affiche les instructions pour la résolution sous la forme suivante (pour une tour de trois disques) :

Disque 1 de 1 vers 3
Disque 2 de 1 vers 2
Disque 1 de 3 vers 2
Disque 3 de 1 vers 3
Disque 1 de 2 vers 1
Disque 2 de 2 vers 3
Disque 1 de 1 vers 3

BEGIN SOLUTION

void hanoi(int n, int a, int b) {
    if (n == 0) return;
    int t = 6 - a - b;
    hanoi(n - 1, a, t);
    cout << "Disque " << n << " de " << a << " vers " << b << endl;
    hanoi(n - 1, t, b);
}
int main() {
    int n;
    cin >> n;
    hanoi(n, 1, 3);
    return 0;
}

END SOLUTION