Haskell编程解决九连环2-多少步骤

共计 10305 个字符，预计需要花费 26 分钟才能阅读完成。

在本系列的第一篇文章《Haskell 编程解决九连环（1）— 数学建模》中，我们认识了中国古老的智力玩具九连环。通过罗列一系列的定理和推论建立了完整的递归模型。在本文中我们将通过编写 Python 和 Haskell 的代码来解决关于九连环的第一个问题：拆解九连环最少需要几步？同时将对编码所涉及到的其它问题做进一步的讨论。
维基百科上关于九连环的条目中有拆解 n 连环所需的步数，在本文中我们将要通过编程计算来得到下表中的这些数字，特别的，当 n = 9 时，结果应该是 341.

连环的数目	1	2	3	4	5	6	7	8	9
步数	1	2	5	10	21	42	85	170	341

上一篇文章中我们罗列了一些定理与推论，这些都是建立递归模型的理论基础。这里再次将它们罗列如下，用于指导接下来的编程实现。

定理 1 ：takeOff(1)的解法步骤序列为 [OFF 1]，putOn(1) 的解法步骤序列为 [ON 1]。
定理 2 ：takeOff(2)的解法步骤序列为 [OFF 2, OFF 1]，putOn(2) 的解法步骤序列为 [ON 1, ON 2]。
定理 3 ：当 n>2 时，takeOff(n)的解法由以下步骤组成：1) takeOff(n-2) 2) OFF n 3) putOn(n-2) 4) takeOff(n-1)；而 putOn(n) 由以下步骤组成 1) putOn(n-1) 2) takeOff(n-2) 3) ON n 4) putOn(n-2)。
推论 1 ：takeOff(n)的解法步骤序列和 putOn(n) 的解法步骤序列互为逆反序列。
推论 2 ：takeOff(n)的解法步骤序列和 putOn(n) 的解法步骤序列含有的步骤数目相等。
推论 3 ：对于任何整数 m, n，如果m>n，那么第m 环的状态（装上或是卸下）不影响 takeOff(n) 或者 putOn(n) 的解，同时解决 takeOff(n) 或者 putOn(n) 问题也不会改变第 m 环的状态。

相信大多数的程序员小伙伴看到这里，已经能用自己擅长的编程语言编码实现了，在此之前让我们再次明确这些定理和推论在递归模型中的作用。

定理 1 和定理 2 确定了递归结束的基本条件
定理 3 描述了怎样把一个较大的问题拆分成几个较小的问题，从而一步步拆分直至到达递归结束的基本条件
推论 3 事实上明确了我们可以在整个过程中放心地把任何一个较大的问题拆分成多个较小的问题
推论 1 和推论 2 使得我们在某些情况下能使用等价的替代算法，从而简化程序代码。

让我们先从一个命令式语言的实现开始。

def solve(n):        # (1)
    if n == 1:       # (2)
        return 1
    elif n == 2:     # (3)
        return 2
    else:
        return 2 * solve (n - 2) + solve (n - 1) + 1  # (4)

Python 的实现简单明了，解释一下代码，序号均在代码中以注释的形式标注。

根据推论 2，既然我们我们只关心步骤的数量，就不再需要区分 takeOff 或是putOn，统一使用resolve
定理 1 所描述的基本条件，拆卸 1 连环仅需 1 步
定理 2 所描述的基本条件，拆卸 2 连环需要 2 步
根据定理 3 把较大的问题拆分成较小尺寸的同样问题，注意那个 2 * solve (n - 2)，乘以 2 是因为takeOff(n-2) 跟putOn(n-2)的步数相等（推论 2）

可以在 Python 的交互式环境中测试该函数，结果应该如下（省略部分输出）：

>>> def solve(n):        # (1)
...     if n == 1:       # (2)
...         return 1
...     elif n == 2:     # (3)
...         return 2
...     else:
...         return 2 * solve (n - 2) + solve (n - 1) + 1  # (4)
...
>>> solve(1)
1
>>> solve(2)
2
>>> solve(3)
5

......

