Résolution de la Tour de Hanoi II

1. • Je suppose que les règles de base pour déplacer les anneaux sont bien connues.
     
   • Si le nombre d’anneaux est impair, vous n’avez besoin que d’une étape pour placer l’anneau supérieur directement sur le dessus de l’anneau que vous voulez.
     
   • Si c’est égal, il faut deux étapes pour faire le déplacement. Supposons que les chevilles A, B et C de gauche à droite. Si, par exemple, sur B nous avons un tas avec des anneaux 1,2,3,4 et que vous voulez les placer sur l’anneau 5 sur C , la première étape sera 1 à A et 2 à C, et la prochaine, 1 à C.. .et avec un total de 15 mouvements, nous aurons les 1,2,3,4 anneaux de plus de 5 sur la cheville C.
     
   • Dans la mise en page initiale il ya de plus grands anneaux sur le dessus de petits anneaux (c’est la principale différence de la version I de ce jeu), mais quand vous commencez à jouer, vous ne pouvez pas mettre un anneau plus grand sur le dessus d’un plus petit comme dans la tour de Hanoi I.
     
   • Je pense que la meilleure approche pour résoudre le jeu est de commencer par un rapide coup d’oeil aux positions des anneaux 9, 8 et 7. Il est important de voir si l’anneau 9 est déjà sur la base d’une cheville. Et si ce n’est pas le cas, quelle est la meilleure façon est (moins de mouvements) de le mettre là. Dans ce cas, il arrive souvent (surtout si 7 et 8 sont sur des chevilles différentes) que l’on a besoin de placer 7 sur 8 pour avoir une cheville libre pour 9. En outre, nous pouvons avoir à placer 6 sur 9, 7 se déplaçant à la cheville libre après le déplacement 6, puis 6 sur 7 . Le résultat sera un tas de 1 à 7 et le besoin de 127 mouvements supplémentaires pour placer ces 7 anneaux sur le dessus de 8,9 (le nombre minimal de mouvements pour résoudre un jeu dans la tour de Hanoi I situation est: mouvements minimes = 2 ^ n - 1 où n est le nombre d’anneaux de sorte, 3 anneaux auront besoin de 7 mouvements, 4 anneaux auront besoin de 15 ... 7 anneaux auront besoin de 127 et ainsi de suite).
     
   • Quoi qu’il en soit, le but est, avec le nombre minimal de mouvements possibles, de changer la disposition initiale à une tour de Hanoi I situation. Cela signifie que vous saurez toujours à l’avance si le jeu peut être résolu sans avoir à réellement le terminer. Lorsque les anneaux sont dans une tour de Hanoi je situation (un tas dans l’ordre croissant à partir des anneaux 1,2 ... sur une cheville, une cheville libre, et une cheville avec les anneaux restants, également dans l’ordre croissant, la finition sur la base de la cheville où 9 est), il suffit d’ajouter les mouvements déjà faits aux mouvements nécessaires donnés par l’équation ci-dessus et le résultat doit être égal aux mouvements minimaux nécessaires (chaque fois que je fais ce contrôle juste ajouter le dernier chiffre).
     
