Python3实现汉诺塔问题
Python3实现汉诺塔问题
一、思路
二、Python3代码实现
放一张我自己画的图，里面记录了函数执行的每一步的过程。重点在注意形参和实参的传递问题。
在这里插入图片描述
在这里插入图片描述
三、总结
- 递归函数关键在于归纳总结出规律，确认它是可以递归的，并且找到合适的简单的递归出口。
- 在汉诺塔里面，对于实参和形参的理解很重要，要注意其区别。整个函数的打印过程，可以自己动手一步一步的去画一下，每一步怎么传参，打印的是什么，来帮助理解。
- 汉诺塔游戏是递归调用，在函数调用过程中，栈的问题需要注意，递归函数一层一层的深入调用，但是每调用一层，函数不是马上返回的，而是放在栈中，相应的局部变量也是存在在里面，只有当调用到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次盘子。
四、参考资料
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-08-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录