最短路线问题二

《最短路线问题二》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最短路线这一讲里，我们将会解决这个特殊的计数问题：最短路线问题。怎样计数从A到B的最短路线的条数呢？我们将介绍一种非常巧妙的方法——对角线法（也叫标号法）。例题精讲【例1】咱们先做个游戏：在方格纸上任取一点A作为起点，再在A的右上方任取一点B作为终点划一条由A到B的最短路线。聪明的小朋友，你能划出来吗？总共能划出几条呢？分析：教师可提问如ACIHGFB是最短路线吗？为什么不是？如果要划从A到B的最短路线，那么从A点出发只能向上或向右（每一条都是横划2格竖划2格），可以是ACDEB、ACIEB、ACIFB、AHGFB、AHIEB、AHIFB这六条路线。在上面这个游戏中，

2、你是用什么方法找到从A到B的最短路线呢？如果A、B两点变成图1、2、3的位置，那么从A到B的最短路线有几条呢？分析：图1、2、3中从A到B的最短路线均为6条。小朋友们，你是怎么做的？你发现了什么规律？如果图形变得复杂，还要保证找出的路线既不重又不漏呢？你又该如何解决呢？我们一起来看【例2】。Page8of8【例2】阿呆和阿瓜到少年宫参加2008北京奥运会志愿者培训。请你想一想他们从学校到少年宫的最短路线最多有多少种？分析：我们采用对角线法（如图）从学校到少年宫共有10种走法。我们观察图发现每一个小格右下角上标的数正好是这个小格右上角与左下角的数的和，这个和就是从出发点

3、A到这点的所有最短路线的条数.这样，我们可以通过计算来确定从A→B的最短路线的条数，而且能够保证“不重”也“不漏”。聪明的小朋友，你总结出什么规律了吗？请填在下面的空格内：每个格左上角与右下角所标的数字和即为这格右上角应标的数字.我们称这种方法为对角线法，也叫标号法。例1可以表示如右图(此规律学生版没有，请教师引导学生总结)【例3】下图是动物王国的街道平面图，纵横各有5条路，森林之王老虎先生通知大家去运动场开会，如果迟到就要挨罚喝100杯水。爱睡懒觉的树袋熊一觉醒来，呀，要迟到了，想想那100杯水，树袋熊都快晕了。善良的小朋友们，快来给树袋熊找找最近的吧！分析：教师可

4、参考例1的解答过程，用对角线法（如下图）解，所以共有20条路线。教师可参考。Page8of8【例4】小猫汤姆和老鼠杰克在博物馆看连环画，突然它们发现了一个千年藏宝图，于是它们决定去寻宝。请爱动脑筋的小朋友们帮他们想想共有几条最短路线能到藏宝地呢？分析：教师可参考例1的解答过程，用对角线法（如右上图）解，所以共有126条路线。【例5】下图是小明家和学校的示意图，你们觉得小明从家到学校一共有几条最短路线呢？分析：我们采用对角线法（如图），但本题图形有变化，，例如D点：从学校到C点有2种走法，再到D点最短路线的选择只能从C点走，所以从学校到D点有2种走法。请教师根据学生的理

5、解情况灵活把握，选择几个点讲透彻。从而得到小明可以选择的最短路线共有12条。从而得到小明可以选择的最短路线共有12条。【例6】学校组织三年级的小朋友去帮助农民伯伯锄草，大家从学校乘车出发，去往东南角的李家村（如图）。爱动脑筋的嘟嘟就在想，从学校到李家村共有多少种不同的最短路线呢？　　分析：教师讲解时要注意阶梯形与前几题的不同。我们采用对角线法（如图），从学校到李家村共有126种不同的最短路线。Page8of8【例7】“五一”长假就要到了，小新和爸爸决定去黄山玩。聪明的小朋友请你找找看从北京到黄山的最短路线共有几条呢？分析：我们采用对角线法（如图）这道题的图形与前几题的

6、图形又有所区别，在解题时要格外注意是D、G、K、E、H、L这样的点共有几条最短路线，具体是怎么走的，即由哪两点的数之和来确定另一点的。从北京到黄山最近的道路共有10条。【例8】大熊和美子准备去看望养老院的李奶奶，可是市中心在修路(城市的街道如图所示),他们从学校到养老院最短路线共有几条呢？聪明的小朋友，请你们快想想吧！　分析：（解法1）先假设直接学校到养老院（也就是说可以经过市中心，也可以不经过市中心）对角线法共126条。再减去必经过市中心的60条，即得126-60=66（条）。Page8of8（解法2）可以直接求，即把含有市中心的田字格挖去（或者认为市中心那一点标“

7、0”），共有66条。教师可参考【附5】【附6】附加内容我们这节课重点想让学生学习对角线法，其实最短路线问题还有【附1】【附2】等类型，教师可选讲。【附1】如图，从A到C有4条路可走，哪条路最短？分析：从A到C有可走AEC、ADC、ABC、AC，显然AC这条路最近。（两点之间线段最短）【附2】假如直线AB是一条公路，公路两侧有甲、乙两个村庄。现在要在公路上建一个汽车站，让两个村子的人到汽车站的路线之和最短，问汽车站建在哪？分析：找到甲村关于AB的对称点C，连接C和乙村交AB的那一点即为汽车站。【附3】从X到Y最短路线共有多少种不同的走法？Page8of