(
课件网) （义务教育版）五年级 全一册 第26课 寻找最短的路径 学习目标 激趣导入 学习活动 学习探究 思考-讨论 课堂小结 拓展-提升 单元主题 单元主题 单元名称 课名称 核心内容 第七单元 了解更多的算法 第24 课 多人过河巧安排 规划算法的应用，把大问题分解成小问题解决。 第 25 课 有趣的七桥问题 抽取问题中的关键要素并进行简化来解决问题，实现一笔画的判断方法。 第 26 课 寻找最短的路径 把全局问题分解成局部问题解决，寻找最小路径的算法描述。 第 27 课 网页排名有策略 网页排名算法的作用，提升网页价值的意义，网络使用的规范及其存在的风险。 学习目标 激趣导入 【生活情境】 比如在一个陌生的城市里，司机叔叔要开车去一个地方，他打开导航软件，输入起点和终点后，导航软件很快就为他规划出了一条最短的路线。 激趣导入 【想一想】 你们知道导航软件是怎么做到的吗？它背后运用了什么神奇的算法呢？ 学习活动 学习活动 活动1：学习探究 一 学习活动 一、学习探究 有一个街道地图，共有9个地点，路线正好能形成2行2列的网格。其中，每个点可以对应到不同地点。例如，起点是家，终点是学校，中间有超市、体育馆、公园、书店、博物馆等。 每条边上的数代表走这条路需要用的时间，如 3 代表 3 分钟。 这些道路都是单行线，在图上只能从左往右走或者从上往下走，不能反方向走。 思考-讨论 一、学习探究 【试一试】 计算从起点走到终点的最短时间。 学习活动 活动2：用枚举法寻找最短路径 二 学习活动 二、用枚举法寻找最短路径 先来尝试用枚举法遍历所有可能的路径。 A → B → C → F → I 3 + 2 + 2 + 1 = 8 A → B → E → F → I 3 + 1 + 2 + 1 = 7 A → B → E → H → I 3 + 1 + 1 + 3 = 8 A → D → E → F → I 2 + 3 + 2 + 1 = 8 A → D → E → H → I 2 + 3 + 1 + 3 = 9 A → D → G → H → I 2 + 3 + 3 + 3 = 11 学习活动 二、用枚举法寻找最短路径 这样获得的路径是 A→B→E→F→I，用时7分钟。 思考-讨论 一、用枚举法寻找最短路径 【想一想】 这样的解法有没有问题呢？ 思考-讨论 一、用枚举法寻找最短路径 【想一想】 问题比较明显：随着地点的增加，路径的数量会快速地增长，如果人工用这种方法操作，就会很耗费时间，而且容易遗漏路径。 例如，用遍历的方法列举以下路径，你还能完全列举出来吗？ 学习活动 活动3：用分段用时寻找最短路径 三 学习活动 三、用分段用时寻找最短路径 下面把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时。用圆圈中的数表示从起点到该点的最短用时。 学习活动 三、用分段用时寻找最短路径 转变思路后，到一个点的用时最多有两个来源。 一是：上方节点用时 + 上方路径用时 二是：左方节点用时 + 左方路径用时 如果一个点有两个来源，那么选其中用时较少的一个。 学习活动 三、用分段用时寻找最短路径 具体步骤如下： 第 1 步：计算第一个局部，A、B、D、E 四个点。 （1）起点A的用时记为0 （2）B点只能从A点向右，最短路径用时为： 左边A点的用时+A点到B点的用时 可以表示为：A +（A→B）= 0 + 3 = 3 学习活动 三、用分段用时寻找最短路径 （3）D 点只能从 A 点向下，最短路径用时为： A +（A → D）= 0 + 2 = 2 （4）E 点可以从 B 点向下，也可以从 D 点向右，分别表示为： B +（B → E）= 3 + 1 = 4 D +（D → E）= 2 + 3 = 5 选较短的路径用时：B +（B → E）= 3 + 1 = 4 学习活动 三、用分段用时寻找最短路径 第 2 步：计算第二个局部 C 点和 F 点。 （1） C 点只能从 B 点向右，最短路径用时为： B +（B → C）= 3 + 2 = 5 （2）F 点可以从 C 点向下，也可 ... ...
