苏珊很为难.她步行去学校,路上老是遇到斯廷基.斯廷基:"嘿嘿,苏珊,我可以陪你一起走吗?"苏珊:"不!请走开." 苏珊心想:我有办法了.每天早上我走不同的路线去学校.这样斯廷基就不知道在哪儿找到我了.这张地图表示苏珊的住所和学校之间的所有街道.苏珊去学校时,走路的方向总是朝南或朝东.她总共有多少条路线呢? 苏珊:"我真想知道有多少条路线可走.让我想一想.要算出多少条路线看来并不简单.嗯.啊哈!一点不难,简单的很!"苏珊想到了什么好主意? 她的推理如下:苏珊:"在我家这个角点上写一个1,因为我只能从这一点出发.然后在遇刺相隔一个街区的两个角点上各写一个1,因为到那里只有一条途径.现在,我在这个角点上写上2,因为到达那里可以有两条途径.苏珊发现2是1加1之和,她忽然领悟:若到某一个仅有一条途径,则该角点上的数字为前一个角点上的数字;若有两条途径,则为前两个角点上的数字之和. 苏珊:"瞧,又有四个角点标上了数字,我马上把其他角点也标上数字."请你替苏珊把剩下的角点标上数字,并且告诉她步行到学校共有多少条不同的路线. 苏珊的家H
学校G
把整个棋盘正确标号,根据所标的数字,一眼就能看出在棋盘上从一个角出发到任意一角,有多少条最短路线.右上角的数字是3432,所以"车"从一角到对角线的另一角的最短路径共有3432条. 让我们把棋盘沿着左上至右下的对角线一截为二,使其成为如下图所示的阵列.此三角形上的数字与著名的怕斯卡三角形(我国叫做杨辉三角形)的数字是相同的,当然,计算街道路径条数的算法,恰恰就是构造怕斯卡三角形所依据的过程.这种同构现象使得怕斯卡三角形成为无数有趣特性的不竭的源泉. 1 11 121 1331 14641 ........... 利用怕斯卡三角形立即可以求出二项式展开的系数,即求(a+b)的任意次幂,同样也可以用来解出初等概率论中的许多问题.请注意,上图中自顶部至底部,从边沿一格来说是1,随着向中间移动,数字逐渐增加.也许你见过根据怕斯卡三角形所制成的一种装置:在一快倾斜的板上,成百个小球滚过木钉进入各格的底部.全部小球呈现出一条钟形的二项式分布曲线,因为到达每个底部孔位的最短路径的条数就是二项式展开的系数. 显然,苏珊的算法同样适用于由矩阵格子组成的三维结构.设有一个边长为3的立方体,分成27个立方体单元,把它看成棋盘,处于某一个角格上的"车"可以向三个坐标上的任何位置作直线移动,试问"车"到空间对角线的另一个角格有多少条最短路径? (责任编辑:admin) |