什么意思呢,就是要写一个程序把盘子搬动的过程啊给它打印出来。
那么为了让大家明白我们需要写一个什么样的程序。我们先来看一下这个程序的运行过程。
比方说对于刚才的汉诺塔的问题。我们假设啊三根柱子的名字分别
叫做A、B、C。我就可以这样来打印。程序运行起来之后呢,首先提示
请输入盘子的数目。假设说我输入的是4个。那么程序呢就会打印出来
在三根柱子上移动四只盘子的步骤为。
底下每一行就是一个步骤。比方说第一行。
把一个盘子从a移动到b,这是第1步。
第2步呢,把一个盘子从a再移动到c,
那么第3行呢,把一个盘子再从b再移动到c,
然后第4行呢,把一个盘子从a再移动到b,等等等等。每行一个步骤,那么现在需要我们做的,
就是要写一个程序,当用户给出来一个n,我们就把这个步骤,
给它打印出来,这是我们要完成的事情。那现在的问题来了,
怎么去解决呢?那么看上去这个问题还是
有点难,当碰到这样问题的时候啊,
我就想起来,我们刚刚开始c程序设计这个部分的时候,曾经给大家讲过的,
当你面临一个问题的时候啊, 你一定要先去思考这个问题的
解决方案,因为没有解决方案就没有程序。
所以阿,我们先放下程序不说,我们先来考虑
一下解决这个问题的方案。我们先来分析一下这个问题。
还是那句话,既然要分析问题啊,我们就要从最简单的情况开始考虑。
假设说现在只有一个盘子需要我们移动,
那么对于一个盘子的情况实在是太简单了,对不对?我们只要把这一个盘子从
a上面拿起来放到c上面,就ok了,这是一个盘子的情况。
那两个盘子的情况呢,也很简单。比方说, 我要把这两个盘子从a经过b移动到c,
那么应该怎么办啊?很简单,我们可以把a上面的这个小盘子先拿起来,
放到b的上面,然后呢再把底下这个大的盘子移到
c的上面,然后呢再把b上面的这个小盘子,移到c的上面,
这是两个盘子的情况。那么三个盘子的情况呢?
为了把a柱子上面三个盘子通过b柱子移动到c,
我们只能这么做。怎么做呢?把a柱子上面,
上面的两个盘子先移动到b柱子上,
然后a柱子上这个最大的盘子就可以移动了,于是呢我们就把a柱子上的这个
最大的盘子从柱子移动到c柱子,在c柱子上放好以后,
我们再把b柱子上的这两个盘子移动到c柱子上面去,那么这三个盘子就都
被移动到c柱子上了。那有的同学说,那怎么才能把
a柱子上最上面的两个盘子移动到b柱子上呢?
有怎么样才能把b柱子上面的两个盘子一下子移动到c柱子上呢?
我说啊,这个过程一点都不复杂。因为刚刚你已经解决过了。
你看我们在第2步,是不是已经移动过两个盘子啦。
是不是?我们在第2步已经把两个盘子
从a柱子跨越b柱子移动到c柱子上面了。
那么在这,当我们想把两个盘子从a柱子 上面移动到b柱子上面的时候,那我们只需要把
这儿的c柱子当作刚才的b柱子来使就可以了。
所以说阿,当我们要移动三个盘子的时候,我们完全可以把它
化简成以两个盘子的情况,也就是说啊,我们可以
得出来这样一个表示,我们要实现把三个盘子从
a柱子上面通过b柱子移动到c柱子, 那我应该怎么办呢?我完全可以这样来做。
先把a柱子上面的两个盘子 从a柱子上面经过c柱子移动到b柱子上面,
这就是我们刚才所叙述的这第一个过程。然后呢,
我把第三个盘子从a柱子上再移动到c柱子上,
这就对应着我们刚才所进行的第2步。
进行完这两步之后呢,然后再把两个盘子从
b柱子上经过a柱子移动到c柱子上,这就对应着
刚才的第3步。那么通过这样3步,
是不是我就可以把三个盘子从a移动到c啦。
ok,是这样的。通过这个分析我们就可以看到,是不是移动三个盘子的问题
就被简化成了两次移动两个盘子的问题啦。
对于对?那么我再问一下,如果对于四个盘子的情况呢?
那如何移动四个盘子的情况就会被简化成如何移动三个盘子
的情况。然后呢,进而又被简化成你如何移动两个盘子的情况。
这样一步一步下去,当我们有n个盘子的时候,
就被演化成了如何移动n减1个盘子的
情况了。好,那么接下来就来看一下如何移动n个盘子。
这有n个盘子,我们不去管它一共有几个阿。我们假设这一共有n个盘子,
那当我想把这n个盘子从a柱子上面经过
b柱子移动到c柱子上面的时候,
我是怎么来进行的呢? 一样的办法。既然要从a柱子上移动到c柱子上,
于是呢,我就必须要把a柱子上面
除了最底下这个盘子之外的所有其他
盘子先从a柱子移动到b柱子, 先给它从a移动到b。
移动完毕以后呢,第2步,再把a柱子上
最底下的这个盘子给它移动到c柱子,移动到c。
那么这个完成了以后呢,再把b柱子上所有的盘子从b柱子再移动到
c柱子。那完成这个步骤以后呢,那么所有的盘子就都在
c柱子上了。如果我们把刚才的这个整个的这个过程
写下来的话,那么可以表述成这个样子。
如果我们想要实现把n个盘子
从a柱子上经过b柱子移动到c柱子, 那么我们应该这样去做。
先把a柱子上面最上面的n减1个盘子,
从a柱子经过c柱子移动到b柱子,
然后呢,再把a柱子上面剩下的这个盘子,移动到c柱子。
那么移动完以后呢,再把刚刚移到b柱子上的n减1个盘子,
从b柱子经过a柱子移动到c柱子。
那么这样一个描述也就告诉我们,对于想要移动
n个盘子的情况,我们完全可以把它化简成要移动 n减1个盘子的情况。
也就是说阿,当我们有5个盘子的时候,我们就可以
约简成4个盘子的情况,有4个盘子的时候我们就可以约简成有3个盘子的情况。
有3个盘子就可以约简成有两个盘子的情况,那有两个盘子的情况我们就
可解了。那步骤是我们已经知道的。于是整个这个问题就可以解决了。
是不是这样的呀?所以如果把这个
逻辑描述下来呢,我们就可以得到一个这样的程序。
我们来看一下这个程序。 假设阿,有这样一个函数move,它呢表示要把m个盘子从
原始的柱子,这个x呢表示起始的柱子,经过
中间的柱子y移动到最终的柱子z.
有的同学说,哎,你在这为什么不使用abc呢?
因为在移动的过程中啊,哪个柱子是原始的柱子
哪个柱子是最终的柱子,哪个柱子当中间的柱子使用
是一件不断变化的事情。所以说呢,我在这用了3个变量,
把它们当作变量写在函数参数里头。 那么当我们想把m个盘子
从x柱子经过y柱子移动到z柱子的时候,
我们就需要这么去做。先判定一下m是多少.
如果m等于1,也就是说只有一个盘子,那我们就直接把这个盘子从x移动到z,
从原始移动到目标。 如果m不等于1,那我们就把最上面的m减1个盘子
先从原始的起点,经过z,移动到y,
然后呢,我们再把x上面剩下的最后一个盘子从x移动到z,
之后呢,我们再把刚刚移动到y上面去的m减1个盘子从y上面,
经过x,移动到z。就是这样的一个逻辑。
那么有了这样一个逻辑之后,我们再去写程序就变得容易了。我们来看一下这个这个程序。
这个呢,是刚刚我们所定义的move函数,它表示啊,
把m个盘子从与原始的数字x
经过中间的柱子y移动到目标柱子z上面去,
这是它的含义。那么在主函数里头呢,我们输入一个盘子的数目,
然后呢,直接去调用move这个函数,
并且呢,我们去写明每一个柱子的名字。
比方说,我们是把原始的柱子命名为a,把中间的柱子命名为b,
然后呢,把目标柱子命名为c。那么这个调用呢,就表示我要把
n个盘子从a经过b,移动到c,
那么结果会是怎样呢?我们来看一下运行的结果。输入4,
然后呢,它就会打印出来每一步运行的步骤。ok,我们来总结一下。
通过这两个例子,我们可以看到 我们可以利用递归啊,来模拟连续发生的动作。
我们可以通过这种方式阿,来解决问题。那么,当我们想通过这种方式
解决问题的时候我们应该怎么去思考呢?也就说那个方法是什么呢?我们首先来看,
第一,首先你要搞清楚,那么连续发生的动作
它是什么。比方说在第一个例子里头,那个连续发生的动作就是
你需要不断地对十进制数处以2,得到
余数,并且判定商是否等于0。
那么在刚刚我们所讲过的汉诺塔问题中呢,你需要不断的做的动作就是
把m个盘子从原始的柱子x
经过中间的柱子y移动到柱子z,你首先要搞清楚,那些连续发生的动作
是什么。其次呢,在这个基础上,你要搞清楚不同次动作之间的
关系。这个关系是什么?比方说,在进制转换的例子里头,那个关系
就是把商当作下一次你要除的那个
十进制数。 在刚刚我们讲过的汉诺塔的例子里面,那么
不同次动作之间的关系其实就意味着
当我要移动m个盘子的时候,我需要先把m减1个盘子
移动出来,然后呢,再把底下的[盘子从x移动到z,
然后再把刚刚移出来的m减1个盘子从y移动到z。
这就是前一次动作和后一次动作之间的关系是什么。
然后在这个基础上,你还需要确定一点,那就是要确定
边界条件是什么。比方说,再刚才我们的汉诺塔的例子里头,
边界条件就是当m等于1,也就是说只有一个盘子需要移动的时候那就好办了。盘子直接
从x移动到z就可以了。那么搞清楚这3点之后,
我们就可以根据第一点来定义那个函数。
根据第2点来描述递归函数之间的关系,
然后第3点呢,来描述递归推出的边界条件。
于是整个程序你就可以得到了。这就是当我们利用
递归来模拟连续发生的动作这样的一种方式 来解题的时候,我们需要做的一些事情。