三年级奥数金典讲义-第四讲 最短路线问题 通用版(含答案)
区域地理-灵巧的近义词是什么
第四讲
最短路线问题
在日常工作、生活和娱
乐中，经常会遇到有关行程路线的问题
.
在这一讲里，我们主要
解决的问题是如何确定从某处到另一处最短路线的条数。
例
1
下图<
/p>
4
—
1
中的线段
表示的是汽车所能经过的所有马路，
这辆汽车从
A
走到
B
处共有多
少条最短路
线？
分析
为了叙述方便，
我们在各交叉点都标上字母
.
如图
4
—
2.
在这里，
首
先我们应该明
确从
A
到
B
的最短路线到底有多长？从
A
点走到
B
点，
不论怎样走，
最短
也要走长方形
AHBD
的一个长与一个
宽，即
AD
＋
DB.
< br>因此，在水平方向上，所有线段的长度和应等于
AD
；在
竖
直方向上，所有线段的长度和应等于
DB.
< br>这样我们走的这条路线才是最短路线
.
为了保证这
一点，
我们就不应该走
“回头路”
，
即在水平方向上不能向左走，
在竖直方向上不能
向上走
.
因此只能向右和向下走。
有些同学很快找出了从
A
到
B
的所有最短路线，
即：
A
→
C
→
D
→
G
→
B A
→
C
→
F
→
G
→
B
A
→
C
→
F
→
I
→
B A
→
E
→
F
→
G
→
B
A
→
E
→
F
→
I
→
B A
→
E
→
H
→
I
→
B
通过验证，我们确信这六条路线都是从
A
到
B
的最短路线<
/p>
.
如果按照上述方法找，它的
缺点是不能
保证找出所有的最短路线，即不能保证“不漏”
.
当然如果图形
更复杂些
，做到
“不重”也是很困难的。
现在观察这种题是否有规律可循。
1.
看
C
点：由
A
、由
F
和由
D
都可以到达
C
，而由
F
→
C
是由下向上走，由
D
→
C
是由右
向左走，这两条路线不管以后怎样走都不可能是最短路线
.
因此，从
A
到
C<
/p>
只有一条路线。
同样道理：从
A
到
D
、从
A
到
E
、从
A
到
H
也都只有一条路线。
我们把数字“
1
”分别标在
C
、
D
、
E
、
H
这四个点上，如图
4
—
2
。
2.
看
F
点：从上向下走是
C
→
F
，从左向右走是
E
< br>→
F
，那么从
A
点出发到
F
，可以是
A
→
C
→
F
，也可以是
A
→
E
→
F
，共有两种走法
.
我们在图
4
—
2
中的
F
点标上数字“
2
”
.2=1
＋
1.
第一个“
1
”是从<
/p>
A
→
C
的一种<
/p>
走法；第二个“
1
”是从
A
→
E
的一种走法。
3.
看
G
点：从上向下走是
D
→
G
，从左向右走是
F
→
< br>G
，那么从
A
→
G
[
来源
< br>:
学
*
科
*
网
]
我
们在
G
点标上数字“
3
”
.3
＝
2+1
，
“
2
”是从
A
→
F
的两种走法，
“
1
”是从
A
→
D
的一
种走法。<
/p>
4.
看
I
点：从上向下走是
F
→
I
，从左向右走是
H
→
I
，那么从出发点
<
/p>
在
I
点标上“
3
”
.3=2+1.
“
< br>2
”是从
A
→
< br>F
的两种走法；“
1
”是从
A
→
H
的一种走法
。
5.
看
B
点：从上向下走是
G
→
B
，从左向右走是
I
→
B
，那么从出发点
A
→
B
可以这样走：
1
<
/p>
共有六种走法
.6=3
＋
3
，第一个“
3
”是从
A
→
G
共有三种走法
，第二个“
3
”是从
A
→
I
共有三种走法
.
在
B
点标上“
6
”。
我们观察图
4
—
2
发现每一个小格右下角上标的数正
好是这个小格右上角与左下角的数
的和，这个和就是从出发点
A
到这点的所有最短路线的条数
.
这样，
我们可以通过计算来确
定从
A
→
B
的最短路线的条数，而且能够保证“不重”也“不漏”。
解：
由上面的分析可以得到如下的规律：
每个格右上角与左下角所标的数字和即为这格右下
角应标的数字
.
我们称这种方法为对角线法，也叫标号法。
根据这种
“对角线法”
，
B
点标
6
，
那么从
A
到
B
就有
6
条不同的最短路线<
/p>
（见图
4
—
3<
/p>
）
。
答：从<
/p>
A
到
B
共有
6
条不同的最短路线。
例
2
图
4
—
4
是一个街道
的平面图，纵横各有
5
条路，
某人从
A
到
B
处（只能从北向南及
从西向东），共有多少种不同的走法？
分析因为
B
点在
A
点的东南方向，题目要求我们
只能从北向南及从西向东，也就是要
求我们走最短路线。解：如图
4
—
5
所示。答：从
A
到
B
共有
< br>70
种不同的走法。
例
3
如图<
/p>
4
—
6
，从甲地
到乙地最近的道路有几条？
分析
<
/p>
要求从甲地到乙地最近的道路有几条，
也就是求从甲地到乙地的最
短路线有几条
.
把各交叉点标上字母，如图
4
—
7.
这道题的图形与例
1
、例
2
的图形又有
所区别，因此，在
解题时要格外注意是由哪两点的数之和来确定另一点的。
①由甲→
A
有
1
种走法，由甲→
F
有<
/p>
1
种走法，那么就可以确定从甲→
G
共有
1
＋
1
＝
2
（种）走法。
②由甲→
B
有
1
种走法，
由甲→
D
< br>有
1
种走法，
那么可以确定由甲
→
E
共有
1+1
＝
2
（种）
走法
.
③由甲→
C
有
1
种走法，由甲→
H
有
2
种走法，那么可以确定由甲→
J
共有
1+2=3
（种）
走
法。
④由甲→
G
有
2
种走法，
由甲→
M
有
1
种走法，
那么可以确定从甲→
N
共有
2
＋
1=3
（种）
< br>走法。
2
⑤从甲→
K
有
2
种走法，从甲→
E
有
2
种走法，那么从甲→
L<
/p>
共有
2
＋
2=4
（种）走法。
⑥从甲→
N
有
3
种走法，
从甲→
L
有
4
种走法，
那么可以确定从甲→
P
< br>共有
3
＋
4=7
（种）
走法。
⑦从甲→
J
有
3
种走法，从
甲→
P
有
7
种
走法，那么从甲→乙共有
3+7=10
（种）走法。
解：在图
4
—
7
中各交叉点标上数，乙处标上
10
，则从甲到乙共有
10
条最近的道路。
例
4
某城市的街道非常整齐，
如图
4
—
8
所示，
从西南角
A
处到东北角
B
处要求走最近
的路，
并且不能通过十字路口
C
（因正
在修路）
.
问共有多少种不同的走法？
分析
因为
B
点在
A
点的东北角，
< br>所以只能向东和向北走
.
为了叙述方便，
在各交叉点标
上字母，如图
4
—
9.
①
从
A
→
A1
有
1
种走法，
A
→
A11
有
1
种走法
，那么可以确定从
A
→
A10
共有
1
＋
1=2
（种）
走法。
②
从
A
→
A2
有
1
种走法，
A
→
A10
有
2
种走法，那么可以确定从
A
→
A9
共有
1+2=3
（种）走
法。
③
从
A
→
A3
有
1<
/p>
种走法，
A
→
A
9
有
3
种走法，
那么可以确定从
A
→
A8
共有
1+3=4
（种）
走
法
.
[
来<
/p>
源
:
学
+
科
+
网
Z+X+X+
K]
④从
A
→
A4
有
1
种走法，
A
→
A8
有
4
种走法，那么可以确定
A
→
A7
，共有
1+4=5
（种）走法。
⑤
从
A
→
A5
< br>有
1
种走法，
A
→
A7
有
5
< br>种走法，
那么可以确定
A
→
A6
共有
1
＋
5
＝
6
（种）
走法。
⑥
从
A
→
C1
有
1
种走法，
A
→
A10
有
2
种走法，那么可以确定从
A
→
C2
共有
1+2=3
（种）
走
法。
⑦
从
A
→
C2<
/p>
有
3
种走法，
A
→
A9
有
3<
/p>
种走法，那么可以确定
A
→
C3
共有
3+3=6
（种）
走法。
⑧
从
A
→
C4
可
以是
A
→
C
→
C4
，也可以是
A
→
A7
→
C4
，因为
C
处正在修路，所以
A
→
C
→
C4
行不通，只能由
A7
→
C4
，
由于
A
→
A7
有
5
种走法，
所以
A
→
C4
也有
5
种走法，从
A
→
A6
有
6
种走法，所以从
A
→
C5
共有
5+6
＝
11
（种）走法。
< br>⑨从
A
→
B6
< br>有
1
种走法，
A
→
C2
有
3
< br>种走法，
那么可以确定从
A
→<
/p>
B7
共有
1
＋<
/p>
3=4
（种）
走法。
⑩从
A
→
B7
有
4
种走法，
< br>A
→
C3
有
6
种走法，那么可以确定从
A
→<
/p>
B8
共有
4
＋<
/p>
6=10
（种）走
法。
< br>
⑾从
A
→
B9
可以是
A
→
< br>B8
→
B9
，也可以是
A
→
C
→
B9
，因为
C
处正在修路，
所以
A
→
C
→
B9
行
不通，只能由
< br>B8
→
B9
，由于
A
→
B8
有
10
种走法，所以
A
→
B9
。也有
10
种走
法
.
从
A
→<
/p>
C4
有
5
种走法
，所以从
A
→
B10
< br>共有
10+5=15
（种）走法。
⑿
从
A
→
C5
有
11
种走法，
A
→
B10
有
15
种走法，那么从
A
→
B11
共有
15+11=26
（种）
走法。
⒀
从
< br>A
→
B5
有
1
种走法，
A
→
< br>B7
有
4
种走法，
那么可以确定从
A
→
B4<
/p>
共有
1+4=5
（种）
< br>走法。
[
来源
:]
[
来源
:Z&xx&]<
/p>
[
来源
:]
⒁<
/p>
从
A
→
B4
有
5
种走法，<
/p>
A
→
B8
有
10
种走法，那么可以确定从
A
→
B3
共有
5+10=1
5
（种）
走法
.
(15)
从
A
→
< br>B3
有
15
种走法，
A
→
B9
有
10
种走法，
那么可以确定从
A
→
B2
共有
15
＋
10=25
（
种）
走法。
(16)
从
A
→
B2
有
25
种走法，
A
→
B10
有
15<
/p>
种走法，
那么可以确定从
A
→
B1
共有
25+15=4
0
（
种）
走法。
3