ENPC - Programmation -
Corrections 3
Les tours de Hanoï
public class Hanoi {
/**
* Méthode récursive résolvant le problème des tours de Hanoï.
* Permet d'effetcuter le déplacement de n disques d'une
* tour src vers une tour dest en utilisant une
* tour auxiliaire tmp.
* @param n le nombre de disques sur la tour de départ
* @param src l'identifiant de la tour de départ
* @param dest l'identifiant de la tour d'arrivée
* @param tmp l'identifiant de la tour auxiliaire
*/
static void hanoi(int n, char src, char dest, char tmp) {
if (n <= 0)
return;
switch(n) {
case 1:
// si un seul disque à déplacer
move(src, dest);
break;
case 2:
// si deux disques à déplacer, on utilise l'intermédiare
move(src, tmp);
move(src, dest);
move(tmp, dest);
break;
default:
// si plus de 2 disques, on fait deux appels récursifs:
// déplacement de n-1 disques de src vers tmp en utilisant dest
hanoi(n-1, src, tmp, dest);
// déplacement du dernier de src vers dest
move(src, dest);
// déplacement des n-1 disques de tmp vers dest en utilisant src
hanoi(n-1, tmp, dest, src);
}
}
/**
* Méthode représentant le déplacement d'un disque d'une tour vers
* une autre. A priori, il s'agit toujours du disque sur le dessus
* de la tour from. Cette implémentation se contente de
* donner des indications à l'utilisateur, sous la forme d'un
* affichage.
* @param from désigne la tour d'où il faut prendre le disque
* @param from désigne la tour où il faut poser le disque
*/
static void move(char from, char to) {
System.out.println("Déplacer un disque de " + from +
" vers " + to);
}
/**
* Main de test. Sait lire un entier sur la ligne de commande
* représentant le nombre de disques souhaités. En l'absence de cet
* argument, utilise 4 disques.
*/
public static void main(String[] args) {
int i = 4;
if (args.length > 0) {
i = Integer.parseInt(args[0]);
}
System.out.println("Pour " + i + " disques, voilà les déplacements");
char src = 'A';
char dest = 'C';
char tmp = 'B';
System.out.println("(on suppose qu'on veut déplacer les disques de "
+ src + " vers " + dest + " en utilisant " + tmp);
hanoi(i, src, dest, tmp);
}
}
Le retournement d'un tableau d'entiers en récursif
/**
* Fonction récursive qui place les éléments d'un tableau dans
* l'ordre inverse.
* @param t le tableau à retourner
* @param deb le plus petit indice qui n'a pas encore été échangé
*/
public static void miroir(int[] t, int deb) {
// fin identifie l'index avec lequel il faut échanger deb
int fin = (t.length - 1) - deb;
// condition de récursion:
// les indices ne se croisent pas encore
if (deb < fin) {
int tmp = t[deb];
t[deb] = t[fin];
t[fin] = tmp;
// après échange, appel récursif avec l'indice suivant
miroir(t, deb+1);
}
// condition de terminaison: les indices se croisent
}