MENU

【代码札记】The Day I Learned Haskell 2

November 22, 2018 • Read: 51 • 瞎折腾

按照上一篇文章中说的,这篇文章将记述 CIS194 Homework1中的第二个练习,三柱和四柱(选做)汉诺塔问题。

三柱汉诺塔

三柱汉诺塔应当说是入门递归的一个经典问题,简单地说就是:

你面前有三根柱子和n个大小不一的碟子,一开始这n个碟子从上到下由小到大依次顺序摞在第一个柱子上,你需要借助第三根柱子把这些碟子移动到第二根柱子上(或者借助第二根柱子移动到第三根柱子上)。其中你需要遵守如下两条规则:

  • 每次只能移动一个盘子
  • 大盘子不能被放在小盘子上

这种问题通常有两种问法,一种是问n个盘子对应最少的操作次数;另一个是操作的顺序。前者很好说,可以从n=1开始列,列出两三个之后就能够找到规律,用数学归纳法得出最小操作数为$2^n - 1$的结论。而后者才算是真正需要用递归完成的。

有关于三柱汉诺塔的视频,我推荐3Blue1Brown的Binary, Hanoi and Sierpinski, part 1Binary, Hanoi, and Sierpinski, part 2。这两个视频虽然不是全部在讲汉诺塔,但是其中有关汉诺塔递归的问题配合视频演示做的非常不错,十分推荐一看。总而言之,要解决n个碟子的三柱汉诺塔问题,应当有如下步骤(此处随题意借助第三根柱子将碟子从第一根挪到第二根):

  1. 将第一根柱子上面的$n-1$个碟子借助第二根柱子挪到第三根上
  2. 将第$n$个碟子从第一根挪到第二根上
  3. 将先前的$n-1$个碟子借助第一根柱子从第三根挪回第二根

在这个练习中,定义如下:

type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]

将String类型用Peg代替,类似C语言中的typedef,同理下面的Move本质上则是(String, String)。这样做的目的是方便阅读和书写程序。
第三行定义的则是主要的函数。这个函数接收一个整数类型和三个Peg类型的参数,整数代表碟子的数量,后面三个Peg代表柱子的名字。最终函数输出一个Move类型的列表,表示操作的顺序。关于变量的解读,应当作如下解释:

假设有代码:hanoi n "a" "b" "c",则应该是“将n个盘子借助ca挪到b”。

接下来是代码:

hanoi3 :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi3 1 a b c = [(a,b)]
hanoi3 n a b c = (hanoi3 (n-1) a c b ) ++ [(a,b)] ++ (hanoi3 (n-1) c b a) 

这里假设三根柱子分别叫做abc。按照前面说的,首先要将$n-1$个碟子借助ba移动到c,然后将第$n$个盘子从a移动到b,再将$n-1$个碟子借助a挪回b
此时需要考虑递归终止的条件。即$n-1$递归到1,只剩下一个碟子时,无需再借助别的柱子,直接移动即可。

在主函数中运行程序:

main :: IO()
main = putStrLn $ show $ hanoi3 2 "a" "b" "c"

输出应当如下:

[("a","c"),("a","b"),("c","b")]

和Homework1中给的样例没有差异。

四柱汉诺塔

四柱汉诺塔和三柱汉诺塔其实差不多,无非是多了一根柱子,可以选择哪一部分挪到第三根柱子,余下的挪到第四根柱子(此处假设还是从第一根挪到第二根)。

这样,就有了如下的思路(假设先保留$x$个盘子不动):

  1. 借助第二、四根柱子将$n-x$个碟子从第一根挪到第三根上
  2. 借助第四根柱子将余下的$x$个碟子从第一根挪到第二根上
  3. 再将上面的$n-x$个碟子借助第一、四根挪回到第二根上

那么问题来了,这$x$是多少?

在指令式编程中可以直接用循环遍历 $\forall x \in [1,n)$ 然后取其中的最小值。同样在Haskell中也可以。定义函数:

hanoi4Helper :: Integer -> Peg -> Peg -> Peg -> Peg -> Integer -> [Move]
hanoi4Helper 1 a b _ _ _ = [(a,b)]
hanoi4Helper n a b c d x = (hanoi4 (n - x) a c b d ) ++ (hanoi3 x a b d) ++ (hanoi4 (n - x) c b a d)

main :: IO ()
main = putStrLn $ show $ minimum $ map (length . hanoi4Helper 15 "a" "b" "c" "d") [1..14]

其中hanoi4Helper定义了一个类似三柱汉诺塔的函数(hanoi3 函数是上面写的三柱汉诺塔函数),只是在一个整数和四个Peg之后额外多了一个整数,这个就是作为待定的$x$。

执行如下的主函数:

main = putStrLn $ show $ minimum $ map (length . hanoi4Helper 15 "a" "b" "c" "d") [1..14]

从右往左看,第一个是map函数,他将一个值到值的函数应用到列表中的每一个数字,通过柯里化将hanoi4Helper和已有的参数15 "a" "b" "c" "d"打包成一个Integer -> [Move]的函数。而括号里还有一个length .这里.表示将右边的函数复合到左边的函数里,类似:$f.g \space x = f(g(x))$的效果。而这里左边的汉诺塔函数被复合到length函数求列表的长度。因此整个括号里面是一个Integer -> Integer的函数,输入待定的x,输出对应的操作数。而被应用的列表正是待定的从1到14(此处n为15)。

随后这个列表又被传给minimum函数,这个函数找出列表中的最小值,之后由更左边的函数输出打印到屏幕上。如果要查看对应x的操作数构成的列表,可以删去minimum $,这样输出的将是一个列表。如果没有差错,最小值输出应该是129。列表是[227,197,169,145,129,145,193,305,545,1049,2065,4105,8197,16385]。可见不同的x对于操作次数的影响还是极大的。

通过谷歌,在这篇文章中提到了对于给定n求x的公式:

$x = \frac {(\sqrt{8*n+1}-1)}{2}$

对应的Haskell代码是:

x = (floor(sqrt(fromIntegral(8 * n + 1))) - 1) `div` 2

因此完善四柱汉诺塔的函数:

hanoi4 :: Integer -> Peg -> Peg -> Peg -> Peg -> [Move]
hanoi4 1 a b _ _ = [(a,b)]
hanoi4 n a b c d = (hanoi4 (n - x) a c b d ) ++ (hanoi3 x a b d) ++ (hanoi4 (n - x) c b a d)
    where x = (floor(sqrt(fromIntegral(8 * n + 1))) - 1) `div` 2

全文完。


知识共享许可协议
【代码札记】The Day I Learned Haskell 2天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://www.skyblond.info/about.html 处获得。

Archives QR Code Tip
QR Code for this page
Tipping QR Code
0:00