IT Notes‎ > ‎Algorithms‎ > ‎

Hanoi Tower

问题描述。有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
  1. 每次只能移动一个圆盘;
  2. 大盘不能叠在小盘上面。
  3. 提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。
问:如何移?最少要移动多少次?

这个问题源于法国数学家爱德华·卢卡斯杜撰的一个故事:傳說印度某間寺院有三根柱子,上串64个金盤。寺院裡的僧侶依照一個古老的預言,以上述規則移動這些盤子;預言說當這些盤子移動完毕,世界就會滅亡。(注:这个故事本身有点扯,因为河内在越南而不是印度。)

我依照参考资料第2条,实现了一个递归方式的 Java 控制台版本:
    public static void hanoi(int i, String a, String b, String c) { //以 b 为中转, 将 i 个盘子从 a 移动到 c
        if (i == 1) {
            move(a, c); // 直接将 a 移动到 c
        } if (i > 1) {
            hanoi(i-1, a, c, b); // 以 c 为中转, 将 i-1 个盘子从 a 移动到 b
            move(a, c); // 直接将 a 移动到 c, 此时移动的就是最底下的那个盘子
            hanoi(i-1, b, a, c); // 以 a 为中转, 将 i-1 个盘子从 b 移动到 c
        }
    }

    public static void move(String src, String dst) {
        System.out.println(src + " -> " + dst);
    }
完整的代码参考这里(from googlecode).

Python3 可以如此写:
# Hanoi Tower
def hanoi(n, a, b, c):
if n == 1:
print(a, '->', c)
return
move(n - 1, a, c, b)
print(a, '->', c)
move(n -1, b, a, c)

# sample
hanoi(4, 'A', 'B', 'C')

(TODO: 还需要插图并配以分析过程,如果能自己实现一个动画版本就太好了,还需要研究它的非递归版本)

河內塔是數據結構 stack 的一個經典應用。

参考:
  1. 维基百科资料:http://zh.wikipedia.org/zh/%E6%B1%89%E8%AF%BA%E5%A1%94
  2. 东北大学网络资源:http://www.neu.edu.cn/cxsj/case/case11.html
  3. 中文FLEX例子(包含非递归解法):http://blog.minidx.com/2008/01/30/457.html
Comments