Python3实现汉诺塔问题
发布时间：2019-08-05 15:33:48编辑：auto阅读（2586）
- 把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客户端使用
50503
- H3C基本命令大全
49806
- openvpn windows客户端使用
40407
- H3C IRF原理及 配置
37423
- Python exit()函数
31844
- openvpn mac客户端使用
28708
- python全系列官方中文文档
27636
- python 获取网卡实时流量
22420
- 1.常用turtle功能函数
22420
- python 获取Linux和Windows硬件信息
20734
- Python搭建一个RAG系统(分片/检索/召回/重排序/生成)
497°
- Browser-use:智能浏览器自动化(Web-Agent)
1112°
- 使用 LangChain 实现本地 Agent
910°
- 使用 LangChain 构建本地 RAG 应用
843°
- 使用LLaMA-Factory微调大模型的function calling能力
1092°
- 复现一个简单Agent系统
966°
- LLaMA Factory-Lora微调实现声控语音多轮问答对话-1
1582°
- LLaMA Factory微调后的模型合并导出和部署-4
2946°
- LLaMA Factory微调模型的各种参数怎么设置-3
2626°
- LLaMA Factory构建高质量数据集-2
2019°
- 姓名：Run
- 职业：谜
- 邮箱：383697894@qq.com
- 定位：上海 · 松江
