#1
5
(由 Microsoft 翻译)
-
- 我假设移动戒指的基本规则是众所周知的。
- 如果环数为奇数，您只需 1 步，就将顶部环直接放在所需的环的顶部。
- 如果是均匀的，则需要两个步骤才能移动。让我们假设从左到右挂钩 A、B 和 C。例如，如果在 B 上，我们有一个带环 1，2，3，4 的堆，并且想要将它们放在 C 上的环 5 上，则第一步是 1 到 A 和 2 到 C，下一步是 1 到 C。.和总共 15 个动作， 我们将有 1， 2， 3， 4 环超过 5 在钉 C 。
- 在最初的布局有较大的戒指顶部较小的戒指（这是这个游戏的第一版的主要区别），但当你开始玩，你不能把一个更大的戒指在一个较小的一个顶部，如在河内塔一。
- 我认为解决游戏的最佳方法是从快速查看 9 号、8 号环和 7 号圈的位置开始。重要的是要看看环 9 是否已经位于挂钩的基座上。如果不是，最好的方法是什么（少移动）把它放在那里。在这种情况下，它经常发生（特别是如果7和8在不同的挂钩），一个人需要放置7超过8有一个自由挂钩9。此外，我们可能需要把6对9，7移动到自由挂钩后移动6，然后6超过7。 结果将是一堆从1到7和需要127个额外的动作，把这7环的顶部8，9（在河内塔一的情况解决游戏的最小数量是：最小移动= 2\n - 1其中n是环的数量，所以，3环将需要7个动作，4环将需要15...7 环将需要 127 等）。
- 无论情况如何，目的是，在可能移动的最小数量的情况下，将初始布局更改为河内一号塔的情况。这意味着你将永远提前知道，如果游戏可以解决，而不必实际完成它。当戒指在河内塔 I 的情况下 （一堆在上升顺序开始与戒指 1， 2...在一个挂钩上，一个自由挂钩，和一个挂钩与剩余的环，也按升序，完成在挂钩的基础，其中9是），只需添加已经作出的动作，由上述方程给出的必要移动，结果应等于所需的最小移动（每当我这样做，控制只是添加最后一个数字）。
- 三个例子（全部来自本网站）。
- 初始布局（需要 145 次最小移动）
佩格 A - 1，8，2，9
佩格 B - 7，3
佩格 C - 6，5，4
步骤 1 - 最好的策略是将 9 放在挂钩 C 的基座上，将 6 放在挂钩 B 的 7 个上面。
第一步是： 环 3 在 A 上 9 的顶部， 然后 4 在 B 上 7...
从 初始布局移动 18 次后，我们得到：
佩格 A - 1
Peg B - 7，6，5，4，3，2 18 移动
佩格 C = 9，8
第 2 步 – 如果我们仔细查看此布局，我们会注意到，这相当于 B 上 7 环的 6 环，前提是下一步是将环 1 放在 C 上的 8 个环的顶部。我们说的是6环（6，5...1，甚至，在挂钩B和2个步骤是必需的）。因此，要将这六个环放在 A 上，我们需要先采取行动，将 1 放在另一个挂钩上，在此例中为 C。
正如我们已经知道的， 要移动 6 环到另一个挂钩 （peg A）， 我们需要 63 个动作。这些移动后，有一个额外的放置7，现在免费，在9，8的顶部。
因此，在此步骤 2 中，移动将是 63 + 1 = 64， 我们得到的布局是：
A - 6，5，4，3，2，1
B - 63×1 × 64 移动
C - 9，8，7
到目前为止， 我们在步骤 1 上有 18 个动作， 第 2 步有 64 个动作
第 3 步 – 上述布局对应于我所说的河内 I 塔的情况。
为了完成比赛，我们需要移动6环（6，5,...1） 在挂钩 A 到 9， 8， 7 的顶部在挂钩 C。 这将需要另外63个动作。
总移动 = 18 = 64 = 63 = 145，这是所需的最小移动。 - 初始布局（需要 256 次最小移动）
A - 5，3，9
B - 8，1，6，4
C - 2，7
要将 9 放在底座上， 因为 8 和 7 在不同的挂钩上， 我们需要在 B 上放置 7 个 8。
第 1 步 - 我们的目标是将 9 放在 C 上，在 B 上放置 7 个。为了达到这个目的，我们首先需要将 6，4 移动到 A 上的 9 的顶部，以释放 C 才能接收 9。
前五个动作是 4 在 7， 6， 除了 9 在 A， 4 到 6， 1 到 4 和 7 到 8 在钉 B。
20 次移动后，布局将
A = 5，3
B = 8，7，6，4，2，1 20 次移动
C = 9
步骤 2 将 6 超过 9 放在挂钩 C 上。为了做到这一点，我们需要4在5顶部的5完成这个步骤2与5，4，3，2，1的钉 A 。这是完成13个动作和布局是
A = 5，4，3，2，1
B = 8， 7 13 移动
C - 9，6
步骤 3 = 将 5，4...，1（5 环）移动到 6 个挂钩 C 的顶部。这对应于 31 个移动加上 1，将 7 放在挂钩 A 上。 因此，步骤 3 31+1=32 中的移动数和布局将
A = 7
B = 8 32 移动
C = 9，6，5，4，3，2，1
第 4 步 - 移动 6，5,...1 到 7 的顶部在挂钩 A 将需要 （6 环） 63 移动加上另一个把 8 放在 9 的顶部 C. 总移动在步骤 4 63 +1 +64 和布局
A = 7，6，5，4，3，2，1
B - 63×1 × 64 移动
C - 9，8
步骤 5
我们有一个河内塔一的情况。最后一步是将 7 环从钉 A 移动
在挂钩 C 上 9，8 的顶部。这意味着 127 个移动。
总移动 - 20 × 13 × 32 × 64 × 127 × 256 最小移动需要。 - 初始布局（需要 303 次最小移动）
A = 4，9，7，5，8
B = 6，2
C = 3，1
此示例比前两个要难一些。
请注意，9 卡在 A 上，顶部有三个环（7，5，8）。此外，B 和 C 不是自由挂钩。很显然， 需要把 8， 7 放在自由挂钩上， 否则我们将没有 9 个自由挂钩。
最好的方法就是把 8，7 放在挂钩 C 上，把 6 移动到 C 上的 8，7 的顶部。
完成之后，Peg B 将免费接收 9。但是请注意，在释放 7 之前，我们需要在 B 上放置 5 个 6。
步骤 1 - 放置 8，在 C 上，在 B 上放置 6，5，3，2，1
前七个动作是：
2 对 A
1 对 A
3 在顶部 B （在 6 的顶部）
1 对 C
2 对 B
1 对 B
8 在 C 上
开始后 23 次移动， 我们得到布局
A = 4，9
B = 6，5，3，2，1 23 次移动
C = 8，7
第 2 步 – 将 6，5，3，1（5 环）放在 C 上，放在 8，7（peg B 将可自由放置 9） 上。
将 5 个环移动到另一个挂钩需要 31 个移动加上另一个移动，以放置 9 个 B，因此，在此步骤中， 我们需要 31+1 +32 移动 。
布局为
A = 4
B = 9 31+1= 32 次移动
C = 8，7，6，5，3，2，1
第 3 步 – 现在的目的是释放挂钩 A 来接收 7 （否则我们不能将 8 放在 9 的顶部） 。要做到这一点，需要将 6，5，3，2，1 移动到 B，在 9 个上面。
但是， 由于移动是交替放置 6 在 B 上， 我们以前需要把 5 放在 A 和 4 在 B...
在 步骤 2 的开始 57 次移动后，我们将具有以下布局。
A = 7
B = 9，6，5，4，3，2，1 57 次移动
C = 8
很明显，这57个动作必须遵循逻辑。事实上，它们可以分解为以下操作
行动 移动数 4 对 B 1 3，2，1 （3 环） 前 4 名 B 7 5 到 A 1 4，3，2，1（4 环）至 A 15 6 到 B 1 5，4，3，2，1（5 环）到 B 顶部 6 31 7 到 A 1 总 57
步骤 4 - 将 6，5...2，1（6 环）移动到顶部 7 的 A。这需要63个动作。 现在，可以将 8 放在 B 上 9 个上面，这意味着额外的移动。
因此，在此步骤 4 中，共有 63+1 = 64 个移动
完成此功能后，布局为
A = 7，6，5，4，3，2，1
B = 9，8，63×1=64（ 河内一号塔的情况）
C |
第 5 步 – 最后一步是移动 7，6,...2，1 到挂钩 B 到顶部 9，8 。
要移动 7 圈，需要 127 个移动。
因此，总移动为 23×32×57×64×127×303 移动 最少
- 初始布局（需要 145 次最小移动）
(原文) Solving Tower of Hanoi II
-
- I assume the basic rules for moving the rings are well known.
- If the number of rings is odd you only need 1 step to place the top ring straight on top of the ring you want.
- If it’s even, there is a need for two steps to make the move. Let’s assume pegs A,B and C from left to right. If, for example, on B we have a pile with rings 1,2,3,4 and want to place them over ring 5 on C , the first step will be 1 to A and 2 to C, and next, 1 to C.. .and with a total of 15 moves we will have the 1,2,3,4 rings over 5 on peg C.
- In the initial layout there are larger rings on top of smaller rings (that’s the main difference from version I of this game) but when you start playing you can’t put a larger ring on top of a smaller one as in Tower of Hanoi I.
- I think the best approach to solve the game is starting with a quick look at the positions of rings 9, 8 and 7. It’ s important to see if ring 9 is already on the base of a peg. And if it isn’t, what the best way is (less moves) to put it there. In this case it often happens (especially if 7 and 8 are on different pegs) that one needs to place 7 over 8 to have a free peg for 9. Moreover we may have to place 6 on 9, 7 moving to the free peg after moving 6 and then 6 over 7 . The result will be a pile from 1 to 7 and the need of 127 additional moves to place these 7 rings on top of 8,9 (the minimal number of moves to solve a game in Tower of Hanoi I situation is : minimal moves = 2^n - 1 where n is the number of rings so, 3 rings will need 7 moves, 4 rings will need 15… 7 rings will need 127 and so on).
- Whatever the case, the purpose is, with the minimal number of moves possible, to change the initial layout to a Tower of Hanoi I situation. This means you will always know in advance if the game can be solved without having to actually finish it. When the rings are in a Tower of Hanoi I situation (a pile in ascending order starting with rings 1,2… on one peg, a free peg, and a peg with the remaining rings, also in ascending order, finishing on the base of the peg where 9 is), just add the moves already made to the necessary moves given by the above equation and the result should be equal to the minimal moves needed (whenever I do that control just add the last digit).
- Three examples (all from this website).
- Initial layout (145 minimal moves needed)
Peg A - 1,8,2,9
Peg B - 7,3
Peg C - 6,5,4
Step 1 - The best strategy is to place 9 on the base of peg C and 6 on top of 7 on peg B.
First move is: ring 3 on top of 9 on A, then 4 on top of 7 on B…
After 18 moves from the initial layout we get:
Peg A - 1
Peg B - 7,6,5,4,3,2 18 moves
Peg C – 9,8
Step 2 – If we look at this layout carefully, we’ll note this is equivalent to 6 rings on top of 7 on B, provided the next move is to place ring 1 on top of 8 on C. We are speaking of 6 rings (6,5 …1 that is, even, on peg B and 2 steps are required). So to place these six rings on A we need a first move to place 1 on the other peg, in this case C.
As we already know, to move 6 rings to another peg (peg A) we need 63 moves. After these moves there is an addtional one to place 7, now free, on top of 9,8.
So, in this Step 2 the moves will be 63 + 1= 64 and the layout we get is:
A - 6,5,4,3,2,1
B - 63+1 = 64 moves
C - 9,8,7
So far, we have 18 moves on Step 1 plus 64 on Step 2
Step 3 – The above layout corresponds to what I call a Tower of Hanoi I situation.
To finish the game we need to move the 6 rings (6,5,…1) on peg A to the top of 9,8,7 on peg C. This will require another 63 moves.
Total moves= 18 + 64 + 63 = 145 which is the minimal moves needed. - Initial layout (256 minimal moves needed)
A - 5,3,9
B - 8,1,6,4
C - 2,7
To place 9 on the base, as 8 and 7 are on different pegs, we need to place 7 on top of 8 on B.
Step 1 - Our goal is to place 9 on C and 7 on top of 8 on B. To achieve this we first need to move 6,4 to the top of 9 on A to free C to receive the 9.
The first five moves are 4 on top of 7,6 on top of 9 on A ,4 to 6,1 to 4 and 7 to 8 on peg B.
After 20 moves the layout will be
A – 5,3
B – 8,7,6,4,2,1 20 moves
C – 9
Step 2 place 6 over 9 on peg C. To achieve this we need 4 on top of 5 on A finishing this Step 2 with 5,4,3,2,1 on peg A . This is done with 13 moves and the layout is
A – 5,4,3,2,1
B – 8, 7 13 moves
C - 9,6
Step 3 – Move 5,4…,1 (5 rings) to the top of 6 on peg C. This corresponds to 31 moves plus 1 to place 7 on peg A. So, the number of moves in Step 3 31+1=32 and the layout will be
A – 7
B – 8 32 moves
C – 9,6,5,4,3,2,1
Step 4 - Moving 6,5,…1 to the top of 7 on peg A will require (6 rings) 63 moves plus another one one to put 8 on top of 9 on C. Total moves on Step 4 63+1=64 and the layout
A – 7,6,5,4,3,2,1
B - 63+1 = 64 moves
C - 9,8
Step 5
We have a Tower of Hanoi I situation. The final step is moving the 7 rings from peg A
to the top of 9,8 on peg C. This means 127 moves.
Total moves- 20 + 13 + 32 + 64 + 127 = 256 minimal moves needed. - Initial layout (303 minimal moves needed)
A – 4,9,7,5,8
B – 6,2
C – 3,1
This example is a bit harder than the previous two.
Note that 9 is stuck on A with three rings on top (7,5,8). Also, B and C are not free pegs. It’s clear the need to place the 8,7 on a free peg otherwise we will not have a free peg for 9.
The best way to do this is to place 8,7 on peg C and move 6 to the top of 8,7 on C.
After this is done Peg B will be free to receive 9. Note however, before freeing 7 we need to place 5 on top of 6 on B.
Step 1 - Place 8, on C and 6,5,3,2,1 on B
The first seven moves are:
2 on A
1 on A
3 on top B (on top of 6)
1 on C
2 on B
1 on B
8 on C
23 moves after the start we get the layout
A – 4,9
B – 6,5,3,2,1 23 moves
C – 8,7
Step 2 – Place the 6,5,3,2,1 (5 rings) on C on top of 8,7 (peg B will be free to place the 9).
Moving 5 rings to another peg requires 31 moves plus another one to place 9 on B so, in this step we need 31+1 =32 moves .
The layout is
A – 4
B – 9 31+1= 32 moves
C – 8,7,6,5,3,2,1
Step 3 – The purpose now is to free peg A to receive 7 (otherwise we can’t place 8 on top of 9). To acheive this it’s needed to move 6,5,3,2,1 to B on top of 9.
But as the moves are alternate to place 6 on B we previously need to place the 5 on A and 4 on B…
After 57 moves from the start on Step 2 we will have the following layout.
A – 7
B – 9,6,5,4,3,2,1 57 moves
C – 8
It’s obvious these 57 moves must follow a logic. In fact they can be decomposed on the following actions
Action Number of moves 4 on B 1 3,2,1 (3 rings) on top 4 on B 7 5 to A 1 4,3,2,1 (4 rings) to A 15 6 to B 1 5,4,3,2,1 (5 rings) to B on top of 6 31 7 to A 1 Total 57
Step 4 - move 6,5…..2,1 (6 rings) to A on top of 7. This needs 63 moves. Now it’s possible to place 8 on top of 9 on B which means an additional move.
So in this Step 4 there is a total of 63+1 = 64 moves
After this is done the layout is
A – 7,6,5,4,3,2,1
B – 9,8, 63+1=64 (Tower of Hanoi I situation)
C –
Step 5 – The final step is to move 7,6,…2,1 to peg B to the top of 9,8 .
To move 7 rings, 127 moves will be needed.
So, the total moves are 23+32+57+64+127= 303 moves minimal moves needed
- Initial layout (145 minimal moves needed)
作者 Slb
2020-02-13 16:10:02
赞
回复