三年級(jí)奧數(shù)詳解答案-第十九講-最短路線問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第十九講 最短路線問題在日常工作、生活和娛樂中，經(jīng)常會(huì)遇到有關(guān)行程路線的問題.在這一講里，我們主要解決的問題是如何確定從某處到另一處最短路線的條數(shù)。例1 下圖41中的線段表示的是汽車所能經(jīng)過的所有馬路，這輛汽車從A走到B處共有多少條最短路線？分析 為了敘述方便，我們?cè)诟鹘徊纥c(diǎn)都標(biāo)上字母.如圖42.在這里，首先我們應(yīng)該明確從A到B的最短路線到底有多長？從A點(diǎn)走到B點(diǎn)，不論怎樣走，最短也要走長方形AHBD的一個(gè)長與一個(gè)寬，即ADDB.因此，在水平方向上，所有線段的長度和應(yīng)等于AD；在豎直方向上，所有線段的長度和應(yīng)等于DB.這樣我們走的這條路線才是最短路線.為了保證這一點(diǎn)，

2、我們就不應(yīng)該走“回頭路”，即在水平方向上不能向左走，在豎直方向上不能向上走.因此只能向右和向下走。有些同學(xué)很快找出了從A到B的所有最短路線，即：ACDGB ACFGBACFIB AEFGBAEFIB AEHIB通過驗(yàn)證，我們確信這六條路線都是從A到B的最短路線.如果按照上述方法找，它的缺點(diǎn)是不能保證找出所有的最短路線，即不能保證“不漏”.當(dāng)然如果圖形更復(fù)雜些，做到“不重”也是很困難的?，F(xiàn)在觀察這種題是否有規(guī)律可循。1.看C點(diǎn)：由A、由F和由D都可以到達(dá)C，而由FC是由下向上走，由DC是由右向左走，這兩條路線不管以后怎樣走都不可能是最短路線.因此，從A到C只有一條路線。同樣道理：從A到D、從A到

3、E、從A到H也都只有一條路線。我們把數(shù)字“1”分別標(biāo)在C、D、E、H這四個(gè)點(diǎn)上，如圖42。2.看F點(diǎn)：從上向下走是CF，從左向右走是EF，那么從A點(diǎn)出發(fā)到F，可以是ACF，也可以是AEF，共有兩種走法.我們?cè)趫D42中的F點(diǎn)標(biāo)上數(shù)字“2”.2=11.第一個(gè)“1”是從AC的一種走法；第二個(gè)“1”是從AE的一種走法。3.看G點(diǎn)：從上向下走是DG，從左向右走是FG，那么從AG我們?cè)贕點(diǎn)標(biāo)上數(shù)字“3”.32+1，“2”是從AF的兩種走法，“1”是從AD的一種走法。4.看I點(diǎn)：從上向下走是FI，從左向右走是HI，那么從出發(fā)點(diǎn)在I點(diǎn)標(biāo)上“3”.3=2+1.“2”是從AF的兩種走法；“1”是從AH的一種走法。

4、5.看B點(diǎn)：從上向下走是GB，從左向右走是IB，那么從出發(fā)點(diǎn)AB可以這樣走：共有六種走法.6=33，第一個(gè)“3”是從AG共有三種走法，第二個(gè)“3”是從AI共有三種走法.在B點(diǎn)標(biāo)上“6”。我們觀察圖42發(fā)現(xiàn)每一個(gè)小格右下角上標(biāo)的數(shù)正好是這個(gè)小格右上角與左下角的數(shù)的和，這個(gè)和就是從出發(fā)點(diǎn)A到這點(diǎn)的所有最短路線的條數(shù).這樣，我們可以通過計(jì)算來確定從AB的最短路線的條數(shù)，而且能夠保證“不重”也“不漏”。解：由上面的分析可以得到如下的規(guī)律：每個(gè)格右上角與左下角所標(biāo)的數(shù)字和即為這格右下角應(yīng)標(biāo)的數(shù)字.我們稱這種方法為對(duì)角線法，也叫標(biāo)號(hào)法。根據(jù)這種“對(duì)角線法”，B點(diǎn)標(biāo)6，那么從A到B就有6條不同的最短路線（見