>>> solve(8)
170
>>> solve(9)
341
>>>

欧耶！结果完全符合预期。且慢，这个实现有个严重的性能问题，如果我们试图计算一下更多环数的答案，就会发现当 n 大到一定程度后会变得很慢，而且随着 n 的增大，性能急剧下降：

>>> import timeit
>>> timeit.timeit (lambda:print(solve(30)), number=1)
715827882
0.4117885000014212
>>> timeit.timeit (lambda:print(solve(35)), number=1)
22906492245
4.801825900009135
>>> timeit.timeit (lambda:print(solve(40)), number=1)
733007751850
54.261840500024846
>>> timeit.timeit (lambda:print(solve(50)), number=1)

我们使用 timeit 给出运行所花费的时间，可以看到在笔者的笔记本电脑上，solve(30)还耗时不到 1 秒，而 solve(40) 就几乎是 1 分钟了，而 solve(50) 已经不能在合理的时间内给出答案了。这是为什么呢？仔细观察递归算法或是画一棵关于求解的示意树就可以看到对于同样的参数我们重复计算了很多次。例如计算 solve(9) 的时候会计算 solve(7) 和solve(8)，而在计算 solve(8) 的时候又会计算一遍 solve(7)，虽然每次计算出的solve(7) 事实上有着完全相同的结果，而在代码实现里仍然必须不断拆分每个问题或子问题问题直至满足基本条件。这样该算法就有着指数级别的时间复杂度，也就是 O(2^n)。
在命令式语言中这个问题很好解决，因为命令式语言允许函数改变全局的状态，也就是允许函数有副作用。思路是创建一个所有函数调用都能够访问的记录表，记下我们已经计算过的结果，在每次函数调用时首先在记录表中查找是否已经有了记录，如果找到就直接返回，否则计算出结果，将其放入记录表中备查并返回。由于在这里只有一个正整数的参数，我们可以选用数组（C/C++/Java，Python 中叫做 list/ 列表）或是一个 map（C++/Java，在 Python 中与 map 对应的数据结构叫 Dictionary）来作为记录表的实现。相信程序员小伙伴们都能轻松地写出代码。在 Python 中甚至有现成的实现functools.lru_cache，这是一个函数装饰器（Decorator）。使用该装饰器不用对原有函数做任何改动，只需要在函数定义前加上一行装饰器的声明就可以了。让我们在 Python 的交互式环境中试试：

>>> import functools
>>> @functools.lru_cache(maxsize=None, typed=False)
... def solve(n):        # (1)
...     if n == 1:       # (2)
...         return 1
...     elif n == 2:     # (3)
...         return 2
...     else:
...         return 2 * solve (n - 2) + solve (n - 1) + 1  # (4)
...
>>> import timeit
>>> timeit.timeit (lambda:print(solve(35)), number=1)
22906492245
0.00022929999977350235
>>> timeit.timeit (lambda:print(solve(40)), number=1)
733007751850
0.0006354999495670199
>>> timeit.timeit (lambda:print(solve(50)), number=1)
750599937895082
0.0007113000028766692
>>> timeit.timeit (lambda:print(solve(200)), number=1)
1071292029505993517027974728227441735014801995855195223534250
0.0006146999658085406
>>>

现在我们能在 1 毫秒内计算出拆卸 200 连环所需要的步数，那是一个相当大的数。假如我们平均需要 1 秒钟来完成一个步骤的话，那么该数字大概是 1071292029505993517027974728227441735014801995855195223534250/60.0/60.0/24.0/365.0 = 3.397044740950005e+52 年，几乎 3.4 万亿亿亿亿亿啊就亿（这里有 6 个亿）年。

我们可以用同样的算法和思路来编写 Haskell 实现：

solve :: Int -> Integer    -- (1)
solve 1 = 1                    -- (2)
solve 2 = 2                    -- (3)
solve n = 2 * solve (n - 2) + solve (n - 1) + 1  -- (4)

沿着在注释中标注的序号，我们来解释一下代码：

