蘇珊很為難.她步行去學校，路上老是遇到斯廷基.斯廷基："嘿嘿，蘇珊，我可以陪你一起走嗎?"蘇珊："不!請走開."
    蘇珊心想：我有辦法了.每天早上我走不同的路線去學校.這樣斯廷基就不知道在哪兒找到我了.這張地圖表示蘇珊的住所和學校之間的所有街道.蘇珊去學校時，走路的方向總是朝南或朝東.她總共有多少條路線呢?
    蘇珊："我真想知道有多少條路線可走.讓我想一想.要算出多少條路線看來并不簡單.嗯.啊哈!一點不難，簡單的很!"蘇珊想到了什么好主意?
    她的推理如下：蘇珊："在我家這個角點上寫一個1，因為我只能從這一點出發(fā).然后在遇刺相隔一個街區(qū)的兩個角點上各寫一個1，因為到那里只有一條途徑.現(xiàn)在，我在這個角點上寫上2，因為到達那里可以有兩條途徑.蘇珊發(fā)現(xiàn)2是1加1之和，她忽然領悟：若到某一個僅有一條途徑，則該角點上的數(shù)字為前一個角點上的數(shù)字;若有兩條途徑，則為前兩個角點上的數(shù)字之和.
    蘇珊："瞧，又有四個角點標上了數(shù)字，我馬上把其他角點也標上數(shù)字."請你替蘇珊把剩下的角點標上數(shù)字，并且告訴她步行到學校共有多少條不同的路線.
    蘇珊的家H
    

1               1	1               2	1               3
	2	5

     
    學校G
    剩下的5個點，自上而下，從左至右分別標以1，4，9，4，13.最后一點上的13表示蘇珊去學校共有十三條最短路徑.
    蘇珊所發(fā)現(xiàn)的是一種快速而簡單的算法，用來計算從她家到學校的最短路徑共有多少條.要是她把這些路徑一條一條地畫出來，然后再計數(shù)，這樣肯定麻煩，還容易出錯.如果街道的數(shù)目很多，那么這種方法根本就行不通.你不妨把這十三條路線都畫出來，這樣你就更能體會到蘇珊的算法是多么地有效了.
    你對這種算法是否已經(jīng)理解，可以再畫一些不同的街道網(wǎng)絡，然后用這種算法來確定從任意點A到另一任意點B的最短路線共有多少條.網(wǎng)絡可以是矩形網(wǎng)格，三角形網(wǎng)格，平行四邊形網(wǎng)格和蜂窩狀的正六邊形網(wǎng)格.也可以用其他方法(例如組合公式)求解，但這種方法十分復雜，需要很高的技巧.
    在國際象棋棋盤上，"車"從棋盤的一角到對角線上另一角的最短路徑共有多少條?就像蘇珊給街道交點標上數(shù)字一樣，把棋盤上所有格子也都填上數(shù)字，于是問題就迎刃而解了."車"只能沿著右上方向朝另一個角的目標移動，便可以求出共有多少條最短路徑.如圖所示：
    

1	8	36	120	330	792	1716	3432
1	7	28	84	210	462	924	1716
1	6	21	56	126	252	462	792
1	5	15	35	70	126	210	330
1	4	10	20	35	56	84	120
1	3	6	10	15	21	28	36
1	2	3	4	5	6	7	8
車	1	1	1	1	1	1	1

     
    把整個棋盤正確標號，根據(jù)所標的數(shù)字，一眼就能看出在棋盤上從一個角出發(fā)到任意一角，有多少條最短路線.右上角的數(shù)字是3432，所以"車"從一角到對角線的另一角的最短路徑共有3432條.
    讓我們把棋盤沿著左上至右下的對角線一截為二，使其成為如下圖所示的陣列.此三角形上的數(shù)字與著名的怕斯卡三角形(我國叫做楊輝三角形)的數(shù)字是相同的，當然，計算街道路徑條數(shù)的算法，恰恰就是構造怕斯卡三角形所依據(jù)的過程.這種同構現(xiàn)象使得怕斯卡三角形成為無數(shù)有趣特性的不竭的源泉.
    1
    11
    121
    1331
    14641
    ...........
    利用怕斯卡三角形立即可以求出二項式展開的系數(shù)，即求(a+b)的任意次冪，同樣也可以用來解出初等概率論中的許多問題.請注意，上圖中自頂部至底部，從邊沿一格來說是1，隨著向中間移動，數(shù)字逐漸增加.也許你見過根據(jù)怕斯卡三角形所制成的一種裝置：在一快傾斜的板上，成百個小球滾過木釘進入各格的底部.全部小球呈現(xiàn)出一條鐘形的二項式分布曲線，因為到達每個底部孔位的最短路徑的條數(shù)就是二項式展開的系數(shù).
    顯然，蘇珊的算法同樣適用于由矩陣格子組成的三維結(jié)構.設有一個邊長為3的立方體，分成27個立方體單元，把它看成棋盤，處于某一個角格上的"車"可以向三個坐標上的任何位置作直線移動，試問"車"到空間對角線的另一個角格有多少條最短路徑?
    中考相關信息請關注出國留學網(wǎng)中考頻道......
     
    

中考政策

中考狀元

中考飲食

中考備考輔導

中考復習資料