2. Trois exemples (tous à partir de ce site).
   1. Disposition initiale (145 mouvements minimaux nécessaires)
      
      Cheville A - 1,8,2,9
      Peg B - 7,3
      Peg C - 6,5,4
      
      Étape 1 - La meilleure stratégie est de placer 9 sur la base de la cheville C et 6 sur le dessus de 7 sur la cheville B.
      
      Premier mouvement: anneau 3 sur le dessus de 9 sur A, puis 4 sur le dessus de 7 sur B ...
      
      Après 18 mouvements de la mise en page initiale, nous obtenons:
      
      Peg A - 1
      Peg B - 7,6,5,4,3,2 18 mouvements
      Peg C – 9,8
      
      Étape 2 – Si nous regardons attentivement cette disposition, nous remarquerons que c’est l’équivalent de 6 anneaux sur le dessus de 7 sur B, à condition que le prochain mouvement est de placer l’anneau 1 sur le dessus de 8 sur C. Nous parlons de 6 anneaux (6,5 ... 1 qui est, même, sur la cheville B et 2 étapes sont nécessaires). Donc, pour placer ces six anneaux sur A, nous avons besoin d’un premier mouvement pour placer 1 sur l’autre cheville, dans ce cas C.
      
      Comme nous le savons déjà, pour déplacer 6 anneaux à une autre cheville (cheville A) nous avons besoin de 63 mouvements. Après ces mouvements, il ya un autre à placer 7, maintenant libre, en plus de 9,8.
      Donc, dans cette étape 2 les mouvements seront 63 + 1 = 64 et la mise en page que nous obtenons est:
      
      A - 6,5,4,3,2,1
      B - 63+1 = 64 mouvements
      C - 9,8,7
      
      Jusqu’à présent, nous avons 18 coups sur l’étape 1 plus 64 sur l’étape 2
      
      Étape 3 – La disposition ci-dessus correspond à ce que j’appelle une tour de Hanoi I situation.
      
      Pour terminer le jeu, nous avons besoin de déplacer les 6 anneaux (6,5,... 1) sur la cheville A au sommet de 9,8,7 sur la cheville C. Cela nécessitera 63 autres mouvements.
      
      Total des mouvements = 18 + 64 + 63 = 145 qui est le minimum de mouvements nécessaires.
      
      
   2. Disposition initiale (256 mouvements minimaux nécessaires)
      
      A - 5,3,9
      B - 8,1,6,4
      C - 2,7
      
      Pour placer 9 sur la base, comme 8 et 7 sont sur des chevilles différentes, nous avons besoin de placer 7 sur le dessus de 8 sur B.
      
      Étape 1 - Notre objectif est de placer 9 sur C et 7 sur le dessus de 8 sur B. Pour ce faire, nous avons d’abord besoin de passer 6,4 au sommet de 9 sur A à C gratuit pour recevoir le 9.
      
      Les cinq premiers mouvements sont 4 au-dessus de 7,6 sur le dessus de 9 sur A ,4 à 6,1 à 4 et 7 à 8 sur la cheville B.
      
      Après 20 mouvements, la mise en page sera
      
      A – 5,3
      B – 8,7,6,4,2,1 20 mouvements
      C – 9
      
      Étape 2 place 6 sur 9 sur la cheville C. Pour ce faire, nous avons besoin de 4 sur le dessus de 5 sur A finition cette étape 2 avec 5,4,3,2,1 sur la cheville A . Cela se fait avec 13 mouvements et la mise en page est
      
      A – 5,4,3,2,1
      B – 8, 7 13 coups
      C - 9,6
      
      Étape 3 – Déplacez 5,4...,1 (5 anneaux) vers le haut de 6 sur la cheville C. Cela correspond à 31 mouvements plus 1 à placer 7 sur la cheville A. Ainsi, le nombre de mouvements à l’étape 3 31+1=32 et la mise en page seront
      
      A – 7
      B – 8 32 coups
      C – 9,6,5,4,3,2,1
      
      Étape 4 - Déménagement 6,5,... 1 au sommet de 7 sur la cheville A nécessitera (6 anneaux) 63 coups plus un autre pour mettre 8 sur le dessus de 9 sur C. Total se déplace sur l’étape 4 63+1=64 et la disposition
      
      A – 7,6,5,4,3,2,1
      B - 63+1 = 64 mouvements
      C - 9,8
      
      Étape 5
      
      Nous avons une tour de Hanoi I situation. La dernière étape consiste à déplacer les 7 anneaux de la cheville A
      au sommet de 9,8 sur la cheville C. Cela signifie 127 mouvements.
      
      Total des mouvements- 20 + 13 + 32 + 64 + 127 = 256 mouvements minimes nécessaires.
      
      
   3. Disposition initiale (303 mouvements minimaux nécessaires)
      
      A – 4,9,7,5,8
      B – 6,2
      C – 3,1
      
      Cet exemple est un peu plus difficile que les deux précédents.
      
      Notez que 9 est coincé sur A avec trois anneaux sur le dessus (7,5,8). En outre, B et C ne sont pas des chevilles libres. Il est clair la nécessité de placer le 8,7 sur une cheville libre sinon nous n’aurons pas une cheville libre pour 9.
      
      La meilleure façon de le faire est de placer 8,7 sur la cheville C et passer 6 au sommet de 8,7 sur C.
      
      Après cela est fait Peg B sera libre de recevoir 9. Notez cependant, avant de libérer 7 nous avons besoin de placer 5 sur le dessus de 6 sur B.
      
      Étape 1 - Place 8, sur C et 6,5,3,2,1 sur B
      
      Les sept premiers mouvements sont les suivants :
      2 sur A
      1 sur A
      3 sur le dessus B (au-dessus de 6)
      1 sur C
      2 sur B
      1 sur B
      8 sur C
      
      23 mouvements après le départ, nous obtenons la disposition
      
      A – 4,9
      B – 6,5,3,2,1 23 mouvements
      C – 8,7
      
      Étape 2 – Placez les 6,5,3,2,1 (5 anneaux) sur C au-dessus de 8,7 (la cheville B sera libre de placer le 9).
      
      Déplacer 5 anneaux à une autre cheville nécessite 31 mouvements plus un autre à placer 9 sur B donc, dans cette étape, nous avons besoin de 31 +1 = 32 mouvements .
      
      La mise en page est
      
      A – 4
      B – 9 31+1= 32 mouvements
      C – 8,7,6,5,3,2,1
      
      Étape 3 – Le but est maintenant de libérer la cheville A pour recevoir 7 (sinon nous ne pouvons pas placer 8 sur le dessus de 9). Pour ce faire, il est nécessaire de déplacer 6,5,3,2,1 à B sur le dessus de 9.
      
      Mais comme les mouvements sont alternatifs à la place 6 sur B, nous avons précédemment besoin de placer le 5 sur A et 4 sur B ...
      
      Après 57 mouvements à partir du début sur l’étape 2, nous aurons la disposition suivante.
      
      A – 7
      B – 9,6,5,4,3,2,1 57 mouvements
      C – 8
      
      Il est évident que ces 57 mouvements doivent suivre une logique. En fait, ils peuvent être décomposés sur les actions suivantes
      
      

      Action	Nombre de mouvements
      4 sur B	1
      3,2,1 (3 anneaux) sur le top 4 sur B	7
      5 à A	1
      4,3,2,1 (4 anneaux) à A	15
      6 à B	1
      5,4,3,2,1 (5 anneaux) à B en plus de 6	31
      7 à A	1
      Total	57

      
      
      Étape 4 - déplacer 6,5 .....2,1 (6 anneaux) à A sur le dessus de 7. Cela nécessite 63 mouvements. Maintenant, il est possible de placer 8 sur le dessus de 9 sur B ce qui signifie un mouvement supplémentaire.
      
      Donc, dans cette étape 4 il ya un total de 63 +1 = 64 mouvements
      
      Une fois cela fait, la mise en page est
      
      A – 7,6,5,4,3,2,1
      B – 9,8, 63+1=64 (Situation de la Tour de Hanoi I)
      C –
      
      Étape 5 – La dernière étape consiste à déplacer 7,6,... 2,1 à la cheville B au sommet de 9,8 .
      
      Pour déplacer 7 anneaux, 127 mouvements seront nécessaires.
      
      Ainsi, les mouvements totaux sont 23+32+57+64+127= 303 mouvements minimes nécessaires

Comment avez-vous réussi à publier des listes imbriquées, des tableaux et des textes soulignés sur les forums ?