在 Haskell 里 Int 类型是由 4 字节或 8 字节表示的有符号整数，是有边界的，我们知道 50 连环或者 200 连环的所需步数将会是一个很大的整数，Int 显然是远远不够用的。所有这里使用了 Integer 作为返回结果的类型，Integer 本身没有大小的限制，它能够表现的最大值只受限于电脑的内存容量。
同 Python 代码解释 2
同 Python 代码解释 3
同 Python 代码解释 4。这里必须使用括号将 n - 2 和n - 1括起来。函数调用在 Haskell 里具有最高的优先级，如果不使用括号，该表达式将等价于 2 * (solve n) - 2 + (solve n) - 1 + 1，这不是我们想要表达的意思，而且将会因为对solve n 的无休止的引用，引起编译 / 解释错误而被拒绝。

这里似乎对于函数 solve 我们有好几个实现，这其实是 Haskell 的一种函数定义方式，叫做模式匹配（Pattern Match）。我们知道在 Haskell 中没有类似 if...then...else 的条件分支语句，如果我们需要对函数的参数做分情形的判断，模式匹配是简明直接的方案（有的时候也会结合另一种叫做哨兵的机制，英文是 Guard），有兴趣的同学可以查阅相关的资料。其实在这里模式匹配的写法更加简洁并且接近数学上定义该函数的方式。使用数学公式，我们通常会有如下的定义：
$$f_{1} = 1$$
$$f_{2} = 2$$
$$f_{n} = 2 * f_{n-2} + f_{n-1} + 1$$
现在让我们在 Haskell 的交互式环境 ghci 中运行测试一下：

Prelude> :{Prelude| solve :: Integer -> Integer    -- (1)
Prelude| solve 1 = 1                    -- (2)
Prelude| solve 2 = 2                    -- (3)
Prelude| solve n = 2 * solve (n - 2) + solve (n - 1) + 1  -- (4)
Prelude| :}
Prelude> solve 1
1
Prelude> solve 2
2
Prelude> solve 3
5
......
Prelude> solve 8
170
Prelude> solve 9
341
Prelude> :set +s
Prelude> solve 30
715827882
(2.59 secs, 375,952,672 bytes)
Prelude> solve 35
22906492245
(32.81 secs, 4,168,814,704 bytes)
Prelude> solve 40
???

可以看到该实现能正确地计算出 1 到 9 环的步数。命令 :set +s 是 ghci 的扩展命令，使得在接下来的任何表达式求值后，ghci 都会输出所用的时间以及内存。明显的是相同的算法在 Haskell 中有着相同的性能问题。而且由于 Haskell 的惰性求值，使得在问题拆分的过程中消耗了大量的内存用于存放中间的表达式。特别的 solve 35 用了 32 秒，以及最大 4GB 内存，而 solve 40 就已经不能在笔者的笔记本电脑上返回了，要么将耗尽电脑的内存，要么将耗尽我们的余生。
既然问题是一样的，是否我们可以使用和 Python 中类似的解决方案呢？答案是肯定的，类似的方案是有，不过由于 Haskell 纯粹（Pure）函数的本质，函数不能访问或改变全局的状态，这些解决方案不像在命令式语言中那样简单和直接。例如：

我们可以把记录表作为函数的参数传入，并且在函数调用后作为返回值的一部分。这样我们不得不小心地在每个函数调用间传递最新的记录表。致使代码相当的晦涩难懂，而且笨重难于修改扩展。
Haskell 中的状态（State）类可以用于处理这种情况。状态类的实现代码本身会很简洁，不过由于 Haskell 的状态事实上是相当高层次的抽象，对于初学者而言理解起来还是有相当的难度。

如果对于如此简单直接的问题我们不得不用或者粗陋或者过于高深的方法来解决的话，那倒真不如不学不用 Haskell 了。幸运的是，Haskell 能够做到简洁高效，甚至更好。那接下来让我们来看一个高效而不失简洁的方法。

