最短路线问题——标数法的应用
余年寄山水
789次浏览
2020年12月07日 07:47
最佳经验
本文由作者推荐
大谎言家-项链绳的编法
v1.0 可编辑可修改
计数的基本方法——标数法
例1：沿着下图所显示的线段，从A点到B点，有多少条最短路线
E
H
B
C
F
I
A
D
G
例2：沿着下图所显示的线段，从A点到B点，有多少条最短路线
(1)
A
(2)
A
B
B
11
v1.0 可编辑可修改
例3：沿下图所示的线段，从A步行到Z，但行走方向只能向东或向南，他有多少种不同的
行走路线
A
例4：如图，求A到B沿网格线的最短路线数：
Z
B
（1）
必须经过点C；
（2） 必须经过线段EF；
（3） 不经过点C；
（4）
不经过线段EF；
例5：按下图箭头所指的方向行走，从A到达Z有多少种不同行走路线
A
本章小结：
1.什么是标数法
22
A
E
F
C
Z
v1.0 可编辑可修改
答：在每个点上标记出从起点出发到此点的路线数的一种计数方法。
2.如何使用标数法解决长方形网络图中的最短路线问题
答：
1.
确定标数的方向；
2. 将与起点共直线的点上标上数字1；
3.
画出每个小方格对角线；
4.
把每个小方格内对角线顶点上的两个数字相加，和标记在剩下的那个点上；
2.如何使用标数法解决路线数问题
答：
1.
从某一点出发到另一点只有一条路线的时候，则后点上标记的数字应该和前一点相同；
2. 如果到达
某一点必须经过与这个点相邻的两个或几个点时，则该点上标记的数字是能够
到达这一点的相邻的两个或
几个点上标记的数字之和。
33