Python3实现汉诺塔问题
发布时间：2019-08-05 15:33:48编辑：auto阅读（2121）
- 把x上的n-1个盘子借助z，移动到y上
- 把x上最下面的盘子移动到z上
- 最后把y上的n-1个盘子借助x移动到，z上，大功告成
递归出口：n=1时，直接从x移动到z上 - 递归函数关键在于归纳总结出规律，确认它是可以递归的，并且找到合适的简单的递归出口。
- 在汉诺塔里面，对于实参和形参的理解很重要，要注意其区别。整个函数的打印过程，可以自己动手一步一步的去画一下，每一步怎么传参，打印的是什么，来帮助理解。
- 汉诺塔游戏是递归调用，在函数调用过程中，栈的问题需要注意，递归函数一层一层的深入调用，但是每调用一层，函数不是马上返回的，而是放在栈中，相应的局部变量也是存在在里面，只有当调用到n=1时，函数才一个一个返回，n=1时返回了，n=2才可以正确返回，直到n=n时，该函数调用才结束。中间有一个递归函数的返回出问题，都会导致最后的结果出错。
- 汉诺塔游戏的移动次数问题其实是一个很经典的等比数列问题。
假设需要移动的总次数为f(n)，根据之前的分析思路，则有f(n) = f(n-1)+1+f(n-1) 即：f(n)=2f(n)=1。变化一下则：[f(n) + 1 ]= 2 * [f(n-1) + 1]，一个非常经典的以2为等比的等比数列，又因为f(1)=1，所以求得f(n) = 2^n -1。
所以如果有3个盘子，移动的步数就是2^3 - 1 = 7次，你可以去数一下，看看是不是？
再回过头来看hannota(3,‘X’,‘Y’,‘Z’)
hannota(2,‘X’,‘Z’,‘Y’) # 执行这句时会移动2^2 -1 = 3次盘子
hannota(1,‘X’,‘Y’,‘Z’) # 执行这句时会移动 1次盘子
hannota(2,‘Y’,‘X’,‘Z’ ) # 执行这句时会移动2^2 -1 = 3次盘子
所以hannota(3,‘X’,‘Y’,‘Z’)总共移动了3+1+3=7次盘子。
Python3实现汉诺塔问题
一、思路
总结归纳为以下3步：
二、Python3代码实现
# Python3递归实现汉诺塔游戏
def hannota(n,x,y,z): # n是盘子数,x,y,z为形参作为柱子
if n == 1: # 递归出口
print(x,'-->',z)
return # 返回None
else:
hannota(n-1,x,z,y) # 把x上的n-1个盘子借助z，移动到y上
hannota(1,x,y,z) # 把x上最下面的盘子移动到z上
hannota(n-1,y,x,z) # 最后把y上的n-1个盘子借助x移动到，z上，大功告成
hannota(3,'X','Y','Z') # 传递实参进去
放一张我自己画的图，里面记录了函数执行的每一步的过程。重点在注意形参和实参的传递问题。
输出结果：
三、总结
四、参考资料
上一篇： 用python解析xml的几种方法
下一篇： python3，浅谈with的神奇魔法
- openvpn linux客户端使用
47448
- H3C基本命令大全
45729
- openvpn windows客户端使用
36737
- H3C IRF原理及 配置
34265
- Python exit()函数
28921
- openvpn mac客户端使用
25552
- python全系列官方中文文档
24397
- 1.常用turtle功能函数
19573
- python 获取网卡实时流量
19055
- python 获取Linux和Windows硬件信息
17594
- python3-scipy-ndimage平滑
5414°
- python3-scikit-image平滑去噪
6006°
- python3-PIL非线性噪声平滑
5520°
- python3-Scipy-ndimage进行盒核与高斯核平滑比较
5597°
- python3-PIL高斯模糊滤波器平滑
6519°
- python3-PIL基于盒模糊核均值化平滑
5326°
- python3-PIL线性噪声平滑
5335°
- python3-scikit-image直方图匹配
5843°
- python3-scikit-image对比拉伸和直方图均衡化
5815°
- python3-PIL二值化
7116°
- 姓名：Run
- 职业：谜
- 邮箱：383697894@qq.com
- 定位：上海 · 松江