5、圖43）。答：從A到B共有6條不同的最短路線。例2 圖44是一個(gè)街道的平面圖，縱橫各有5條路， 某人從A到B處（只能從北向南及從西向東），共有多少種不同的走法？ 分析 因?yàn)锽點(diǎn)在A點(diǎn)的東南方向，題目要求我們只能從北向南及從西向東，也就是要求我們走最短路線。解：如圖45所示。答：從A到B共有70種不同的走法。例3 如圖46，從甲地到乙地最近的道路有幾條？ 分析 要求從甲地到乙地最近的道路有幾條，也就是求從甲地到乙地的最短路線有幾條.把各交叉點(diǎn)標(biāo)上字母，如圖47.這道題的圖形與例1、例2的圖形又有所區(qū)別，因此，在解題時(shí)要格外注意是由哪兩點(diǎn)的數(shù)之和來確定另一點(diǎn)的。由甲A有1種走法，由甲F有1種走法，

6、那么就可以確定從甲G共有112（種）走法。由甲B有1種走法，由甲D有1種走法，那么可以確定由甲E共有1+12（種）走法.由甲C有1種走法，由甲H有2種走法，那么可以確定由甲J共有1+2=3（種）走法。由甲G有2種走法，由甲M有1種走法，那么可以確定從甲N共有21=3（種）走法。從甲K有2種走法，從甲E有2種走法，那么從甲L共有22=4（種）走法。從甲N有3種走法，從甲L有4種走法，那么可以確定從甲P共有34=7（種）走法。從甲J有3種走法，從甲P有7種走法，那么從甲乙共有3+7=10（種）走法。解：在圖47中各交叉點(diǎn)標(biāo)上數(shù)，乙處標(biāo)上10，則從甲到乙共有10條最近的道路。例4 某城市的街道非常整

7、齊，如圖48所示，從西南角A處到東北角B處要求走最近的路，并且不能通過十字路口C（因正在修路）.問共有多少種不同的走法？分析 因?yàn)锽點(diǎn)在A點(diǎn)的東北角，所以只能向東和向北走.為了敘述方便，在各交叉點(diǎn)標(biāo)上字母，如圖49. 從AA1有1種走法，AA11有1種走法，那么可以確定從AA10共有11=2（種）走法。從AA2有1種走法，AA10有2種走法，那么可以確定從AA9共有1+2=3（種）走法。 從AA3有1種走法，AA9有3種走法，那么可以確定從AA8共有1+3=4（種）走法.從AA4有1種走法，AA8有4種走法，那么可以確定AA7，共有1+4=5（種）走法。從AA5有1種走法，AA7有5種走法，那

8、么可以確定AA6共有156（種）走法。從AC1有1種走法，AA10有2種走法，那么可以確定從AC2共有1+2=3（種）走法。從AC2有3種走法，AA9有3種走法，那么可以確定AC3共有3+3=6（種）走法。從AC4可以是ACC4，也可以是AA7C4，因?yàn)镃處正在修路，所以ACC4行不通，只能由A7C4，由于AA7有5種走法，所以AC4也有5種走法，從AA6有6種走法，所以從AC5共有5+611（種）走法。從AB6有1種走法，AC2有3種走法，那么可以確定從AB7共有13=4（種）走法。從AB7有4種走法，AC3有6種走法，那么可以確定從AB8共有46=10（種）走法。從AB9可以是AB8B9，

9、也可以是ACB9，因?yàn)镃處正在修路，所以ACB9行不通，只能由B8B9，由于AB8有10種走法，所以AB9。也有10種走法.從AC4有5種走法，所以從AB10共有10+5=15（種）走法。 從AC5有11種走法，AB10有15種走法，那么從AB11共有15+11=26（種）走法。 從AB5有1種走法，AB7有4種走法，那么可以確定從AB4共有1+4=5（種）走法。 從AB4有5種走法，AB8有10種走法，那么可以確定從AB3共有5+10=15（種）走法.從AB3有15種走法，AB9有10種走法，那么可以確定從AB2共有1510=25（種）走法。從AB2有25種走法，AB10有15種走法，那么可

10、以確定從AB1共有25+15=40（種）走法。從AB1有40種走法，AB11有26種走法，那么可以確定從AB共有40+26=66（種）走法。解：如圖4-10所示。答：從A到B共有66種不同的走法.習(xí)題四1.如果沿圖4-11中的線段，以最短的路程，從A點(diǎn)出發(fā)到B點(diǎn)，共有多少種不同的走法？2.從學(xué)校到少年宮有4條東西向的馬路和3條南北向的馬路相通.如圖4-12，李楠從學(xué)校出發(fā)，步行到少年宮（只許向東和向南行進(jìn)），最多有多少種不同的行走路線？3.如圖 4-13，從P到Q共有多少種不同的最短路線？4.如圖4-14所示為某城市的街道圖，若從A走到B（只能由北向南、由西向東），則共有多少種不同的走法？5.如圖4-15所示，從甲地到乙地，最近的道路有幾條？6.圖4-16為某城