汉诺塔——各种编程范式的解决
版权申明：本文为博主窗户(Colin Cai)原创，欢迎转帖。如要转贴，必须注明原文网址 http://www.cnblogs.com/Colin-Cai/p/7823264.html 作者：窗户 QQ/微信：6679072 E-mail：6679072@qq.com
理解递归，汉诺塔(Tower of Hanoi)是个很适合的工具，不大不小，作为最开始递归的理解正合适。从而学习各种计算机语言乃至各种编程范式的时候，汉诺塔一般都作为前几个递归实现的例子之一，是入门的好材料。
本文从汉诺塔规则出发，讲讲汉诺塔的递归解法以及各种编程范式下汉诺塔的解实现。
汉诺塔介绍
汉诺塔传说是源于印度的古老传说。
汉诺塔游戏一共有三根柱子，第一根柱子上有若干个盘，另外两根柱子上没有盘。
柱子上的盘是按照大小从小到大的排列的，最上面的盘是最小的，越到下面越大。
每一次将任意一根柱子上最上面的一个盘放到另外一根柱子上，但要遵守以下两条：
1.每一次必须移动一个盘
2.大盘不可以压在小盘上面
我们的目标就是反复移动盘，直到把所有的盘从第一根柱子上全部移动到其他的柱子，比如，这里我们就定死，全部移动到第三根柱子，则达到目的。
以上6个盘的移动方法我做了个动画，如下所示：
递归
如果是第一次看到汉诺塔，估计会一下子变的手足无措。
但我们细细的去想想，从简单的开始入手，先看一个盘的情况，这个太简单了，只需要一步即可。
既然是递归，我们就要考虑问题的分解，也就是降阶。
我们考虑n个盘的汉诺塔问题(n>1)。
我们来看，最大的那个盘什么时候才可以移动走呢？因为这是最大的盘，大盘不可以压小盘，所以它移动的前提一定是在其他的盘都在另外一根柱子上，这样可以空出来一根柱子让它移动过去。而同时，它的存在并不影响任何小盘的移动。
于是我们可以把问题分解一下：
当n>1时，我们把n个盘从第一根柱子移动到第三根柱子，可以分为三个步骤：
1.把上面的n-1个盘从第一根柱子移动到第二根柱子
2.把最大的盘从第一根柱子移动到第三根柱子
3.把那n-1个盘从第二根柱子移动到第三根柱子
于是，一个问题就这样被分解为三个小问题，达到了递归的降阶。
用数学归纳法很容易证明上述的移动方法，对于n个盘的移动步数是2n-1
当然，问题本身的形式化，我们用可以用hanoi(n, from, to, buffer)来表示问题，n是盘子的个数，from是盘子初始时所在的柱子，to是盘子最终所在的柱子，buffer是除了from和to的另外一个柱子。
于是用伪码来表示这个递归：
hanoi(n, from, to, buffer):
begin
if n=1
begin
move_disk(from,to)
end
else
begin
hanoi(n-1,from,buffer,to)
hanoi(1,from,to,buffer)
hanoi(n-1,buffer,to,from)
end
end
递归过程动画：
C++实现
C++作为当今世界上最复杂的计算机语言，没有之一，是值得说说的。C++支持过程式编程，同时也支持过程式基础上的面向对象，乃至泛型(其实比起很多语言比如lisp的泛型抽象来说，C++的泛型还是带有底层语言的特征)等。
C++还有实现很好的STL，支持各种常用数据结构，用来做算法描述真的比C语言舒服多了，而且编译后运行效率比C语言差不了多少。这也是为什么很多信息竞赛是用C++答题。
我们每一次移动盘，都会从某一个柱子(源柱)移动到另外一个柱子(目的柱),用源柱号和目的柱号的pair来代表一步，STL里有pair，正好使用，这也是集合论中比较基础的概念。
然后我们用pair串成的list来表示一个汉诺塔问题的解。
#include <list> #include <utility> using namespace std; list<pair<int, int> > hanoi(int n, int from, int to, int buffer) { if(n == 1) { list<pair<int, int> > s; s.push_back(pair<int, int>(from, to)); return s; } list<pair<int, int> > s = hanoi(n-1,from,buffer,to); list<pair<int, int> > s2 = hanoi(1,from,to,buffer); list<pair<int, int> > s3 = hanoi(n-1,buffer,to,from); s.splice(s.end(), s2); s.splice(s.end(), s3); return s; }
这基本就是上面的递归伪码的C++实现，需要注意的是，list的splice方法，是把s2、s3的链表直接搬过来，而不是复制。
Scheme实现
Scheme作为一种Lisp，支持多种范式，最主要当然是函数式编程，采用lambda演算作为其计算手段。Lisp一直是我认为必学的语言。而我心里越来越削弱Common Lisp的地位，觉得Scheme更为纯正，纯就纯在它至简的设计，Common Lisp还要分函数和变量两个名字空间，这时常让我觉得没有真正体现数据和函数一家的意思。
我们还是使用Scheme的实现当然比C++更为简洁一些
(define (hanoi n from to buffer) (if (= n 1) (list (cons from to)) (append (hanoi (- n 1) from buffer to) (hanoi 1 from to buffer) (hanoi (- n 1) buffer to from))))
Prolog实现
Prolog是与C语言同时代的语言，曾经AI的三大学派之一符号学派的产物，当然，Lisp也属于这一学派的产物。
Prolog是明显不同于之前的几种编程语言，它使用的是逻辑范式，使用谓词演算来计算。
hanoi(1,FROM,TO,_,[[FROM,TO]]). hanoi(N,FROM,TO,BUFFER,S) :- N>1, M is N-1, hanoi(M,FROM,BUFFER,TO,S2), hanoi(1,FROM,TO,BUFFER,S3), hanoi(M,BUFFER,TO,FROM,S4), append(S2,S3,S5), append(S5,S4,S).
有点诡异啊，长的和平常习惯的语言很不一样了。
比如这里如果我想查4个盘的汉诺塔，从柱1移到柱3，
?- hanoi(4,1,3,2,S),write(S),!.
[[1,2],[1,3],[2,3],[1,2],[3,1],[3,2],[1,2],[1,3],[2,3],[2,1],[3,1],[2,3],[1,2],[1,3],[2,3]]
改进的递归
我们重新去看看这个递归的伪码
hanoi(n, from, to, buffer):
begin
if n=1
begin
move_disk(from,to)
end
else
begin
hanoi(n-1,from,buffer,to)
hanoi(1,from,to,buffer)
hanoi(n-1,buffer,to,from)
end
end
绿色的hanoi(1,from,to,buffer)自然就是move_disk(from,to)
而两个红色的hanoi(n-1,from,buffer,to)和hanoi(n-1,buffer,to,from)，其实不过是柱号有所偏差,其实只需要解得hanoi(n-1,from,buffer,to)，然后通过from->buffer，buffer->to，to->from这样改变柱号，就得到hanoi(n-1,from,buffer,to)的解。
C++的代码并不难改，只要遍历一把list，每个转换一遍，然后再来合并list就行了。
#include <list> #include <utility> using namespace std; list<pair<int, int> > hanoi(int disks, int from, int to, int buffer) { if(disks == 1) { list<pair<int, int> > s; s.push_back(pair<int, int>(from, to)); return s; } list<pair<int, int> > s = hanoi(disks-1,from,buffer,to); list<pair<int, int> > s2; pair<int, int> x; for(list<pair<int, int> >::iterator i=s.begin();i!=s.end();i++) { if(i->first == from) { x.first = buffer; } else if(i->first == buffer) { x.first = to; } else { x.first = from; } if(i->second == from) { x.second = buffer; } else if(i->second == buffer) { x.second = to; } else { x.second = from; } s2.push_back(x); } s.push_back(pair<int, int>(from, to)); s.splice(s.end(),s2); return s; }
lambda满天飞的Scheme，上述的list转换完全可以用几个lambda来表示，
(define (hanoi disks from to buffer) (if (= disks 1) (list (cons from to)) (let ((s (hanoi (- disks 1) from buffer to))) (append s (list (cons from to)) (map (lambda (x) (let ((f (lambda (y) (cond ((= y from) buffer) ((= y buffer) to) (else from))))) (cons (f (car x)) (f (cdr x))) ) ) s ) ) ) ) )
C++一直是一个大试验田，里面可谓古灵精怪什么都有。其实，C++11也同样引入了lambda，于是C++局部也可以引入函数式编程，我在这里不给出代码，这个就交给有兴趣的读者去完成吧。
Prolog的转化则值得讲一讲,先把hanoi谓词修改了
hanoi(1,FROM,TO,_,[[FROM,TO]]). hanoi(N,FROM,TO,BUFFER,S) :- N>1, M is N-1, hanoi(M,FROM,BUFFER,TO,S2), turn(S2,[[FROM,BUFFER],[BUFFER,TO],[TO,FROM]],S3), append(S2,[[FROM,TO]],S4), append(S4,S3,S).
我在这里加了一个谓词turn，而[[FROM,BUFFER],[BUFFER,TO],[TO,FROM]]代表着转化规则FROM=>BUFFER，BUFFER=>TO，TO=>FROM，通过规则把S2转换成S3。
再举个例子，turn([[1,2],[3,4],[5,9]], [[1,10],[2,20],[3,30],[4,40],[5,50]], [[10,20],[30,40],[50,90]])
因为[[1,10],[2,20],[3,30],[4,40],[5,50]]代表着转换规则1=>10，2=>20，3=>30，4=>40，5=>50
[[1,2],[3,4],[5,9]]里面只有9在转换表里找不到，其他都可以转换，所以最终最右边的这个是 [[10,20],[30,40],[50,90]]
接下来就是如何实现turn，这个需要逐步递归过去。
对于空列，当然转换为空列，
turn([],_,[]).
而对于其他情况，
我们可以先定义一个turn_list谓词，它跟turn谓词很相似，只是，它处理的对象是单个list
比如turn_list([1,2,3], [[1,10],[2,20],[3,30]], [10,20,30]).
于是我们对于普通情况的turn就可以如下定义：
turn([A|B],C,S) :-
turn_list(A,C,D),
turn(B,C,S2),
S = [D|S2].
于是解决turn就转化为turn_list问题，处理的问题规模得到了降阶，这的确是解决递归的真谛啊。
我们在用递归的过程中，就是用尽任何手段来降阶，也就是说解决一个复杂问题转化为解决若干个复杂程度降低的问题。能够理解这一点，这篇文章的目的也就达到了。
turn_list谓词还是太复杂，继续降阶，我们再定义一个谓词turn_one，它只是用来转换单个元素的。
比如turn_one(1, [[1,10]], 10).
于是turn_list的描述则可以如下：
turn_list([],_,[]).
turn_list([A|B],C,S) :-
turn_one(A,C,D),
turn_list(B,C,S2),
S = [D|S2].
而最终，turn_one的实现如下：
turn_one(A,[],A).
turn_one(A,[[A,B]|_],B).
turn_one(A,[[B,_]|D],E) :-
not(A=B),
turn_one(A,D,E).
现实中的玩法
以上讨论递归，虽然可以解决问题，但是似乎并不适合于现实中的汉诺塔游戏，人脑不是计算机，不太适合干递归的事情。
我们稍微修改一下Scheme程序，来观察移动过程中到底移动的是哪个盘，以期待更多的信息，从而发现规律。
我们对所有的盘从小到大从1号开始依次标号。
(define (hanoi disks from to buffer) (if (= (length disks) 1) (list (list from to (car disks))) (append (hanoi (cdr disks) from buffer to) (hanoi (list (car disks)) from to buffer) (hanoi (cdr disks) buffer to from) ) ) ) (for-each (lambda (x) (display (format "柱~a -> 柱~a (盘~a)\n" (car x) (cadr x) (caddr x)))) (hanoi (range (read) 0 -1) 1 3 2) )
对于3个盘的情况，
柱1 -> 柱3 (盘1)
柱1 -> 柱2 (盘2)
柱3 -> 柱2 (盘1)
柱1 -> 柱3 (盘3)
柱2 -> 柱1 (盘1)
柱2 -> 柱3 (盘2)
柱1 -> 柱3 (盘1)
对于4个盘的情况，
柱1 -> 柱2 (盘1)
柱1 -> 柱3 (盘2)
柱2 -> 柱3 (盘1)
柱1 -> 柱2 (盘3)
柱3 -> 柱1 (盘1)
柱3 -> 柱2 (盘2)
柱1 -> 柱2 (盘1)
柱1 -> 柱3 (盘4)
柱2 -> 柱3 (盘1)
柱2 -> 柱1 (盘2)
柱3 -> 柱1 (盘1)
柱2 -> 柱3 (盘3)
柱1 -> 柱2 (盘1)
柱1 -> 柱3 (盘2)
柱2 -> 柱3 (盘1)
我们再继续观察别的数量的盘，
总结一下，我们发现：
1.从第一步开始，奇数步都是移动最小的盘
2.对于奇数个盘的情况， 最小的盘的移动顺序是柱1->柱3->柱2->柱1->柱3->柱2->…
3.对于偶数个盘的情况， 最小的盘的移动顺序是柱1->柱2->柱3->柱1->柱2->柱3->…
4.偶数步的移动发生在最小的盘所在柱子之外的两根柱子之间
对于上述2、3，在于我们的移动目的是想把盘从第一根柱子移动到第三根柱子，如果我们是想把盘从第一根柱子移动到第二根柱子，那么2、3的移动顺序交换。
对于上述4，因为大盘不能压小盘的规则，所以实际的移动方向是固定的，需要临时比较一下从而看出移动方向。
以下的动画可以说明移动过程：
思考
我还是留下几个思考给读者:
1.可不可以证明对于n个盘，上述的2n-1步是最少的移动步数？
2.可以证明“现实中的玩法”的正确性吗？对于“现实中的玩法”，可以用计算机语言实现吗？
3.这个问题有点意思，对于n个从小到大的盘，全部放在3个柱子中任何一个柱子上，每个盘任意放，但要满足大盘不可以压小盘上。这有很多种不同的放法。
比如上图中下面的情况就是6个盘随便给定的一个放法，满足大盘不压小盘。
初始的时候n个盘都在第一根柱子上，可不可以使用汉诺塔的规则一步步移动到某个给定的放法？再进一步，可以编程解决吗？
4.这个问题比较难一点，需要一定的数学推导了。可不可以直接解决step(n,from,to,buffer,m)，表示n个盘的汉诺塔的解的第m步。当然，我要的可不是一步步先算出来，再找出第m步，这个做法不好。