排列组合中的最短路径问题
白玉兰树-大闹天宫影评
两个计数原理的应用
一、选择题
1.如图,小明从街道的E处出
发,先到F处与小红会合,再一起到位于G处的老年公
寓参加志愿者活动,则小明到老年公寓可以选择的
最短路径条数为【答案】B
(A)24 (B)18
(C)12 (D)9
【解析】
试题分析:由题意,小明从街道的E处出发到F
处最短路径的条数为6,再从F处到G
处最短路径的条数为3,则小明到老年公寓可以选择的最短路径条
数为
6318
,故
选B.
【考点】计数原理、组合
【名师点
睛】分类加法计数原理在使用时易忽视每类中每一种方法都能完成这件事情,
类与类之间是相互独立的;
分步乘法计数原理在使用时易忽视每步中某一种方法只是完
成这件事的一部分,而未完成这件事,步步之
间是相互关联的.
2.如图,一只蚂蚁从点出发沿着水平面的线条爬行到点,再由点沿着置于水平面的
长
方体的棱爬行至顶点,则它可以爬行的不同的最短路径有( B )条
A. 40 B. 60 C. 80 D. 120
【解析】试题分析
:蚂蚁从到需要走五段路,其中三纵二竖,共有条路径,从到共有条
路径,根据分步计数乘法原理可知,
蚂蚁从到可以爬行的不同的最短路径有条,故选
B.
考点:分步计数乘法原理.
二、解答题
3.某城市有连接8个小区A、B、C、D、E、F、G、H和市中心
O的整齐方格形道路网,
每个小方格均为正方形,如图,某人从道路网中随机地选择一条最短路径,由小
区A前
往H.
(1)列出此人从小区A到H的所有最短路径(自A至H依次用所经过的小区的字母表示);
(2)求他经过市中心O的概率.
【答案】(1)见解析 (2)
【解析】
解:(1)此人从小区A前往H的所有最短路径为:
2
3
A
1
A
2
A
3
N
A→B→C→E→H,A→B→O→E→H,A→B→O
→G→H,A→D→O→E→H,
A→D→O→G→H,A→D→F→G→H共6条.
(2)记“此人经过市中心O”为事件M,则M包含的基本事件为:
M
A
4
A→B→O→E→H,A→B→O→G→H,A→D→O→E→H,A
→D→O→G→H
共4个,
∴P(M)=
42
=,
63
2
.
3
即他经过市中心O的概率为
【考点定位】概率、统计
4.如图,在某城市
中,M,N两地之间有整齐的方格形道路网,
A
1
、
A
2
、
A
3
、
A
4
是
道路网中位于一条对角线上的4个交
汇处,今在道路网M、N处的甲、乙两人分别要到
M,N处,他们分别随机地选择一条沿街的最短路径,
同时以每10分钟一格的速度分
别向N,M处行走,直到到达N,M为止。
(1)求甲由M处到达N处的不同走法种数;
(2)求甲经过
A
2
的概率;
(3)求甲、乙两人相遇经
A
2
点的概率;
(4)求甲、乙两人相遇的概率;
【答案】(1)
20
(2)
8141
9
(3)(4) 400100
20
【解析】甲由道路网M处出发随机地选择一条沿街的最短路径到达N处
需走6步,共
有
3
C
6
种,即共有20种。
(2)甲经过
A
2
到达N,可分为两步:第一步:甲从M经过
A2
的方法数:
C
3
种;第二
步:甲从
A
2到N的方法数:
C
3
种;所以:甲经过
A
2
的方法数为
(C
3
)
;
112
1
12
(C
3
)
9
所以:甲经过
A
2
的概率
P
3
20
C
6
(3)由(1)知:甲经过
A2
的方法数为:
(C
3
)
;乙经过
A
2
的方法数也为:
(C
3
)
;
14
所以甲、乙两人相遇经<
br>A
2
点的方法数为:
(C
3
)
=81;
1212
14
(C
3
)
81
甲、乙两人相遇经
A
2
点的概率
P
33
C
6
C
6
400
(4)甲、乙两人沿最短路径行走,只可
能在
A
1
、
A
2
、
A
3
、
A
4
处相遇,他们在
A
i
(i1,2,3,4)
相遇的
走法有
(C
3
i1
)
4
种方法;
041424
34
所以:
(C
3
)(C
3
)(C
3
)(C
3
)
=164
甲、乙两人相遇的概率
P
16441
400100
三、填空题
5.如图所示是一个由边长为1个单位的12个
正方形组成的
34
棋盘,规定每次只能
沿正方形的边运动,且只能走一个单位,则从
A
走到
B
的最短路径的走法有 种
B
A
【答案】35
【
解析】要想从
A
走到
B
的路径最短,只需走7个单位,并且这7个单位中,有
3个
横单位和4个竖单位;在这7各单位中,只要3个横单位确定,走法就确定;所以
B
的
3
最短路径的走法有
C
7
35
种
6.从点
A
到点
B
的路径如图所示,则不同的最短路径共有
条.
【答案】35
【解析】
试题分析:由于从A,到B走7步,但是
这7步中必须走3个垂直的步伐,4个水平的步
43
伐,那么可知只要确定了水平的4步即可,
即为
C
7
C
7
35
,则不同的最短路径为35.
考点:排列组合的运用
点评:解决的关键是利用分布乘法计数原理得到,属于基础题。