汉诺塔问题的两种解法(4)

第四节 汉诺塔问题的递归解法——移动所有盘子

上一节我们实现了连续移动两个盘子(数字),现在我们发挥一点儿想象力,将上一节的两个盘子当作一个盘子来处理,从而得出移动3个盘子的过程,代码如图22所示。

图22 连续移动三个盘子(数字)的过程

我们还可以写出连续移动4个盘子的过程,代码如图23的左图所示。在暂停按钮的点击事件中调用该过程,即可执行移动操作。读者不妨测试一下,看看虚实。

图23 连续移动4个盘子的过程

以此类推,我们可以编写出连续移动任意多个盘子的过程,如果盘子数为N,那么连续移动N个盘子的过程,要依赖于移动前N-1个盘子的过程。像这样,对N个对象的操作要依赖于对前N-1个对象的操作,解决这样的问题,需要用到一种叫做“递归”的编程方法,即,在一个过程内部调用这个过程本身。下面我们编写移动N个盘子的过程——移动N,代码如图24所示。

图24 连续移动N个盘子的过程

上述过程里增加了一个参数N,这是至关重要的一步,它的作用有两点:一是借助于N,我们得以描述数量相邻的两组盘子之间的移动规律,也就是在N与N-1之间建立联系,如图24中条件语句中的“否则”分支部分;二是为递归调用提供了一个出口,即当N=0时,退出递归,执行条件语句的“则”分支。为递归程序设置出口,这是使用递归方法的第一要务,否则,程序有可能进入死循环。

在暂停按钮的点击事件中调用移动N过程,参数N为左列表的长度,代码如图25所示。

图25连续移动N个数字

在测试手机上的输入框中输入数字10,然后点击开始按钮,之后再点击暂停按钮,程序的运行结果如图26所示。

图26 测试:连续移动10个数字

这次测试在我的手机上运行了很长时间,我很好奇究竟用了几秒钟,5秒?10秒?还是用程序来测一下吧,代码如图27所示,测试结果如图28所示,竟然耗时24秒!

图27 测量运算时长

图28 运算时长的测试结果——24秒钟

前面提到过移动次数与盘子数n之间的关系,移动次数 =,当n=10时,次数=1023。如果仅仅是1023次四则运算,用时不会超过1秒钟,但是当涉及到列表的操作时(添加、删除列表项),运算量呈几何级数增长,况且递归调用过程中,消耗大量内存来保存局部变量——过程的参数,由此导致的资源及运算力的消耗都是巨大的。

程序写到这里,已经实现了解决汉诺塔问题的目标,不过,心中总有些不甘,希望能够将数字移动的过程呈现出来,于是有了后面的几节。

== 未完待续 ==

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180125G082DR00?refer=cp_1026

扫码关注云+社区