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