排列組合中的最短路徑問(wèn)題[教育相關(guān)]

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

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

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

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