2022年排列组合中的最短路径问题 .pdf

《2022年排列组合中的最短路径问题 .pdf》由会员分享，可在线阅读，更多相关《2022年排列组合中的最短路径问题 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、试卷第 1 页，总 4 页两个计数原理的应用一、选择题1如图，小明从街道的E处出发，先到F 处与小红会合，再一起到位于G处的老年公寓参加志愿者活动，则小明到老年公寓可以选择的最短路径条数为【答案】B（ A）24 （B）18 （ C）12 （D）9【解析】试题分析：由题意，小明从街道的E处出发到F 处最短路径的条数为6，再从 F处到 G处最短路径的条数为3，则小明到老年公寓可以选择的最短路径条数为6318，故选 B.【考点】计数原理、组合【名师点睛】分类加法计数原理在使用时易忽视每类中每一种方法都能完成这件事情，类与类之间是相互独立的；分步乘法计数原理在使用时易忽视每步中某一种方法只是完成这件事

2、的一部分，而未完成这件事，步步之间是相互关联的2如图，一只蚂蚁从点出发沿着水平面的线条爬行到点，再由点沿着置于水平面的长方体的棱爬行至顶点，则它可以爬行的不同的最短路径有（B ）条A. 40 B. 60 C. 80 D. 120 【解析】试题分析：蚂蚁从到需要走五段路，其中三纵二竖，共有条路径，从到共有条路径，根据分步计数乘法原理可知，蚂蚁从到可以爬行的不同的最短路径有条，故选B. 考点：分步计数乘法原理. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - -

3、- - - - - - - 试卷第 2 页，总 4 页二、解答题3某城市有连接8 个小区A、B、C、D、E、F、G、H和市中心O的整齐方格形道路网，每个小方格均为正方形，如图，某人从道路网中随机地选择一条最短路径，由小区A前往H.(1) 列出此人从小区A到H的所有最短路径( 自A至H依次用所经过的小区的字母表示) ；(2) 求他经过市中心O的概率【答案】 (1) 见解析（2）23【解析】解： (1) 此人从小区A前往 H的所有最短路径为：AB CEH，ABO EH，ABO G H，ADO EH，ADO G H，ADFG H共 6 条(2) 记“此人经过市中心O ”为事件M ，则M 包含的基本事

4、件为： ABO EH，ABO G H，ADO EH，ADO G H共 4 个， P(M)4623，即他经过市中心O的概率为23.【考点定位】概率、统计4如图，在某城市中，两地之间有整齐的方格形道路网，1A、2A、3A、4A是道路网中位于一条对角线上的个交汇处，今在道路网、处的甲、乙两人分别要到，处，他们分别随机地选择一条沿街的最短路径，同时以每10 分钟一格的速度分别向，处行走，直到到达，为止。（ 1）求甲由M处到达 N处的不同走法种数；（ 2）求甲经过2A的概率；（ 3）求甲、乙两人相遇经2A点的概率；（ 4）求甲、乙两人相遇的概率；【答案】（1）20（2）920（3）81400（4）411

5、00【解析】甲由道路网处出发随机地选择一条沿街的最短路径到达处需走 6 步，共有36C种，即共有20 种。（ 2）甲经过2A到达，可分为两步：第一步：甲从经过2A的方法数：13C种；第二步：甲从2A到的方法数：13C种；所以：甲经过2A的方法数为213)(C；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 试卷第 3 页，总 4 页所以：甲经过2A的概率209)(36213CCP（3）由（） 知：甲经过2A的方法数为：213)(

6、C；乙经过2A的方法数也为：213)(C；所以甲、乙两人相遇经2A点的方法数为：413)(C；甲、乙两人相遇经2A点的概率40081)(3636413CCCP（4）甲、乙两人沿最短路径行走，只可能在1A、2A、3A、4A处相遇，他们在)4, 3, 2, 1(iAi相遇的走法有413)(iC种方法；所以：433423413403)()()()(CCCC甲、乙两人相遇的概率10041400164P三、填空题5如图所示是一个由边长为1 个单位的12 个正方形 组成的43棋盘，规定每次只能沿正方形的边运动，且只能走一个单位，则从A走到B的最短路径的走法有种【答案】 35【解析】 要想从A走到B的路径最

7、短， 只需走 7 个单位，并且这7 个单位中， 有 3 个横单位和 4 个竖单位；在这7 各单位中，只要3 个横单位确定，走法就确定；所以B的最短路径的走法有3735C种6从点A到点B的路径如图所示，则不同的最短路径共有条【答案】 35【解析】试题分析：由于从A,到 B走 7 步，但是这 7 步中必须走3 个垂直的步伐， 4 个水平的步伐， 那么可知只要确定了水平的4 步即可，即为437735CC, 则不同的最短路径为35. 考点：排列组合的运用点评：解决的关键是利用分布乘法计数原理得到，属于基础题。AB名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -