按照上一篇文章中说的，这篇文章将记述 CIS194 Homework1中的第二个练习，三柱和四柱（选做）汉诺塔问题。
三柱汉诺塔
三柱汉诺塔应当说是入门递归的一个经典问题，简单地说就是：
你面前有三根柱子和n个大小不一的碟子，一开始这n个碟子从上到下由小到大依次顺序摞在第一个柱子上，你需要借助第三根柱子把这些碟子移动到第二根柱子上（或者借助第二根柱子移动到第三根柱子上）。其中你需要遵守如下两条规则：
- 每次只能移动一个盘子
- 大盘子不能被放在小盘子上
这种问题通常有两种问法，一种是问n个盘子对应最少的操作次数；另一个是操作的顺序。前者很好说，可以从n=1开始列，列出两三个之后就能够找到规律，用数学归纳法得出最小操作数为$2^n - 1$的结论。而后者才算是真正需要用递归完成的。
有关于三柱汉诺塔的视频，我推荐3Blue1Brown的Binary, Hanoi and Sierpinski, part 1和Binary, Hanoi, and Sierpinski, part 2。这两个视频虽然不是全部在讲汉诺塔，但是其中有关汉诺塔递归的问题配合视频演示做的非常不错，十分推荐一看。总而言之，要解决n个碟子的三柱汉诺塔问题，应当有如下步骤（此处随题意借助第三根柱子将碟子从第一根挪到第二根）：
- 将第一根柱子上面的$n-1$个碟子借助第二根柱子挪到第三根上
- 将第$n$个碟子从第一根挪到第二根上
- 将先前的$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个盘子借助c从a挪到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) 这里假设三根柱子分别叫做a，b，c。按照前面说的，首先要将$n-1$个碟子借助b从a移动到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$个盘子不动）：
- 借助第二、四根柱子将$n-x$个碟子从第一根挪到第三根上
- 借助第四根柱子将余下的$x$个碟子从第一根挪到第二根上
- 再将上面的$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://skyblond.info/about.html 处获得。