越算越亂的最短路徑數(shù)

李如

小紅帽的外婆住在森林中的一個小村子里，小紅帽每個周末都會獨自從家出發(fā)，前往外婆家看望她，順便給外婆帶上一些美味的食物。狡猾的大灰狼不知從哪里知道了小紅帽這個習慣，想要埋伏在路邊襲擊小紅帽，把她抓回去吃掉，還好小紅帽的媽媽早有準備。

在小紅帽出門之前，媽媽拿了一張從家到外婆家的路線圖給小紅帽。媽媽囑咐小紅帽，每次從家出發(fā)去外婆家的路線都要不同，而且盡量選擇較短的路線，這樣遇到大灰狼的概率就會大大減少。

“老實”的算法VS“聰明”的算法

小紅帽拿到路線圖的時候看了一下，上面給出了所有從自己家到外婆家可以走的小路。因為外婆家在小紅帽家的東南方向，所以她要么先向南走，要么先向東走，這樣就能順利到達外婆家。那么，她到底有多少條路線可以選擇呢？

小紅帽用筆在路線圖上將路線一條一條地畫了出來，不一會兒，路線圖就被弄花了。她數(shù)了數(shù)，有9條路線可以選擇。

媽媽看著小紅帽一個人趴在桌子上對著路線圖寫寫畫畫，便問她：“你在干什么呢？”

“媽媽，我想算一算從咱們家到外婆家一共有幾條不同的路線可以選擇。”小紅帽向媽媽求助，“我一共算出9條，您看看我算得對嗎？”

媽媽看著被小紅帽弄花的路線圖笑了笑：“我教你用另外一種方法來算，保證簡單，一學就會！”

“真的嗎？快教教我。”小紅帽迫不及待地想讓媽媽教她另一種計算方法。

媽媽接過筆，在路線圖上標出了數(shù)字“1”和“F”，說道：“你看，在與起點相鄰的兩條道路上分別標上1，說明起點附近有2條路可以走。

如果我們想去起點所在的對角線的另一端F，是不是有2條路可以走？”小紅帽點點頭。

“既然這樣，我們在F后邊做個標記。你看，標記的‘（2）其實是與起點相鄰的兩個1的和。代表從起點，也就是我們家，到F有2條路可以走?！毙〖t帽一看，還真是這樣。

媽媽繼續(xù)說：“我們繼續(xù)按照這樣的方法來算算到外婆家有幾條路線可以選擇吧！如果用A表示我們家、用L表示外婆家，那么，我們的目的就是從A出發(fā)到達L。”為了方便小紅帽理解，媽媽繼續(xù)在路線圖上標出了一些不同的字母。

“從A出發(fā)有2條路可以走，分別是‘A→B和‘A→E。

到達B、E后再出發(fā)，各有2條路可以走。

按照剛剛標記路線的方法，我們把能到達這幾個地方的路線數(shù)標記上去。

我們不斷地按照這個方法畫下去，最終就可以得到從A到L的最短路徑數(shù)。”最后，媽媽在路線圖上標出的數(shù)是這樣的：

“這樣算下來，一共有10條路線可以選擇呢！之前是我算錯了?！毙〖t帽羞愧地說。

媽媽笑了笑：“沒關(guān)系，你現(xiàn)在學會了這個方法，既可以簡便地算出結(jié)果，又不會出現(xiàn)遺漏?！?/p>

另一種“聰明”的算法

“其實還有另一種‘聰明的計算方法?！眿寢寷Q定多教小紅帽一點，“這個方法比上一個方法難一點，你可要開動腦筋，好好思考?！?/p>

小紅帽立馬端正地坐下來：“媽媽您快說?！?/p>

“我們先來看看路線圖。”

媽媽拿出另一張嶄新的路線圖，慢慢地畫出幾條線：“你發(fā)現(xiàn)了嗎？無論你選擇哪條路線，都至少要走3條橫向的路和2條豎向的路?！?/p>

“實際上，我們只需要確定走的是哪2條豎向的路，就能確定最短路徑數(shù)。但是這豎向的路不能隨便選?！眿寢屌e了一個例子，“例如，你選擇了下邊這種路線，就必須要走回頭路或者繞遠路?！?/p>

“對這2條豎向的路的選擇還真不能馬虎。”小紅帽若有所思地說。

媽媽也緊接著說道：“是的，這樣的話，我們就要分情況來考慮了。從豎向的路來看，如果我們選擇了‘A→E這條路，那么接下來豎向的路，共有4種選擇。

如果我們選擇了‘A→B→F，那么接下來豎向的路就有3種選擇。

如果我們選擇了‘A→B→C→G

這條路，接下來豎向的路就有2種選擇;最后，如果我們選擇‘A→B→C

→D→H這條路，就只剩下‘H→L這1種選擇了?！?/p>

“把不同情況下的路線數(shù)加起來，一共是4+3+2+1=10（條）。”小紅帽高興地說道，“和用第一種方法算出來的結(jié)果一樣呢！”

媽媽點點頭，說道：“在現(xiàn)實生活中，這個路線圖的模型算是非常簡單的了。今天你學習了新的數(shù)學知識，可一定要牢牢記住喲！”