perdu dans l'algorithme de la tour de Hanoi

Bonjour,

j'ai cherché avant de poster mais n'ai pas trouvé de solution.

Je suis en train d'essayer de comprendre l'algorithme récursif de Hanoï mais c'est un vrai casse-tête.

Voici l'algorithme que j'utilise avec les lignes permettant de suivre les étapes:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Data Structures with Java by John R. Hubbard
// Copyright McGraw-Hill, 2001
// Example 4.15 on page 83
// The Towers of Hanoi
public class Hanoi {
	public static void main(String [] args)
	{
		runHanoi(3, 'A', 'B', 'C');
	}
 
	public static void runHanoi(int n, char x, char y, char z)
	{
		if (n == 1)
		{
			System.out.println("n= " + n + ", x= " + x + ", y= " + y + ", z= " + z);
			System.out.println("De " + x + " vers " + z);
			System.out.println();
		} else
		{
			System.out.println("Avant runHanoi(n - 1, x, z, y): n= " + n + ", x= " + x + ", y= " + y + ", z= " + z);
			runHanoi(n - 1, x, z, y);
			System.out.println("Après runHanoi(n - 1, x, z, y): n= " + n + ", x= " + x + ", y= " + y + ", z= " + z);
			System.out.println();
 
			System.out.println("Avant runHanoi(1,x,y,z): n= " + n + ", x= " + x + ", y= " + y + ", z= " + z);
			runHanoi(1, x, y, z);
			System.out.println("Après runHanoi(1,x,y,z): n= " + n + ", x= " + x + ", y= " + y + ", z= " + z);
			System.out.println();
 
			System.out.println("Avant runHanoi(n - 1, y, x, z): n= " + n + ", x= " + x + ", y= " + y + ", z= " + z);
			runHanoi(n - 1, y, x, z);
			System.out.println("Après runHanoi(n - 1, y, x, z): n= " + n + ", x= " + x + ", y= " + y + ", z= " + z);
			System.out.println();
		}
	}
}

Et voici ce que j'obtiens:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Avant runHanoi(n - 1, x, z, y): n= 3, x= A, y= B, z= C
Avant runHanoi(n - 1, x, z, y): n= 2, x= A, y= C, z= B
n= 1, x= A, y= B, z= C
De A vers C
 
Après runHanoi(n - 1, x, z, y): n= 2, x= A, y= C, z= B
 
Avant runHanoi(1,x,y,z): n= 2, x= A, y= C, z= B
n= 1, x= A, y= C, z= B
De A vers B
 
Après runHanoi(1,x,y,z): n= 2, x= A, y= C, z= B
 
Avant runHanoi(n - 1, y, x, z): n= 2, x= A, y= C, z= B
n= 1, x= C, y= A, z= B
De C vers B
 
Après runHanoi(n - 1, y, x, z): n= 2, x= A, y= C, z= B
 
Après runHanoi(n - 1, x, z, y): n= 3, x= A, y= B, z= C
 
Avant runHanoi(1,x,y,z): n= 3, x= A, y= B, z= C
n= 1, x= A, y= B, z= C
De A vers C
 
Après runHanoi(1,x,y,z): n= 3, x= A, y= B, z= C
 
Avant runHanoi(n - 1, y, x, z): n= 3, x= A, y= B, z= C
Avant runHanoi(n - 1, x, z, y): n= 2, x= B, y= A, z= C
n= 1, x= B, y= C, z= A
De B vers A
 
Après runHanoi(n - 1, x, z, y): n= 2, x= B, y= A, z= C
 
Avant runHanoi(1,x,y,z): n= 2, x= B, y= A, z= C
n= 1, x= B, y= A, z= C
De B vers C
 
Après runHanoi(1,x,y,z): n= 2, x= B, y= A, z= C
 
Avant runHanoi(n - 1, y, x, z): n= 2, x= B, y= A, z= C
n= 1, x= A, y= B, z= C
De A vers C
 
Après runHanoi(n - 1, y, x, z): n= 2, x= B, y= A, z= C
 
Après runHanoi(n - 1, y, x, z): n= 3, x= A, y= B, z= C

Je ne comprends pas trop comment n repasse de 1 à 2 ou de 1 à 3.

J'ai beau essayer avec des dessins, je comprends le principe, mais ne pige pas l'algorithme. Si quelqu'un pouvait essayer de m'éclairer.

Merci par avance,
johnny3

le passage de 1 à 3 ne se fait pas. c'est juste une petite illusion ...
n= 3
puis tu entres dans ton récursif, tu fais bouger n ( 3, 2, 1 etc )
puis tu sors de ton recursif donc n revient à 3 ....( valeur qu'il a ce niveau )

merci

Citation:

Envoyé par miloux32

le passage de 1 à 3 ne se fait pas. c'est juste une petite illusion ...
n= 3
puis tu entres dans ton récursif, tu fais bouger n ( 3, 2, 1 etc )
puis tu sors de ton recursif donc n revient à 3 ....( valeur qu'il a ce niveau )

D'accord, c'est déjà un peu plus clair.

Par contre, l'algorithme n'est pas facile au début à comprendre, je rame encore avec les permutations.