递归算法之汉诺塔

xiaoxiao2021-02-28  121

之前看鱼C的汇编教程学了一段时间,在调研了各路大神的言论后,毅然决定转学Python了

经过这两周的学习,发现Python果然是适合初学者,函数语法都比较简单易懂,而且能够很快的实现一些小功能,为枯燥的学习过程增添一点乐趣。

今天学习的递归算法,求解经典的汉诺塔的问题,让我第一次感受到了程序的强大之处,之前虽然知道程序可以做什么,但一直不知道具体是如何一步一步实现的,在学习了递归算法求解汉诺塔问题后,才彻彻底底的感受到了程序的牛逼之处,虽然这只是一个简单到不能再简单的小程序,但却仿佛为我打开了一扇大门,通向光明大道。

下边就递归及汉诺塔问题,跟大家交流一下我的看法,不对的地方还请大神们指正!谢谢

首先,我对递归的理解,递归的原理在于,分析问题从结果出发,往前推演,可以通过对参数的改变,将问题分解成一步步的简单步骤来解决,最后由明确的返回值来结束函数。

对于汉诺塔问题:

1、如下图1所示,我们假设一个4级的汉诺塔,目的是将4层塔从X,移动到Z,一次只能移动一层,且只能按顺序放置

----------所以我们先定义一个函数:def hanoi(n,x,y,z)     ####n代表了塔的层数,对于4层汉诺塔n就等于4,x y z分别代表3个轴#######

2、对于这个问题我们如何用递归的思想的理解呢,需要再看下图:

(1)我们需要将第1层塔从X轴  移动到  Z轴;

(2)然而,我们只有将第 2,3,4层塔从X轴移动到Y轴,才可以实现(1)的操作

(3)下一步,我们需要将第2层塔,移动到Z轴的第1层塔上,同样,为了实现这个,我们需要先将第3,4层塔移动到X轴上。其实,在这一步,假如我们忽视第1层塔,单纯的看第2,3,4层塔,就会发现,其实解决步骤和第(2)里描述的是一样的,所以,这就是我们所说的递归的关键:我们就是要将一个复杂的问题,分解为一步步近似重复的简单步骤来解决。

(4)总结一下,对于n层的汉诺塔,

我们首先将上面的(n-1)层塔移动到Y轴,然后将最下面的一层塔移动到Z轴,就完成了一次操作;

然后我们的对象切换为在已经被移动到Y轴上的那(n-1)层塔,此时需要将上面的(n-2)层塔移动到X轴(注意,这次是拿X轴作为中转),然后将剩下的那一层移动到Z轴,Z轴上就有2层塔了,依次类推,直到所有层塔都移动到Z轴。

(5)因此,我们按照这个规律,就可以写出完整的程序,其中涉及函数的重复调用:

-----------------def hanoi (n,x,y,z):                      #----n代表了塔的层数,对于4层汉诺塔n就等于4,x y z分别代表3个轴-----#

----------------- if n == 1:

----------------- print (‘x"-->"z')           #---- 当只有1层汉诺塔时,我们只需要将其从X-->Z,这也将是我们程序最后正确返回的保障----#

----------------- if n > 1:

----------------- hanoi (n-1,x,z,y)         #----首先将(n-1)层塔,从X轴移动到Y轴,这里看参数中的x,y,z变为了x,z,y

----------------- print (‘x"-->"z')             #----然后将剩下的1层塔,从X轴移动到Y轴,这里是将我们的操作步骤输出

----------------- hanoi (n-1,y,x,z)         #----最后,将Y轴上的(n-1)层移动到Z轴上

-------------------------------------------###END------------------------------------------------------------

这里我觉得有几个点比较难于理解且容易造成混乱的是:

1、函数的4个参数中的(n,x,y,z),n代表的本次函数的对象塔的层数没什么问题,后面的三个参数(x,y,z)在后来的两次调用n-1时,位置发生了改变是为什么?这是一个难以理解的地方,那么我们改怎么理解呢?

第1个参数:n----塔的层数

第2个参数:x-----初始位置

第3个参数:y-----中转位置

第4个参数:z-----目标位置

不管x,y,z也好,y,z,x也好,a,b,c也好,他们所处的参数位置,就是他们的意义,这么去理解可能要好一点。

希望对大家有所帮忙,也希望大神对于其中理解不对的地方予以指正。

转载请注明原文地址: https://www.6miu.com/read-65060.html

最新回复(0)