Haskell编程解决九连环1-数学建模

摘要

本文是该系列文章中的第一篇。将对中国传统的智力玩具九连环做简要的介绍。并从数学的角度对其建模。所谓建模就是在定义的基础之上罗列一系列的可证明的定理和推论，从而为该问题的解决建立坚实的理论基础。该理论基础将在本系列的后续文章中作为编程实现的指导和基础。

缘起

记得在完成学业，开始工作后不久，偶尔在路边摊上看到九连环，喜欢并买了回来。很快发现其背后是一个纯粹干净的递归，于是可以熟练的解开并安装还原。彼时也不曾写成电脑程序。要写的话也多半是 C /C++/Java/Python 这类命令式编程语言，简洁明了，没有多少难度，也没有什么激动人心之处。后来东西丢了，也就多年没再玩过。前段时间十一岁的儿子在网上为自己淘来一个，居然也能熟练地拆装，这多少令我有些惊讶。于是想着是否可以乘此机会教教他电脑编程。不成想思考的时候头脑里出现的都是这几年努力学习的 Haskell，发现 Haskell 跟数学是如此的接近，也一如数学一般优美。奈何小家伙不肯学习这个，随他去吧，也许缘分未到呢。好歹把想明白的东西记录成文，万一将来有机会，有缘分，至少不需要从头做起。

定义

九连环的综合信息可以参见维基百科中的条目。一些图片如下，依次是完整未解的，解到一半的和完全解开为两部分的九连环：

可以看到：

• 九连环由两个部分组成，一个“U”型的长剑。另一部分是九个通过直杆连在一起的圆环。
• 长剑的“U”型的弯曲顶端叫做“刀口”，所有的圆环都必须从刀口装上或取下。
• 长剑的另一端“U”型的双尾被连接在一起，称为“手柄”。圆环不能通过手柄端安装或者拆卸。故而在安装或是拆卸九连环的整个过程中“手柄”都可以作为握持的部位，不需要放开。
• 在完全装好时，我们指定最靠近“刀口”的圆环为第 1 环，依次是第 2 环，第 3 环，直至第 9 环。

• 定义问题“拆卸 n 连环”为：当第 1,2, .. ,n 环均处于装上状态时，通过最少的步骤使第 1,2, .. ,n 环均转变为拆下的状态，记为 takeOff(n)。
• 定义问题“装上 n 连环”为：当第 1,2, .. ,n 环均处于拆下状态时，通过最少的步骤使第 1,2, .. ,n 环均转变为装上的状态，记为 putOn(n)。
• 定义在可能（条件许可）的情况下装上或拆下一个圆环（第 n 环）的动作为一个步骤，记作 ON n 或是OFF n。多个步骤的有序排列称为一个步骤序列。

基本操作

基本的操作通过实物演示比较容易理解，如果读者有一个九连环在手，就可以很容易地验证这些操作。

1. 第 1 环在任何时候都可以最少以 1 个步骤被装上或者拆下，记装上的动作为 ON 1，拆下的动作为 OFF 1
2. 如果第 1 环和第 2 环都处于装上的状态，最少用 2 个步骤全部拆卸下来：1)拆下第 2 环 2)拆下第 1 环，步骤序列为 [OFF 2, OFF 1]
3. 如果第 1 环和第 2 环都处于拆下的状态，最少用 2 个步骤全部安装上去：1)安装第 1 环 2)安装第 2 环，步骤序列为 [ON 1, ON 2]
4. 在第 1,2, .. , n – 2 环均处于拆下状态，并且第 n – 1 环处于装上状态时，最少以 1 个步骤安装或拆下第 n 环，该动作为 ON n 或者 OFF n
5. 当 n >1 时，如果第 4 点的前提条件不成立，则第 n 环不能被拆下或装上。这一点很重要，在数学归纳法的基础上可以证明根据第 4 点所提供的没有反复的解法步骤是最少的，从而该方法得到的解才能成为问题 takeOff(n) 或是 putOn(n) 的解

