分类:
2009-01-16 16:08:14
苏珊的家H
1
1 |
1
2 |
1
3 |
|
2 |
5 |
|
学校 G
剩下的5个点,自上而下,从左至右分别标以1,4,9,4,13.最后一点上的13表示苏珊去学校共有十三条最短路径.
苏珊所发现的是一种快速而简单的算法,用来计算从她家到学校的最短路径共有多少条.要是她把这些路径一条一条地画出来,然后再计数,这样肯定麻烦,还容易
出错.如果街道的数目很多,那么这种方法根本就行不通.你不妨把这十三条路线都画出来,这样你就更能体会到苏珊的算法是多么地有效了.
你对这种算法是否已经理解,可以再画一些不同的街道网络,然后用这种算法来确定从任意点A到另一任意点B的最短路线共有多少条.网络可以是矩形网格,三角
形网格,平行四边形网格和蜂窝状的正六边形网格.也可以用其他方法(例如组合公式)求解,但这种方法十分复杂,需要很高的技巧.
在国际象棋棋盘上,"车"从棋盘的一角到对角线上另一角的最短路径共有多少条?就像苏珊给街道交点标上数字一样,把棋盘上所有格子也都填上数字,于是问题
就迎刃而解了."车"只能沿着右上方向朝另一个角的目标移动,便可以求出共有多少条最短路径.如图所示:
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 |
把整个棋盘正确标号,根据所标的数字,一眼就能看出在棋盘上从一个角出发到任意一角,有多少条最短路线.右上角的数字是3432,所以"车"从一角到对角线的另一角的最短路径共有3432条.
让我们把棋盘沿着左上至右下的对角线一截为二,使其成为如下图所示的阵列.此三角形上的数字与著名的怕斯卡三角形(我国叫做杨辉三角形)的数字是相同的,
当然,计算街道路径条数的算法,恰恰就是构造怕斯卡三角形所依据的过程.这种同构现象使得怕斯卡三角形成为无数有趣特性的不竭的源泉.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...........