Je ne comprends pas l'algorithme de Hanoi

Question

Soyons honnêtes: je fais du bon en programmation depuis le début de l'année (lycée lycée) jusqu'au jour où nous avons enfin vu la récursivité. Je ne comprends pas le code récursif de Hanoi Towers: le point spécifique que je ne trouve pas est le changement entre la tour de destination et l'origine et vice versa:

Je comprends fondamentalement ce qu'est la récursivité, et quelle est la pile, mais je ne comprends pas pourquoi l'ordre des tours est changé.

Votre aide sera grandement appréciée. Je vous remercie. // N nombre de pièces

private void Déplacer(short N, string o, string i, string d) 
    { 
     if (N == 1) 
     { 
      MessageBox.Show("Move " + o + "to " + d); 
      lstUn.Items.Add((lstUn.Items.Count + 1).ToString() + "-" + "Move " + o + " vers " + d); 
      return; 
     } 


     else 
     { 
     //Switch d and i 
      Déplacer((short)(N - 1), o, d, i); 
      lstUn.Items.Add((lstUn.Items.Count + 1).ToString() + "-" + "Déplace " + o + " vers " + d); 
      MessageBox.Show("Déplace " + o + " vers " + d); //1 vers 3 
      Déplacer((short)(N - 1), i, o, d); 

     } 

Answer 1

En vertu des règles de la Tour de Hanoi, vous ne pouvez jamais mettre un plus grand disque au-dessus d'un plus petit.

Imaginez trois tours dont la tour 1 comporte trois disques. Pour déplacer les trois disques vers la tour 3, vous devez être en mesure de déplacer le plus gros disque de la tour 1 à la tour 3; cela signifie que vous devez déplacer les deux plus petits disques de la tour 1 à la tour 2. Comment déplacez-vous les deux disques de la tour 1 à la tour 2? Eh bien, vous devez déplacer le disque 1 à la tour 3; alors vous pouvez déplacer le disque 2 à la tour 2; Ensuite, vous pouvez déplacer le disque 1 de la tour 3 à la tour 2. Vous pouvez maintenant déplacer le disque 3 vers la tour 3; et vous devez déplacer les deux disques de la tour 2 à la tour 3 - ce qui signifie que vous déplacez le disque 1 vers la tour 1; puis le disque 2 à la tour 3; et enfin le disque 1 à la tour 3, complétant le processus.

Et c'est l'essence de l'algorithme. Chaque fois que vous devez déplacer un certain nombre de disques d'une tour à une autre, vous vous recurerez.

Une conséquence des règles est que le plus petit disque est déplacé tous les deux pas.

Answer 2

Une grande explication de l'algorithme peut être trouvé dans http://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution

Remarquez comment le code est presque une ligne à la ligne mise en œuvre de cet algorithme

Answer 3

L'ordre des tours est changé parce que les deux étapes récursives ont objectifs différents. Pour l'un d'entre eux, le but est de "déplacer la pile entière de la tour A à la tour C" (objectif # 1). Pour l'autre, le but est de "déplacer l'anneau inférieur de la tour A à la tour C en mettant tous les autres anneaux sur la tour B" (objectif # 2).

Il est probablement plus facile à comprendre si vous regardez un exemple avec 3 anneaux. Au départ, nous avons:

A (3)(2)(1) 
B 
C 

Nous voulons déplacer les anneaux de A à C, mais pour ce faire, nous devons d'abord mettre l'anneau inférieur sur C, nous commençons donc avec l'objectif n ° 2. Dans objectif n ° 2, nous devons déplacer tous les autres anneaux sur B, donc quand entrer dans ce que nous obtenons objectif # 1, mais avec la tour de destination a changé B. Une fois fait, nous obtenons:

A 
B (2)(1) 
C (3) 

Maintenant, nous avons le but # 1 de B à C. Mais pour ce faire, nous avons d'abord le but # 2 de B à C (qui est essentiellement l'objectif # 1 de B à A). Donc, fondamentalement, la tour de destination change parce qu'à chaque étape récursive, nous passons du but n ° 1 au but n ° 2.