如果我们将 n 连环的步数看成一个数列的话，那么只要有两个相邻的数字我们就可以计算出数列中的下一个数字。那我们可以构造这样一个序列，它的每个元素是相邻的两个解组成的数对（Pair），只要得到该序列中的任何一个元素（数对）就可以计算出下一个元素（数对）。这个序列看起来像这样[(1,2), (2,5), (5,10), (10,21), ...]。有了这样一个序列，解开 n 连环的步数就是该序列的第 n 个元素（一个数对）的第一个数值。代码实现如下：

steps :: [(Integer, Integer)]   -- (1)
steps = iterate (\(cur, next) -> (next, cur * 2 + next + 1)) (1, 2)    -- (2)

solve' :: Int -> Integer             -- (3)
solve' n = map fst steps !! (n-1)      -- (4)

照例，让我们沿着注释中的序号解释一下代码：

steps 就是我们打算构造的数对的序列。它可以被理解为一个没有参数的函数，这样的函数在 Haskell 里也被称为一个定义（Definition）。再来看看 steps 的结果类型，事实上也就是 steps 的类型 [(Integer, Integer)]。首先它是一个序列（List，其标志是外层的方括号），而序列中每个元素是一个形如(Integer, Integer) 的元组（Tuple）。在 Haskell 中形如 (a,b,c,..) 的数据结构叫做元组（Tuple），跟 Python 里的 Tuple 比较类似。元组可以是零元，二元，三元直到多元的，而二元元组又被称作值对（Pair），特别的这里的二元元组所包含的值都是整形的数值，我们称之为数对。稍后我们可以在 ghci 中看到 steps 的头几个元素就是[(1,2), (2,5), (5,10), (10,21) ...]。
这一行代码构建了 steps 序列，需要详细说明一下：
- 预定义的函数 iterate 接受一个函数 f 和一个初始值 i，将 i 作为参数喂给 f，然后将结果作为参数再喂给 f，在这个不断重复的过程中将历次得到的计算结果扩展为一个无穷的序列。例如 iterate (+1) 0 就是自然数序列（据说现在的自然数定义包括 0），在 ghci 中求值 take 10 $ iterate (+1) 0 将会输出[0,1,2,3,4,5,6,7,8,9].
- 传给 iterate 作为初始值的值对 (1,2) 会被作为 iterate 结果序列中的第 1 个元素，然后被喂给传入的 lambda 函数，计算结果将作为 iterate 结果序列中的第 2 个元素，以此递推。该初始值就是由 1 连环和 2 连环的步数组成的值对。
- 传给 iterate 的第一个参数是一个 lambda 函数 (\(cur, next) -> (next, cur * 2 + next + 1))，其功能是传入当前值对时，计算出下一值对。请注意它的参数(cur, next) 不是说有两个参数 cur 和 next，实际上这里仅有一个参数，它的类型是值对(Integer, Integer)，这里的语法仍然是模式匹配（Pattern Match），我们通过匹配值对的结构将两个名称（name）cur 和 next 分别绑定（Bind）到传入的值对的两个数值上。名称 cur 和 next 随后可以在 lambda 函数的函数体里被引用。该 lambda 函数的返回值就比较容易理解了，它就是计算出的下一个值对，算法是将当前值对的第 2 个值作为结果值对的第 1 个值，然后根据定义公式计算出下一结果值作为结果值对的第 2 个值。
solve’ 函数是上一节中的 solve 的姊妹版本，有着相同的类型。
map 函数接受一个函数 f 和一个序列，将 f 作用于序列中的每个元素，将所有结果的序列返回作为结果。其作用相当于 C ++ STL 算法库中的 for_each，Java 的 stream.map 以及 Python 中的 map 函数。这里我们传给 map 的函数是 fst，其作用是返回二元元组中的第一个值。我们已经知道 steps 是这样一个序列 [(1,2), (2,5), (5,10), (10,21), ...]，那么map fst steps 就将是这样一个序列 [1, 2, 5, 10 ...]，也就是 n 连环的解法步数的序列，那么它的第 n 个元素就是 n 连环的解的步数了。运算符!! 正是在一个序列中通过给定的索引值 i 取第 i 个元素，注意到 !! 的索引值是从 0 开始的，那么第 n 个元素的索引即是 n -1。

