4.3递归的应用：汉诺塔与迷宫探索（Python进阶-数据结构与算法）课件

递归的应用：汉诺塔 数据结构与算法（Python版） ❖ 汉诺塔问题是法国数学家Edouard Lucas于 1883年 ，根据传说提出来的。 ❖ 传说在一个印度教寺庙里 ，有3根柱子 ，其中 一根套着64个由小到大的黄金盘片 ，僧侣们 的任务就是要把这一叠黄金盘从一根柱子搬 到另一根 ，但有两个规则： 一次只能搬1个盘子 大盘子不能叠在小盘子上 ❖ 神的旨意说一旦这些盘子完成迁移 寺庙将会坍塌，世界将会毁灭 …… 神的旨意是千真万确的！ 数据结构与算法（Python版） 复杂递归问题：汉诺塔 0 数据结构与算法（Python版） 汉诺塔问题： 3盘片演示 0 数据结构与算法（Python版） 汉诺塔问题： 4盘片演示 0 ❖ 虽然这些黄金盘片跟世界末日有着神秘的 联系 ， 但我们却不必太担心 ， 据计算 ， 要 搬完这64个盘片： 需要的移动次数为264-1 = 18,446,744,073,709,551,615次 如果每秒钟搬动一次，则需要584,942,417,355 （五千亿）年！ ❖ 我们还是从递归三定律来分析河内塔问题 基本结束条件（最小规模问题），如何减小规模 ,调用自身 数据结构与算法（Python版） 汉诺塔问题 0 ❖ 假设我们有5个盘子 ， 穿在1#柱 ， 需要挪 到3#柱 如果能有办法把最上面的一摞4个盘子统统挪到 2#柱，那问题就好解决了： 把剩下的最大号盘子直接从1#柱挪到3#柱 再用同样的办法把2#柱上的那一摞4个盘子挪到 3#柱，就完成了整个移动 3# 数据结构与算法（Python版） 汉诺塔问题：分解为递归形式 0 2# 1# ❖ 接下来问题就是解决4个盘子如何能从1# 挪到2#？ 此时问题规模已经减小！ 同样是想办法把上面的一摞3个盘子挪到3#柱， 把剩下最大号盘子从1#挪到2#柱，再用同样的办 法把一摞3个盘子从3#挪到2#柱 ❖ 一摞3个盘子的挪动也照此： 分为上面一摞2个，和下面最大号盘子 ❖ 那么2个盘子怎么移动？ ❖ 不行 ， 就再分解为1个盘子的移动 数据结构与算法（Python版） 汉诺塔问题：分析 0 ❖ 将盘片塔从开始柱 ， 经由中间柱 ， 移动到 目标柱： 首先将上层N-1个盘片的盘片塔，从开始柱，经 由目标柱，移动到中间柱； 然后将第N个（最大的）盘片，从开始柱，移动 到目标柱； 最后将放置在中间柱的N-1个盘片的盘片塔，经 由开始柱，移动到目标柱。 ❖ 基本结束条件 ， 也就是最小规模问题是： 1个盘片的移动问题 数据结构与算法（Python版） 汉诺塔问题：递归思路 0 ❖ 上面的思路用Python写出来 ， 几乎跟语 言描述一样： 数据结构与算法（Python版） 汉诺塔问题：递归思路 0 数据结构与算法（Python版） 汉诺塔问题：代码 0 ❖ 古希腊克里特岛米诺斯王 牛头人身怪物米诺陶洛斯 童男童女献祭，雅典王子忒修斯 公主，利剑，线团 老国王投海……爱琴海 数据结构与算法（Python版） 探索迷宫：古希腊的迷宫 0 数据结构与算法（Python版） 探索迷宫：圆明园的黄花阵 ❖ 位于圆明园西洋楼景区 0 ❖ 将海龟放在迷宫中间，如何能找到出口 ❖ 首先 ， 我们将整个迷宫的空间（矩形） 分 为行列整齐的方格，区分出墙壁和通道。 给每个方格具有行列位置，并赋予“墙壁 ”、“ 通道 ”的属性 数据结构与算法（Python版） 0 探索迷宫 ❖ 考虑用矩阵方式来实现迷宫数据结构 采用“数据项为字符列表的列表 ”这种两级列表 的方式来保存方格内容 采用不同字符来分别代表“墙壁+ ”、“通道 ” 、“海龟投放点S ” 从一个文本文件 逐行读入迷宫数据 数据结构与算法（Python版） 迷宫的数据结构 0 迷宫的数据结构： Maze Class 数据结构与算法（Python版） 0 保存矩阵 ❖ 读入数据文件成功后 mazelist如下图示意 mazelist[row][col]=='+' 迷宫的数据结构： Maze Class 数据结构与算法（Python版） 0 ❖ 确定了迷宫数据结构之后 ， 我们知道， 对 于海龟来说，其身处某个方格之中 它所能移动的方向，必须是向着通道的方向 如果某个方向是墙壁方格，就要换一个方向移动 数据结构与算法（Python版） 探索迷宫：算法思路 0 ❖ 这样，探索迷宫的递归算法思路如下： 将海龟从原位置向北移动一步，以新位置递归调 用探索迷宫寻找出口； 如果上面的步骤找不到出口，那么将海龟从原位 置向南移动一步，以新位置递归调用探索迷宫； 如果向南还找不到出口，那么将海龟从原位置向 西移动一步，以新位置递归调用探索迷宫； 如果向西还找不到出口，那么将海龟从原位置向 东移动一步，以新位置递归调用探