// // hanoi // But: Deplacer n disques d'une pile 1 a une pile 3 // Regle 1: On ne deplace qu'un seul disque a la fois // Regle 2: On ne peut pas deposer un disque sur un plus petit // // Position de depart: (n=3 disques) // * // *** // ***** //---1--- ---2--- ---3--- // // Position d'arrivee: // * // *** // ***** //---1--- ---2--- ---3--- // // Pour resoudre ce probleme, on utilise: // Deplace(3,1,3,2); // Deplace 3 disques de la position 1 a la position 3, // en utilisant la position 2 comme intermediaire // public class hanoi { // Compte le nombre total de coups public static int nb=0; // Deplace n disque de la position A a la position B // et en utilisant la position T comme position intermediaire // On suppose que les n disque sont numerotes de 1 a n, avec // 1 etant le plus petit, sur le dessus de la pile public static void Deplace(int n,int A,int B,int T) { // Condition d'arret (cas trivial): un seul disque a deplacer if( n==1 ) { nb++; System.out.println(nb+" : Disque "+n+" de "+A+" a "+B); return; } // A partir d'ici, on sait qu'il y a au moins 2 disques a deplacer // Etape 1: // Deplace n-1 disques de A vers T (B sera l'intermediaire) Deplace(n-1,A,T,B); // Etape 2: // Deplace le disque n de A vers B nb++; System.out.println(nb+" : Disque "+n+" de "+A+" a "+B); // Etape 3: // Deplace n-1 disque de T vers B (A sera l'intermediaire) Deplace(n-1,T,B,A); } public static void main(String arg[]) { // Probleme typique: deplace 3 disques de la position 1 vers 3 // avec position 2 comme intermediaire Deplace(3,1,3,2); // Probleme typique plus gros: deplace 10 disques de la position 1 vers 3 // avec position 2 comme intermediaire // Deplace(10,1,3,2); } }