用haskell实现汉诺塔

发表于 更新于 阅读次数：

汉诺塔问题是一个经典的递归问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

haskell三行源码解决问题:

1
2
3
4
hanoi::[Char]->[Char]->[Char]->Int->[[Char]]
hanoi _ _ _ 0 = []
hanoi from middle too n = (hanoi from too middle (n-1)) ++ [from ++ "->" ++ too] ++ (hanoi middle from too (n-1))
-- 调用 hanoi "1" "2" "3" 5 (假设5个金片，3根柱子的名字就叫 1 2 3)

done!

别试原题64个金片啊，用一个C语言的程序试了一下，把结果写到文件里，运行了几十秒也不见结束，赶紧停止，一看生成的半截文件已经好几百兆了。

那么64个金片到底是多少步呢? 我们重新写个函数算一下:

1
2
3
4
5
6
7
8
hanoiSteps::Integer->Integer
hanoiSteps 0 = 0
hanoiSteps n = 1 + 2*(hanoiSteps (n-1))
-- 计算结果

hanoiSteps 64
18446744073709551615

C语言的源程序也贴出来，比较一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>

void hanoi(int num,int from,int by,int to){
    if(num==0)
        return;
    hanoi(num-1,from,to,by);
    printf("%d-->%d\n",from,to);
    hanoi(num-1,by,from,to);
}

int main(int argc,char *argv[]){
    hanoi(atoi(argv[1]),1,2,3);
}