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
  }

Etienne.Duris[at]univ-mlv.fr - © École Nationale des Ponts et Chaussées - Décembre 2001 - http://www-igm.univ-mlv.fr/~duris/ENPC