Discussion :

[johnny3]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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 )

[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 )

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.