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

1、两个计数原理的应用一、选择题1.如图，小明从街道的 E处出发，先到F处与小红会合，再一起到位于G处的老年公寓参加志愿者活动，则小明到老年公寓可以选择的最短路径条数为【答案】B（A） 24（ B）18（ C） 12（ D） 9【解析】试题分析：由题意，小明从街道的 E处出发到F处最短路径的条数为 6，再从F处到G 处最短路径的条数为 3，则小明到老年公寓可以选择的最短路径条数为 6 3=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（1）列出此人从小

3、区 A到H的所有最短路径（自A至H依次用所经过的小区的字母表示 ）;求他经过市中心0的概率.2【答案】见解析 （2）-3【解析】 解：（1）此人从小区A前往H的所有最短路径为:A、A2A4At CH, AtH, At3 H, 2 “E H,At DTOTG H, At DT FtGH 共 6 条.(2) 记“此人经过市中心O为事件 M,则 M包含的基本事件为:At BtOT Et H, At BtOT3 H, At DTOT Et H, At DTOTGH共4个，P(M) = 4 = 2 ,632即他经过市中心 O的概率为三.3【考点定位】概率、统计4 .如图，在某城市中，M,N两地之间有整齐

4、的方格形道路网，A1、A2、A3、A4是道路网中位于一条对角线上的4个交汇处，今在道路网M、N处的甲、乙两人分别要到M,N处，他们分别随机地选择一条沿街的最短路径，同时以每10分钟一格的速度分别向N,M处行走，直到到达N,M为止。(1) 求甲由M处到达N处的不同走法种数；(2) 求甲经过A2的概率；(3) 求甲、乙两人相遇经 A2点的概率；【答案】(1) 20 (2)(3) -81 (4)2040041100(4) 求甲、乙两人相遇的概率；需走6步，共【解析】甲由道路网M处出发随机地选择一条沿街的最短路径到达N处 有3C6种，即共有20种。(2)甲经过A2到达N,可分为两步：第一步：甲从M经过

5、A2的方法数：C；种；第二步：甲从A2到n的方法数：c3种；所以：甲经过 A2的方法数为(c3)2 ；(C1)29所以：甲经过A的概率P33c；2012 1 2(3) 由(1)知：甲经过A2的方法数为：(C3)；乙经过A2的方法数也为：(C3);所以甲、乙两人相遇经 A2点的方法数为：(C3)4 =81;(C1)481甲、乙两人相遇经 a2点的概率p33 3c3c3400(4 )甲、乙两人沿最短路径行走，只可能在A-i、A2、A3、A4处相遇，他们在A(i =123,4)相遇的走法有(C3)4种方法；04142434所以：(C3)(C3)(C3) (C3) =16 416441甲、乙两人相遇的概率 P =400100三、填空题5如图所示是一个由边长为1个单位的12个正方形 组成的3 4棋盘，规定每次只能沿正方形的边运动， 且只能走一个单位， 则从A走到B的最短路径的走法有 种【答案】35【解析】要想从A走到B的路径最短，只需走7个单位，并且这7个单位中，有3个横 单位和4个竖单位；在这7各单位中，只要3个横单位确定，走法就确定；所以 B的最短路径的走法有 Cy -35种6.从点A到点B的路径如图所示，则不同的最短路径共有 条.【答案】35【解析】试题分析：由于从 A,到B走7步，但是这7步中必须走3个垂直的步伐，4