经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » 编程经验 » 查看文章
汉诺塔——各种编程范式的解决
来源：cnblogs　　作者：窗户　　时间：2018/11/13 11:59:30　　对本文有异议 
  1. 　　版权申明：本文为博主窗户(Colin Cai)原创，欢迎转帖。如要转贴，必须注明原文网址
  2.  
  3. 　　http://www.cnblogs.com/Colin-Cai/p/7823264.html 
  4.  
  5. 　　作者：窗户
  6.  
  7. 　　QQ/微信：6679072
  8.  
  9. 　　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来表示一个汉诺塔问题的解。　

  1. #include <list>
  2. #include <utility>
  3. using namespace std;
  4. list<pair<int, int> > hanoi(int n, int from, int to, int buffer)
  5. {
  6.         if(n == 1) {
  7.                 list<pair<int, int> > s;
  8.                 s.push_back(pair<int, int>(from, to));
  9.                 return s;
  10.         }
  12.         list<pair<int, int> > s = hanoi(n-1,from,buffer,to);
  13.         list<pair<int, int> > s2 = hanoi(1,from,to,buffer);
  14.         list<pair<int, int> > s3 = hanoi(n-1,buffer,to,from);
  15.         s.splice(s.end(), s2);
  16.         s.splice(s.end(), s3);
  17.         return s;
  18. }

 

　　这基本就是上面的递归伪码的C++实现，需要注意的是，list的splice方法，是把s2、s3的链表直接搬过来，而不是复制。

 

　　Scheme实现

 

　　Scheme作为一种Lisp，支持多种范式，最主要当然是函数式编程，采用lambda演算作为其计算手段。Lisp一直是我认为必学的语言。而我心里越来越削弱Common Lisp的地位，觉得Scheme更为纯正，纯就纯在它至简的设计，Common Lisp还要分函数和变量两个名字空间，这时常让我觉得没有真正体现数据和函数一家的意思。

　　我们还是使用Scheme的实现当然比C++更为简洁一些

  1. (define (hanoi n from to buffer)
  2.  (if (= n 1)
  3.   (list (cons from to))
  4.   (append
  5.    (hanoi (- n 1) from buffer to)
  6.    (hanoi 1 from to buffer)
  7.    (hanoi (- n 1) buffer to from))))

 

　　Prolog实现

 

　　Prolog是与C语言同时代的语言，曾经AI的三大学派之一符号学派的产物，当然，Lisp也属于这一学派的产物。

　　Prolog是明显不同于之前的几种编程语言，它使用的是逻辑范式，使用谓词演算来计算。

  1. hanoi(1,FROM,TO,_,[[FROM,TO]]).
  2. hanoi(N,FROM,TO,BUFFER,S) :-
  3.         N>1,
  4.         M is N-1,
  5.         hanoi(M,FROM,BUFFER,TO,S2),
  6.         hanoi(1,FROM,TO,BUFFER,S3),
  7.         hanoi(M,BUFFER,TO,FROM,S4),
  8.         append(S2,S3,S5),
  9.         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就行了。

  1. #include <list>
  2. #include <utility>
  3. using namespace std;
  4. list<pair<int, int> > hanoi(int disks, int from, int to, int buffer)
  5. {
  6.         if(disks == 1) {
  7.                 list<pair<int, int> > s;
  8.                 s.push_back(pair<int, int>(from, to));
  9.                 return s;
  10.         }
  12.         list<pair<int, int> > s = hanoi(disks-1,from,buffer,to);
  13.         list<pair<int, int> > s2;
  14.         pair<int, int> x;
  15.         for(list<pair<int, int> >::iterator i=s.begin();i!=s.end();i++) {
  16.                 if(i->first == from) {
  17.                         x.first = buffer;
  18.                 } else if(i->first == buffer) {
  19.                         x.first = to;
  20.                 } else {
  21.                         x.first = from;
  22.                 }
  23.                 if(i->second == from) {
  24.                         x.second = buffer;
  25.                 } else if(i->second == buffer) {
  26.                         x.second = to;
  27.                 } else {
  28.                         x.second = from;
  29.                 }
  30.                 s2.push_back(x);
  31.         }
  32.         s.push_back(pair<int, int>(from, to));
  33.         s.splice(s.end(),s2);
  34.         return s;
  35. }

　　

