Hanoi

Question

Bonjour tout le monde!
J'ai un projet sur la résolution d'une tour de hanoi en java.
J'ai fait des recherches et voici ce que j'ai choisi comme code:
package hanoi;

import javax.swing.JOptionPane;
/*
- déplacer les disques du pilier de départ au pilier d'arrivée en utilisant un pilier intermédiaire
- un disque d'un certain diamètre ne peut pas être placé au dessus d'un disque de diamètre inférieur.
si on a "n" disques à déplacer :
- d'abord on déplace les premiers n-1 disques de depart vers intermediaire(en utilisant arrivée comme tour intermediaire)
- ensuite on déplace le dernier disque(le disque "n") de départ vers arrivée
- enfin on déplace les n-1 disques de intermediaire vers arrivée(en utilisant le pilier de départ comme tour intermediaire)
NB:hn=(2 exposant(n))-1(avec hn le nbre de déplacement de disques nécéssaire)
*/

public class Hanoi {
public static void hanoi(int n, String dep, String temp, String arr) {
if (n == 0) return;
hanoi(n-1, dep, arr, temp);
System.out.println("Déplacez le disque " + n + " de " + dep + " à " + arr);
hanoi(n-1, temp, dep, arr);
}

public static void main(String[] args) {
String a;
int n;
a = JOptionPane.showInputDialog("Combien de diques ?");
n = Integer.parseInt(a);
hanoi(n, "A", "B", "C"); //A,B,C les 3 piliers:A le pilier de départ,B le pilier intermediaire,C le pilier d'arrivée
}
}

Bon le probleme est que je ne serai pas à mesure d'expliquer ce code à mon prof, surtout la méthode hanoi, je n'arrive pas à comprendre comment elle tourne, à quoi sert le if(n==0)return;?
Moi je pense que n n'est jamais égal à 0 mais quand je mets cette ligne en commentaire,rien ne marche.
SVP si quelqu'un peut bien m'expliquer ce code, je lui serai très reconnaissant. Merci d'avance!

cs_jojolemariole · Answer

Salut,

Ce code est correct et résout par récursivité le problème des tours de Hanoï.
Le commentaire en début de code me semble clair.

Cette méthode est ultra-classique :
http://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF

Peut-être n'es-tu pas à l'aise avec la programmation par récursivité?
Il existe une version itérative, moins élégante.

Si ça peut t'aider à comprendre la récursivité, regarde les deux fonctions suivantes. La première calcule la factorielle d'un nombre par récursivité, la seconde par une itération.


/**
 * Calcule la factorielle d'un entier naturel par récursivité.
 * 
 * @param nombre
 *            un entier naturel inférieur ou égal à 20
 * @return nombre! (la factorielle du nombre)
 */
public static final long factorielleRecursivite(int nombre) {

long factorielle;

if (nombre == 0) {
factorielle = 1;
} else {
factorielle = nombre * factorielleRecursivite(nombre - 1);
}

return factorielle;

}

/**
 * Calcule la factorielle d'un entier naturel par itération.
 * 
 * @param nombre
 *            un entier naturel inférieur ou égal à 20
 * @return nombre! (la factorielle du nombre)
 */
public static final long factorielleIteration(int nombre) {

long factorielle = 1;

for (int i = 2; i <= nombre; i++) {
factorielle *= i;
}

return factorielle;

}

Hanoi

1 réponse

Votre réponse

Discussions similaires