汉诺塔问题其实很简单 Python 递归经典面试题
2024-09-21 21:05:17
话不多说,上代码
1 def hanoi_move(n, source, dest, intermediate):
2 if n >= 1: # 递归出口,只剩一个盘子
3 hanoi_move(n-1, source, intermediate, dest)
4 print("Move %s -> %s" % (source, dest))
5 hanoi_move(n-1, intermediate, dest, source)
首先我们这里有三根杆子依次排放,分别是 源杆、媒介杆、目标杆 对应 代码的 source、dest、intermediate,源杆上有n块大饼
我们定义一个函数 def hanoi(n,源杆,目标杆,媒介杆):# 意思是源杆 借助 媒介杆 到 目标杆
我们假设除了底下最后一层上面的n-1层都已经摆放好了,即源杆上目前只有两块大饼,我们要执行的操作是:
源杆上的n-1层 借助 目标杆 到 媒介杆 等同于 hanoi(n-1,源杆,媒介杆,目标杆)相当于n-1层在媒介杆上了
打印 源杆 到 目标杆 显示路径
再把媒介杆的n-1层 借助 源杆 到 目标杆 等同于 hanoi(n-1,媒介杆,目标杆,源杆)
再来说说为什么假设n-1层的,因为我们在假设n-1层的时候使用了递归,在hanoi(n-1…)的时候我们就是假设n-2层已经摆放好了,然后就是在hanoi(n-2…)的时候我们假设n-3层已经摆放好了,不断回溯,就到了最上面一层已经摆放好了,这个假设是合理的,既可以使用该方法。使用了递归的回溯思想,如果使用递归思想不断地推出他的步骤那基本是不可能的,然而通过前提不断地假设反而更容易拿到结果。
最新文章
- 在windows下面配置redis集群遇到的一些坑
- Vijos P1769 网络的关键边
- Linux C 程序 两变量值交换(FIVE)
- STL set multiset map multimap unordered_set unordered_map example
- 讯飞语音SDK Android平台使用
- 十大纺织品、布料、面料品牌排名 - 十大品牌 - 中国品牌网 Chinapp.com
- socket实例1
- externkeyword放到函数体内而导致的linkage问题
- MyBatis Mapper.xml文件中#{selector}和${selector}的区别
- 解决由于VNC日志导致服务器磁盘100%
- Thinkphp5 常量设置问题
- BZOJ 3098: Hash Killer II(新生必做的水题)
- OpenXC : Any updates on plans for IOS?
- oracle 产生随机数
- [转]使用Visual Studio Code开发Asp.Net Core WebApi学习笔记(三)-- Logger
- 在ubuntu 上安装sublime
- PHP -- 页面传值的6种获取方法
- #define NULL ((void *)0)引起的风波
- http://www.cnblogs.com/peida/archive/2013/05/31/3070790.html深入理解Java:SimpleDateFormat安全的时间格式化
- Canvas 动态小球重叠效果
热门文章
- James Munkres Topology: Sec 22 Example 1
- Codeforces 1155F Delivery Oligopoly dp(看题解)
- 022 包含min函数的栈
- android studio 开发免安装的app之目录结构
- 如何用 js 获取虚拟键盘高度?(适用所有平台)
- Metasploit远程调用Nessus出错
- 3dmax 3dmax计算机要求 3dmax下载
- Chrome开发者工具面板
- [POJ1273][USACO4.2]Drainage Ditches (网络流最大流)
- Fio测试工具参数