排列組合中的最短路徑問題

1、兩個計數原理的應用一、選擇題1如圖，小明從街道的E處出發(fā)，先到F處與小紅會合，再一起到位于G處的老年公寓參加志愿者活動，則小明到老年公寓可以選擇的最短路徑條數為【答案】B（A）24 （B）18 （C）12 （D）9【解析】試題分析：由題意，小明從街道的E處出發(fā)到F處最短路徑的條數為6，再從F處到G處最短路徑的條數為3，則小明到老年公寓可以選擇的最短路徑條數為，故選B.【考點】計數原理、組合【名師點睛】分類加法計數原理在使用時易忽視每類中每一種方法都能完成這件事情，類與類之間是相互獨立的；分步乘法計數原理在使用時易忽視每步中某一種方法只是完成這件事的一部分，而未完成這件事，步步之間是相互關聯(lián)的2

2、如圖，一只螞蟻從點出發(fā)沿著水平面的線條爬行到點，再由點沿著置于水平面的長方體的棱爬行至頂點，則它可以爬行的不同的最短路徑有（ B ）條A. 40 B. 60 C. 80 D. 120【解析】試題分析：螞蟻從到需要走五段路，其中三縱二豎，共有條路徑，從到共有條路徑，根據分步計數乘法原理可知，螞蟻從到可以爬行的不同的最短路徑有條，故選B.考點：分步計數乘法原理.二、解答題3某城市有連接8個小區(qū)A、B、C、D、E、F、G、H和市中心O的整齊方格形道路網，每個小方格均為正方形，如圖，某人從道路網中隨機地選擇一條最短路徑，由小區(qū)A前往H.(1)列出此人從小區(qū)A到H的所有最短路徑(自A至H依次用所經過的小

3、區(qū)的字母表示)；(2)求他經過市中心O的概率【答案】(1)見解析 （2）【解析】解：(1)此人從小區(qū)A前往H的所有最短路徑為：ABCEH，ABOEH，ABOGH，ADOEH，ADOGH，ADFGH共6條(2)記“此人經過市中心O”為事件M，則M包含的基本事件為：ABOEH，ABOGH，ADOEH，ADOGH共4個，P(M)，即他經過市中心O的概率為.【考點定位】概率、統(tǒng)計4如圖，在某城市中，兩地之間有整齊的方格形道路網，、是道路網中位于一條對角線上的個交匯處，今在道路網、處的甲、乙兩人分別要到，處，他們分別隨機地選擇一條沿街的最短路徑，同時以每10分鐘一格的速度分別向，處行走，直到到達，為止。

4、（1）求甲由M處到達N處的不同走法種數；（2）求甲經過的概率；（3）求甲、乙兩人相遇經點的概率；（4）求甲、乙兩人相遇的概率；【答案】（1）20（2）（3）（4）【解析】甲由道路網處出發(fā)隨機地選擇一條沿街的最短路徑到達處 需走6步，共有種，即共有20種。 （2）甲經過到達，可分為兩步：第一步：甲從經過的方法數：種；第二步：甲從到的方法數：種；所以：甲經過的方法數為； 所以：甲經過的概率（3）由（）知：甲經過的方法數為：；乙經過的方法數也為：；所以甲、乙兩人相遇經點的方法數為： ； 甲、乙兩人相遇經點的概率（4）甲、乙兩人沿最短路徑行走，只可能在、處相遇，他們在相遇的走法有種方法；所以：甲、乙兩人相遇的概率三、填空題5如圖所示是一個由邊長為1個單位的12個正方形組成的棋盤，規(guī)定每次只能沿正方形的邊運動，且只能走一個單位，則從走到的最短路徑的走法有 種【答案】35【解析】要想從走到的路徑最短，只需走7個單位，并且這7個單位中，有3個橫單位和4個豎單位；在這7各單位中，只要3個橫單位確定，走法就確定；所以的最短路徑的走法有種6從點到點的路徑如圖所示，則不同的最短路徑共有 條【答案】35【解析】試題分析：由于從A,到B走7步，但是這7步中必須走3個垂直的步伐，4個水平