汉诺塔问题 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4717
编号	1808
注册	2003-11-3
家族	瓦岗寨

发表于 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 编辑 ]

[广告] 真诚支持说岳，携手共创辉煌


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4717
编号	1808
注册	2003-11-3
家族	瓦岗寨

发表于 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 编辑 ]

[广告] 真诚支持说岳，携手共创辉煌