让我们在 ghci 中看看情况：

Prelude> :{Prelude| steps :: [(Integer, Integer)]   -- (1)
Prelude| steps = iterate (\(cur, next) -> (next, cur * 2 + next + 1)) (1, 2)    -- (2)
Prelude|
Prelude| solve' :: Int -> Integer             -- (3)
Prelude| solve' n = map fst steps !! (n-1)      -- (4)
Prelude| :}
Prelude> take 9 steps
[(1,2),(2,5),(5,10),(10,21),(21,42),(42,85),(85,170),(170,341),(341,682)]
Prelude> take 9 $ map fst steps
[1,2,5,10,21,42,85,170,341]
Prelude> solve' 9
341
Prelude> :set +s
Prelude> solve' 200
1071292029505993517027974728227441735014801995855195223534250
(0.03 secs, 194,992 bytes)

这里我们看到 steps 的前 9 个元素组成的子序列为 [(1,2),(2,5),(5,10),(10,21),(21,42),(42,85),(85,170),(170,341),(341,682)]，而map fst steps 的前 9 个元素为 [1,2,5,10,21,42,85,170,341]。请注意 steps 是一个无穷序列，只能通过take n 函数来取得该序列的一个有限子序列并求值打印，否则贸然求值整个 steps 将使 ghci 陷入无穷的计算和输出之中。最后上一节中出现的性能问题也已经得到解决，solve’ 函数花费了 0.03 秒计算出了 200 连环的解法步数，那个熟悉的大数值，转换为时间的话将比太阳系的历史和未来还长。

简洁高效已经有了，说好的优美呢？如果前一节的实现还不够优美的话，那么怎样的代码才可以被称作为优美呢？我们这就来看一个优美而又不失简洁高效的实现方法。这也是笔者迄今为止最喜欢的实现方案。之所以说这个方案优美，是因为它的代码就跟数学定义一样公式化。是的，公式化，就这么简单明确。任何的工程问题，一个有效的解决方案的公式化程度越高，它就越优美，反之亦然。
该方案的思路是构建一个解的序列solutions = [F1, F2, F3, F4 ...]，其中 Fn 的值就是拆卸 n 连环所需要的步数。那么我们知道：

solutions 是一个无穷序列，其中包含的元素是整数。
F1 = 1，F2 = 2
F3 由 F1 和 F2 计算而来，F4 由 F2 和 F3 计算而来 … 一般的当 n>2 时，Fn 由 F(n-2)和 F(n-1)计算而来，而且计算的方法（公式）是固定的。那么我们可以定义一个函数，或者等价的一个操作符⊕，使得当 n>2 时Fn = F(n-2) ⊕ F(n-1)

我们现在设 solutions 的除去头两个元素的子序列 [F3, F4, F5 ...] 为 s，那么s = [F1 ⊕ F2, F2 ⊕ F3, F3 ⊕ F4, ...]。换一种写法s = [F1, F2, F3, ...] Θ [F2, F3, F4, ...] = xs Θ ys。这样我们看到 xs 实际上就是 solutions，而 ys 是 solutions 刨除第 1 个元素 F1 后的子序列。那个操作符 Θ 实际上是这样一个函数，它接受两个序列 xs 和 ys，依次取出两个序列中的对应元素，xs 的第 n 个（设为 x）对 ys 的第 n 个（设为 y），将函数⊕作用于 x 和 y，也就是 x⊕y，所有的计算结果依次组成的序列就是函数 Θ 的结果。现在我们将所有这些都写成 Haskell 代码。请注意以上提到的符号变量是如何对应出现在代码中的。

solutions :: [Integer]
solutions = 1:2:s                          -- (1)

s = zipWith (\x y -> 2 * x + y + 1) xs ys  -- (4)
xs = solutions                             -- (2)
ys = tail solutions                        -- (3)

代码解释如下：