定理与推论

定理 1 ：takeOff(1)的解法步骤序列为 [OFF 1]，putOn(1) 的解法步骤序列为 [ON 1]。
根据基本操作 1，定理 1 显而易见

定理 2 ：takeOff(2)的解法步骤序列为 [OFF 2, OFF 1]，putOn(2) 的解法步骤序列为 [ON 1, ON 2]。
根据基本操作 2 和 3，定理 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)。
定理 3 可以通过数学归纳法证明，其中的起始步骤为定理 1 和定理 2，递推步骤为基本操作 4

推论 1 ：takeOff(n)的解法步骤序列和 putOn(n) 的解法步骤序列互为逆反序列，步骤序列 A 的逆反序列可以通过以下步骤得到: 1) 将序列 A 反序得到序列 A ’ 2) 对 A ’ 中的每个步骤取其反动作，反动作的定义为 ON n 和OFF n互为反动作。可以看出如果 B 是 A 的逆反序列，那么在 B 的基础上取逆反序列，其结果就等于 A。
推论 1 同样可以用数学归纳法证明，当 n<=2 时，通过定理 1 和定理 2 显而易见。当 n>2 时，通过定理 3 提供的步骤可以递推得到。

推论 2 ：takeOff(n)的解法步骤序列和 putOn(n) 的解法步骤序列含有的步骤数目相等。
根据推论 1 和步骤序列的逆反序列定义和算法，推论 2 显而易见。

推论 3 ：对于任何整数 m, n，如果m>n，那么第m 环的状态（装上或是卸下）不影响 takeOff(n) 或者 putOn(n) 的解，同时解决 takeOff(n) 或者 putOn(n) 问题也不会改变第 m 环的状态。
这条推论仍然可以用数学归纳法证明，当 n<=2 时，通过定理 1 和定理 2 显而易见。当 n>2 时，定理 3 提供的步骤不受第 m 环的影响并且不会操作第 m 环。

递归模型

至此我们已经拥有创建一个递归模型所需要的全部理论基础。定理 1 和定理 2 确定了递归结束的基本条件；定理 3 描述了怎样把一个较大的问题拆分成几个较小的问题，从而一步步拆分直至到达递归结束的基本条件；推论 3 事实上明确了我们可以在整个过程中放心地把任何一个较大的问题拆分成多个较小的问题；而推论 1 和推论 2 使得我们在某些情况下能使用等价的替代算法，从而简化编写的实现代码。
下图显示了 takeOff(5) 怎样一步步被拆分成更小的问题，最终达到基本条件的过程。

可以看到该求解过程形成了一颗树，在树中将所有叶结点所包含的动作依次连成一个序列，就是根节点所代表的问题 takeOff(5) 的解法步骤序列。可以看到这个序列是 [OFF 1, OFF 3, ON 1, OFF 2, OFF 1, OFF 5, ON 2, ON 1, OFF 1, ON 3, ON 1, OFF 2, OFF 1, OFF 4, ON 2, ON 1, OFF 1, OFF 3, ON 1, OFF 2, OFF 1]，一共 21 个步骤。
观察解法树的最左侧分支直到末端的叶结点，我们看到通过不断的拆分 takeOff(n) 到takeOff(n-2)再到 takeOff(n-4) 最终到达基本条件 takeOff(1) 或是takeOff(2)，特别地，当 n 为奇数的时候将最终拆分到takeOff(1)，为偶数时将最终拆分到takeOff(2)。这样就得到一个有趣的推论：如果 n 为奇数，则第一步是OFF 1，为偶数时第一步为OFF 2。该推论对于自顶向下地编程实现没有什么特殊的意义，但在实际拆卸九连环的操作中，由于 9 是奇数，记得第一步是OFF 1，也就是拆下第 1 环。