轩辕春秋文化论坛 - Powered by Discuz! Board

标题: 汉诺塔问题 [打印本页]

作者: 周瑜 时间: 2010-9-29 22:25 标题: 汉诺塔问题

汉诺塔问题原题：
有 A、B、C 三根金刚石柱子，B、C 柱子初始为空，在柱子 A 上按大小顺序放着 n 片黄金圆盘。每一块圆盘都比上面那块更大，最下层的圆盘最大而最上层的最小。
现在需要把圆盘按大小顺序重新摆放在另一根柱子 C 上，每次移动只能把某柱子最上层的一个圆盘移动到另一个柱子的圆盘最上层，并且在任何时候所有柱子上的圆盘都满足上小下大的关系。
问需要多少次移动才能把 n 个圆盘都移动到柱子 C 上。

答案：
需要移动 2^(n-1) 次。这是一个递归的过程，需要分三步走：
1. 把上面 n-1 个圆盘从 A 柱移动到 B 柱。
2. 把最大的圆盘从 A 柱移动到 C 柱。
3. 把 B 柱的 n-1 个圆盘从 B 柱移动到 C 柱。
其中1、3两步是少一个圆盘的汉诺塔问题，可以递归求解。

现在的问题是，当移动了 x 步之后 (0 ≤ x ≤ 2^(n-1))， n 个圆盘分别位于哪一个柱子上？

[ 本帖最后由周瑜于 2010-10-4 13:19 编辑 ]

作者: 金圭子 时间: 2010-10-4 20:14

百度不给外连，楼主直接贴论坛图片吧，不过就是个汉诺塔的图示，贴不贴都可以。

既然是个递归问题，还是2底的，那不断除2应该就可以了吧。
比如如果把最上面（最小）的叫做1，最下面（最大）的叫做n。
那如果x<2^n-2，n就在A，x>=2^n-2，n就在C，
同理，x<2^n-3，n-1就在A，2^n-3<=x<2^n-2+2^n-3，n-1就在B，x>=n-2+2^n-3，n-1就在C
……

倒是反过来想的话，需要考虑n的余数问题（一开始觉得是奇数偶数，后来想想也不对，虽然在左右子树中第1个都在动，但是中间正好那下是不动的）……
因为每递归一次，树的左子树中，就相当于B和C交换；树的右子树中，就相当于A和B交换……

作者: 金圭子 时间: 2010-10-4 20:30

还是用观察法吧，先看一下具体数据，以下横行最左面的数字为步数，纵行最上面的数字为圆盘编号：

n=1:
  1
0 A
1 C

n=2:
  1 2
0 A A
1 B A
2 B C
3 C C

n=3:
  1 2 3
0 A A A
1 C A A
2 C B A
3 B B A
4 B B C
5 A B C
6 A C C
7 C C C

n=4:
1 2 3 4
00 A A A A
01 B A A A
02 B C A A
03 C C A A
04 C C B A
05 A C B A
06 A B B A
07 B B B A
08 B B B C
09 C B B C
10 C A B C
11 A A B C
12 A A C C
13 B A C C
14 B C C C
15 C C C C

n=5:
1 2 3 4 5
00 A A A A A
01 C A A A A
02 C B A A A
03 B B A A A
04 B B C A A
05 A B C A A
06 A C C A A
07 C C C A A
08 C C C B A
09 B C C B A
10 B A C B A
11 A A C B A
12 A A B B A
13 C A B B A
14 C B B B A
15 B B B B A
16 B B B B C
17 A B B B C
18 A C B B C
19 C C B B C
20 C C A B C
21 B C A B C
22 B A A B C
23 A A A B C
24 A A A C C
25 C A A C C
26 C B A C C
27 B B A C C
28 B B C C C
29 A B C C C
30 A C C C C
31 C C C C C

从这儿就可以看出，1的位置基本上是2次1换，2的位置4次一换，3的位置8次一换。
在n为偶数的情况下，1是按照A->B->C的顺序来换的，2和1相反，而3和2相反和1相似
在n为奇数的情况下，1是按照A->C->B的顺序来换的，同样2和1相反，而3和2相反和1相似
呃，就是说假设第k个圆盘，在n+k为奇数的情况下，是按照ABC的顺序来换的，在n+k为偶数的情况下，是按照ACB来换的。

另外，前2^k-1（从0到2^(k-1)-1）的一定是A，下面才开始按照这个顺序来换。

于是乎……

我自行假设了以下公式：

假设一共有n个圆盘，一共运行了2^n-1步，第k个圆盘在第x步的情况下是这样的：

第k个圆盘位于A，if x<2^(k-1)
else：

（以下符号"mod"表示取余；符号"\"表示整除，例如c=a\b，即表示c=math.floor(a/b)。另外为了规范下面幂也加括号了，上面的跟着楼主都没加……）
y=((x-2^(k-1)) \ (2^k)) mod 3

或者按照计算机的风格来写就是：
z=math.floor((x-2^(k-1)) / (2^k))
y=z mod 3
括号看不懂的话我按照数学的格式来写：

然后：
如果 x<2^(k-1)，第k个圆盘位于A
否则 y为0，且n+k为奇数时；或y为1，且n+k为偶数时，第k个圆盘位于B
y为1，且n+k为奇数时；或y为0，且n+k为偶数时，第k个圆盘位于C
y为2时候，第k个圆盘位于A

～～～～～～～～～

晕，突然发现前面忘记了x是从0开始的，想去都补个+1，结果突然发现只要把“x<=2^(k-1)”改成“x<2^(k-1)”就可以了（其实是正好和前面整除的-1抵消了），呃，说明前面的公式还是有问题啊，继续验算一次……

[ 本帖最后由金圭子于 2010-10-4 20:56 编辑 ]

作者: 金圭子 时间: 2010-10-4 20:48

以上为经验公式，未得到验证，请自行证明。

以上～

作者: 周瑜 时间: 2010-10-4 22:15

赞圭子的认真态度，不过我得到的公式略有不同。

假设一共有 n 个圆盘，第 k 个圆盘在经过 x 步之后，总共搬动的次数是：
(x+2^(k-1)) \ (2^k)

把三个圆柱标注为 0，1，2，此时该圆盘所在位置为：
y=((x+2^(k-1)) \ (2^k) * (-1)^(n-k+1)) MOD 3

[ 本帖最后由周瑜于 2010-10-4 16:39 编辑 ]

作者: 金圭子 时间: 2010-10-4 23:54

呃，看到那个-1的某次方，总觉得应该差不多，今天要走了，以后有空推导一下是不是一样……

欢迎光临轩辕春秋文化论坛 (http://xycq.org.cn/forum/)