冒号 : 是 Haskell 中列表（List）的值构造符（Value Constructor），可以理解为一个二目操作符，它的第一个参数是一个值，第二个参数是一个列表，:将该值插入到列表的开头作为第一个元素，返回新的包含给定值的列表，例如 1:[1,2] 的结果是 [1,1,2]。事实上我们在代码里经常把列表写成[1,2,3]，这种形式只是语法糖而已，其本质的表示应该是1:2:3:[]。运算符: 是右结合的，，也就是说 1:2:3:[] 等价于 1:(2:(3:[])))。那么这里的代码1:2:s 的结果是这样一个序列，其第 1 个元素为 1，第 2 个元素为 2，从第 3 个元素开始依次是原 s 序列中的元素。根据上面讨论的子序列 s 的定义可以知道 1:2:s 就是完整的 solutions 序列。
根据上面的讨论，设定的序列 xs 就是 solutions 序列。
我们说过 ys 序列就是 solutions 序列刨除第 1 个元素，预定义的函数 tail 正是这样一个函数，它接受一个列表，刨除第一个元素，将剩下的子序列作为结果返回。
这一行代码的内容颇多，我们逐点解释：
- 首先在这里我们没有申明 s 的类型。Haskell 的编译器和解释器有很强的类型推导能力。根据 s 在表达式 (1) 处出现的位置还有 solutions 的类型，Haskell 将推导出 s 的类型也是[Integer]。其实在 Haskell 代码里大部分的类型申明都不是必须的，不过对于不太熟练的 Haskeller 来说，最好还是在关键的函数上放上类型申明，这样可以确保编译器所理解的和我们所设想的一致。
- 这里我们在定义申明前就引用了名称 xs 和 ys，在 Haskell 里由于函数的纯粹性以及名称不可被多次定义，这确保了名称不会有二义性，因此名称或者函数都可以先引用而后定义。事实上 Haskeller 们经常这么做，先把顶层的表达式写出来，然后再详细定义那些局部的函数和名称。这也是 Haskell 经常炫耀的优势，那就是尽量书写让人能看明白的定义，而不是照顾编译器。
- lambda 函数 (\x y -> 2 * x + y + 1) 就是我们上文讨论提到的操作符⊕，也是前几节中将 F(n-2)和 F(n-2)计算成 Fn 的表达式。
- zipWith 是一个预定义的高阶函数。它的第一个参数是一个函数 f，该函数必须接受两个参数。而 zipWith 的第 2 和第 3 个参数都是一个列表，zipWith 依次从两个列表中取出相应的元素喂给函数 f，将所有 f 的输出结果依次所形成的列表作为 zipWith 的结果。可以看到偏函数 zipWith (\x y -> 2 * x + y + 1) 事实上就是上文中提到的处理两个列表的函数 Θ。

现在可以在 ghci 中测试这段代码：

Prelude> :{Prelude| solutions :: [Integer]
Prelude| solutions = 1:2:s                          -- (1)
Prelude|
Prelude| s = zipWith (\x y -> 2 * x + y + 1) xs ys  -- (4)
Prelude| xs = solutions                             -- (2)
Prelude| ys = tail solutions                        -- (3)
Prelude| :}
Prelude> take 9 solutions
[1,2,5,10,21,42,85,170,341]
Prelude> solutions !! 8
341
Prelude> :set +s
Prelude> solutions !! 199
1071292029505993517027974728227441735014801995855195223534250
(0.02 secs, 166,760 bytes)

可以看到该实现同样的高效，0.02 秒计算出拆解 200 连环的步数。
这段代码还可以简化，注意到名称 s，xs，ys 都只被引用过一次，完全可以就地展开而不用单独定义。下面就是简化的版本：

solutions = 1:2:zipWith (\x y -> 2 * x + y + 1) solutions (tail solutions)

solve'' :: Int -> Integer
solve'' n = solutions !! (n-1)

嗯，简洁，高效。优美吗？是的，我觉得相当的优美。

下一篇预告：《Haskell 编程解决九连环（3）— 详细的步骤》

摘要

定理与推论

Python 实现

Haskell 实现（1）

Haskell 实现（2）

Haskell 实现（3）

Just My Socks（注册教程内含优惠码）