《排列组合中的最短路径问题.pdf》由会员分享，可在线阅读，更多相关《排列组合中的最短路径问题.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、两个计数原理的应用两个计数原理的应用一、选择题一、选择题1如图，小明从街道的 E 处出发，先到 F 处与小红会合，再一起到位于 G 处的老年公寓参加志愿者活动，则小明到老年公寓可以选择的最短路径条数为【答案】B（A）24（B）18（C）12（D）9【解析】试题分析：由题意，小明从街道的E 处出发到 F 处最短路径的条数为 6，再从 F 处到 G处最短路径的条数为 3，则小明到老年公寓可以选择的最短路径条数为63 18，故选 B.【考点】计数原理、组合【名师点睛】分类加法计数原理在使用时易忽视每类中每一种方法都能完成这件事情，类与类之间是相互独立的；分步乘法计数原理在使用时易忽视每步中某一种方法
2、只是完成这件事的一部分，而未完成这件事，步步之间是相互关联的2如图，一只蚂蚁从点出发沿着水平面的线条爬行到点，再由点沿着置于水平面的长方体的棱爬行至顶点，则它可以爬行的不同的最短路径有（B）条A.40 B.60 C.80 D.120【解析】试题分析：蚂蚁从到需要走五段路，其中三纵二竖，共有条路径，从到共有条路径，根据分步计数乘法原理可知，蚂蚁从到可以爬行的不同的最短路径有条，故选B.考点：分步计数乘法原理.二、解答题二、解答题3某城市有连接 8 个小区A、B、C、D、E、F、G、H和市中心O的整齐方格形道路网，每个小方格均为正方形，如图，某人从道路网中随机地选择一条最短路径，由小区A前往H.(
3、1)列出此人从小区A到H的所有最短路径(自A至H依次用所经过的小区的字母表示)；(2)求他经过市中心O的概率【答案】(1)见解析（2）【解析】解：(1)此人从小区 A 前往 H 的所有最短路径为：23ABCEH，ABOEH，ABOGH，ADOEH，ADOGH，ADFGH共 6 条(2)记“此人经过市中心 O”为事件 M，则 M 包含的基本事件为：共 4 个，P(M)ABOEH，ABOGH，ADOEH，ADOGH42，632.3即他经过市中心 O 的概率为【考点定位】概率、统计4如图，在某城市中，两地之间有整齐的方格形道路网，A1、A2、A3、A4是道路网中位于一条对角线上的个交汇处，今在道路网
4、、处的甲、乙两人分别要到，处，他们分别随机地选择一条沿街的最短路径，同时以每 10 分钟一格的速度分别向，处行走，直到到达，为止。（1）求甲由 M 处到达 N 处的不同走法种数；（2）求甲经过A2的概率；（3）求甲、乙两人相遇经A2点的概率；（4）求甲、乙两人相遇的概率；【答案】（1）20（2）81419（3）（4）40010020【解析】甲由道路网处出发随机地选择一条沿街的最短路径到达处 需走 6 步，共有3C6种，即共有 20 种。（2）甲经过A2到达，可分为两步：第一步：甲从经过A2的方法数：C3种；第二步：甲从A2到的方法数：C3种；所以：甲经过A2的方法数为(C3)；112112(C
5、3)9所以：甲经过A2的概率P 320C6（3）由（）知：甲经过A2的方法数为：(C3)；乙经过A2的方法数也为：(C3)；所以甲、乙两人相遇经A2点的方法数为：(C3)；14(C3)81甲、乙两人相遇经A2点的概率P 33C6C6400141212（4）甲、乙两人沿最短路径行走，只可能在A1、A2、A3、A4处相遇，他们在Ai(i 1,2,3,4)相遇的走法有(C3i1)4种方法；04142434所以：(C3)(C3)(C3)(C3)甲、乙两人相遇的概率P 16441400100三、填空题三、填空题5如图所示是一个由边长为 1 个单位的 12 个正方形组成的34棋盘，规定每次只能沿正方形的边
6、运动，且只能走一个单位，则从A走到B的最短路径的走法有种BA【答案】35【解析】要想从A走到B的路径最短，只需走 7 个单位，并且这7 个单位中，有 3 个横单位和 4 个竖单位；在这7 各单位中，只要3 个横单位确定，走法就确定；所以B的最3短路径的走法有C7 35种6从点A A到点B B的路径如图所示，则不同的最短路径共有条【答案】35【解析】试题分析：由于从A,到 B 走 7 步，但是这7 步中必须走 3 个垂直的步伐，4 个水平的步43伐，那么可知只要确定了水平的4 步即可，即为C7 C7 35,则不同的最短路径为 35.考点：排列组合的运用点评：解决的关键是利用分布乘法计数原理得到，属于基础题。