python汉诺塔递归

<!DOCTYPE html>

python汉诺塔递归

python汉诺塔递归


图一,画错了,圈圈应该在a上

图二

图三

我们把图三稍微交换一下位置,就变成了图二的状况。


图四

当n=1,就从a移到c。。。函数零(一步)

当n=2,看成两部分,函数一加(n-1其余的)。{先将其余的调到b,再执行函数零,再把其余的调到c}。。。。函数一(1+1+1=3步)

当n=3,看成两部分,最大的和其余的。{先将其余的调到b(也就是函数一的情况),再把最大的调到c(函数0),再把其余的调到c(函数一)}。。。。函数二。(3+1+3=7步)

。。。。这就是递归。

这是思考的部分,因为其余的圈不能一起挪,所以不能将其余的调到b。

操作只能倒着思考的顺序来,不管n等于几,操作到最后,其余的肯定等于1,(因为一次挪一个)就开始。

要执行函数三,就要先执行函数二

而要执行函数二,就要先执行函数一

要执行函数一,就要先执行函数其余到b,再执行函数0,在执行其余到c.

...就是说


我们发现图四和图二其实没什么区别,思考上,都是其余的往空柱子挪,最大的往c挪。




问题一:为什么第7行和第九行的参数分别是a,c,b 以及 b,a,c?

这里的a,c有个位置转换,所以比较难理解,我们表达为位置一,-->,位置三。

第三行abc是初始化的参数。当条件n=1时,有着对应关系是abc,对应的输出就是a-->c。

其中a对应着a,b对应着-->,c对应着c。

当条件不满足时候,move函数的参数对应关系是,a对应a   c对应-->  b对应c

下面代码表示参数对应关系又改变了一次。


比如说将其中一个参数改变了下,当条件为2的时候,满足n-1等于1,于是move函数对应关系是a=a,c='-->',c=to   。。。所以输出a-->to

下一行,表示恒为1,对应关系是a=a,to='-->',c=c输出a-->c

就是这样转换参数的位置,来决定不同的输出。

当n等于3的时候,n-1等于2,因为不等于1,所以第六行不输出,第七行恒输出a-->c,第八行不输出。

再循环,n-1等于2-1,等于1,因为循环一次n减小1。move函数变成了(1,a,c,to)

注意,此时第四行print(a,-->,to)。。。因为对应关系变了




问题二:如何想出move(n-1,a,c,b)....move(n-1,b,a,c)

我们理解了递归,函数一等于(其余搬b加函数0加其余搬c)



所以我们将move函数的参数换一下位置,就得到了函数一的结果。