　　lambda满天飞的Scheme，上述的list转换完全可以用几个lambda来表示，　　

  1. (define (hanoi disks from to buffer)
  2.  (if (= disks 1)
  3.   (list (cons from to))
  4.   (let ((s (hanoi (- disks 1) from buffer to)))
  5.    (append
  6.     s
  7.     (list (cons from to))
  8.     (map
  9.      (lambda (x)
  10.       (let ((f (lambda (y) (cond ((= y from) buffer) ((= y buffer) to) (else from)))))
  11.        (cons (f (car x)) (f (cdr x)))
  12.       )
  13.      )
  14.      s
  15.     )
  16.    )
  17.   )
  18.  )
  19. )

　　

　　C++一直是一个大试验田，里面可谓古灵精怪什么都有。其实，C++11也同样引入了lambda，于是C++局部也可以引入函数式编程，我在这里不给出代码，这个就交给有兴趣的读者去完成吧。

 

　　Prolog的转化则值得讲一讲,先把hanoi谓词修改了

  1. hanoi(1,FROM,TO,_,[[FROM,TO]]).
  2. hanoi(N,FROM,TO,BUFFER,S) :-
  3.         N>1,
  4.         M is N-1,
  5.         hanoi(M,FROM,BUFFER,TO,S2),
  6.         turn(S2,[[FROM,BUFFER],[BUFFER,TO],[TO,FROM]],S3),
  7.         append(S2,[[FROM,TO]],S4),
  8.         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号开始依次标号。　

  1. (define (hanoi disks from to buffer)
  2.  (if (= (length disks) 1)
  3.   (list (list from to (car disks)))
  4.   (append
  5.    (hanoi (cdr disks) from buffer to)
  6.    (hanoi (list (car disks)) from to buffer)
  7.    (hanoi (cdr disks) buffer to from)
  8.   )
  9.  )
  10. )
  12. (for-each
  13.  (lambda (x) (display (format "柱~a -> 柱~a (盘~a)\n" (car x) (cadr x) (caddr x))))
  14.  (hanoi (range (read) 0 -1) 1 3 2)
  15. )

 

　　对于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步，这个做法不好。

 　　

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

编程经验热门文章

  • Prometheus监控之SNMP Exporter介绍和数据展现
  • Intel 82599网卡异常挂死原因
  • 腾讯防水墙的分析识别与破解
  • 桌面应用自动化WinAppDriver入门
  • 文档在线预览（三）使用js前端实现word、excel、pdf、ppt 在线预览
  • 「教程」如何下载AcFun网站上的视频、A站视频下载工具
  • 基于Hi3559AV100的SVP(NNIE)开发整体流程
  • GBDT(梯度提升树)scikit-klearn中的参数说明及简汇
  • antd之RangePicker设置默认值方式
  • 决胜经典算法之插入排序

    • 编程经验推荐文章

  • wifi基础(一)：无线电波与WIFI信号干扰、衰减
  • 甲方扔给两个存在包名与类名均相同的Jar包，要在工程中同时使用怎么办？
  • 《花100块做个摸鱼小网站! 》第三篇—热搜表结构设计和热搜数据存储
  • Fluent Editor：一个基于 Quill 2.0 的富文本编辑器，功能强大、开箱即用！
  • 方法的三种调用形式
  • 《花100块做个摸鱼小网站! 》第二篇—后端应用搭建和完成第一个爬虫
  • 《熬夜整理》保姆级系列教程-玩转Wireshark抓包神器教程(4)-再识Wireshark - 北京-宏哥
  • 《软件性能测试分析与调优实践之路》(第2版) 读书笔记（二）总体介绍（下）-真正从性能分析与调优来看性能测试
  • 架构知识点（三）
  • 《花100块做个摸鱼小网站! 》第一篇—买云服务器和初始化环境

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号