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

1 / 4 两个计数原理的应用一、选择题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） 23【解析】解： (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 个，∴ P(M)＝ 46＝ 23，即他经过市中心O的概率为 23.【考点定位】概率、统计4．如图，在某城市中，Ｍ，Ｎ两地之间有整齐的方格形道路网，1A 、2A 、3A 、4A 是道路网中位于一条对角线上的４个交汇处，今在道路网Ｍ、Ｎ处的甲、乙两人分别要到Ｍ，Ｎ处，他们分别随机地选择一条沿街的最短路径，同时以每10 分钟一格的速度分别向Ｎ，Ｍ处行走，直到到达Ｎ，Ｍ为止。（ 1）求甲由 M处到达 N处的不同走法种数；（ 2）求甲经过2A 的概率...