11.8. Exemple : les tours de Hanoi

Le problème des « tours de Hanoï » peut s’énoncer de la manière suivante :

Le programme shell récursif hanoi traite ce problème ; il utilise quatre arguments : le nombre de disques et le nom de trois tables.

#!/bin/bash

if (( $1 > 0 ))
  then
    hanoi $(( $1 - 1)) $2 $4 $3
    echo Deplacer le disque de la table $2 a la table $3
    hanoi $(( $1 - 1)) $4 $3 $2
fi

Pour exécuter ce programme, on indique le nombre total N de disques présents sur la première table, le nom de la table où sont placés ces N disques et le nom des deux autres tables.

Dans l'exemple mentionné, la table A contient au départ trois disques et les deux autres tables B et C sont vides. Le programme affiche chaque déplacement effectué.

$ hanoi 3 A B C
Deplacer le disque de la table A a la table B
Deplacer le disque de la table A a la table C
Deplacer le disque de la table B a la table C
Deplacer le disque de la table A a la table B
Deplacer le disque de la table C a la table A
Deplacer le disque de la table C a la table B
Deplacer le disque de la table A a la table B
$