排列组合中的最短路径问题.docx

两个计数原理的应用

一、选择题

1．如图，小明从街道的E处出发，先到F处与小红会合，再一起到位于G处的老年公寓参加志愿者活动，则小明到老年公寓可以选择的最短路径条数为【答案】B

（A）24 （B）18 （C）12 （D）9

【解析】

试题分析：由题意，小明从街道的E处出发到F处最短路径的条数为6，再从F处到G处最短路径的条数为3，则小明到老年公寓可以选择的最短路径条数为6?3?18，故选B.

【考点】计数原理、组合

【名师点睛】分类加法计数原理在使用时易忽视每类中每一种方法都能完成这件事情，类与类之间是相互独立的；分步乘法计数原理在使用时易忽视每步中某一种方法只是完成这件事的一部分，而未完成这件事，步步之间是相互关联的．2．如图，一只蚂蚁从点出发沿着水平面的线条爬行到点，再由点沿着置于水平面的长方体的棱爬行至顶点，则它可以爬行的不同的最短路径有

（ B ）条

A.40B.60C.80D.120

【解析】试题分析：蚂蚁从到需要走五段路，其中三纵二竖，共有条路径，从到共有条路径，根据分步计数乘法原理可知，蚂蚁从到可以爬行的不同的最短路径有条，故选B.

考点：分步计数乘法原理.二、解答题

某城市有连接8个小区A、B、C、D、E、F、G、H和市中心O的整齐方格

形道路网，每个小方格均为正方形，如图，某人从道路网中随机地选择一条最短路径，由小区A前往H.

列出此人从小区A到H的所有最短路径(自A至H依次用所经过的小区的字母表示)；

求他经过市中心O的概率．

2

【答案】(1)见解析（2）3

【解析】

解：(1)此人从小区A前往H的所有最短路径为：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包含的基本事件为：A→B→O→E→H，A→B→O→G→H，A→D→O→E→H，A→D→O→G→H共4个，

4 2

∴P(M)＝6＝3，

2

即他经过市中心O的概率为3.

【考点定位】概率、统计

Ａ１

Ａ

１

Ｎ

Ａ

２

Ａ

３

Ｍ

Ａ

４

路网，A、A、A

1 2 3

、A是道路网中位于一条对角线上的

4

４个交汇处，今在道路网Ｍ、Ｎ处的甲、乙两人分别要到Ｍ，Ｎ处，他们分别随机地选择一条沿街的最短路径，同

时以每10分钟一格的速度分别向Ｎ，Ｍ处行走，直到到达Ｎ，Ｍ为止。

求甲由M处到达N处的不同走法种数；

求甲经过A

2

的概率；

求甲、乙两人相遇经A

2

点的概率；

求甲、乙两人相遇的概率；

【答案】（1）20（2）9

（3）

81（4）41

20 400 100

【解析】甲由道路网Ｍ处出发随机地选择一条沿街的最短路径到达Ｎ处需走6步，共有

C3种，即共有20种。

6

（2）甲经过A

2

到达Ｎ，可分为两步：第一步：甲从Ｍ经过A

2

的方法数：C1

3

种；第二步：甲从A

到Ｎ的方法数：C1种；所以：甲经过A

的方法数为

2

(C1)2；

3

所以：甲经过A的概率P?

3 2

?(C1)2 9

?

3

2

（3）由（１）知：甲经过A

C3 20

6

的方法数为：(C1)2；乙经过A

的方法数也

2 3 2

为：(C1)2；所以甲、乙两人相遇经A点的方法数为：(C1)4＝８１；

3

甲、乙两人相遇经A

2

2

点的概率P?

(C1)4

3

C3C3

3

? 81

400

6 6

（4）甲、乙两人沿最短路径行走，只可能在A、A、A

1 2 3

们在A(i?1,2,3,4)相遇的走法有(Ci?1)4种方法；

、A处相遇，他

4

i 3

所以：(C0)4?(C1)4?(C2)4?(C3)4＝１６４

3 3 3 3

甲、乙两人相遇的概率P?

三、填空题

164? 41

400 100

如图所示是一个由边长为1个单位的12个正方形组成的34棋盘，规定每次只能沿正方形的边运动，且只能走一个单位，则从A走到B的最短路径的走法有种

B

A

【答案】35

【解析】要想从A走到B的路径最短，只需走7个单位，并且这7个单位中，有3个横单位和4个竖单位；在这7各单位中，