沿网格线从 A(-3,-2) 到 B(5,2)，途中要经过 P(-1,1) 或 Q(-2,2) 的最短路径有几条？

wintex

請問為何a走到b延着格線走必經過第二像限走法（＝75）
一定要經過p,q
A-p-b
A-q-b

再問 為何不等於用全部方法 －  A-O-B

luyuanhong

题  沿网格线从 A(-3,-2) 到 B(5,2)，途中要经过 P(-1,1) 或 Q(-2,2) 的最短路径有几条？

解  一般来说，设 S(p,q)，T(m,n)（其中 m≥p ，n≥q）是坐标平面上两点。

    沿网格线从 S(p,q) 到 T(m,n) 的最短路径共有 C(m-p+n-q,m-p) 条。

    在本题中，沿网格线从 A(-3,-2) 到 P(-1,1) 的最短路径有 C(-1+3+1+2,-1+3)=C(5,2) 条。

    沿网格线从 P(-1,1) 到 B(5,2) 的最短路径有 C(5+1+2-1,5+1)=C(7,6) 条。

    所以，从 A 经过 P 再到 B 的最短路径有 C(5,2)×C(7,6) = 10×7 = 70 条。

    沿网格线从 A(-3,-2) 到 Q(-2,2) 的最短路径有 C(-2+3+2+2,-2+3)=C(5,1) 条。

    沿网格线从 Q(-2,2) 到 B(5,2) 的最短路径有 C(5+2+2-2,5+2)=C(7,7) 条。

    所以，从 A 经过 Q 再到 B 的最短路径有 C(5,1)×C(7,7) = 5×1 = 5 条。

    总之，从 A 到 B ，途中经过 P 或 Q 的最短路径共有 70+5 = 75 条。

wintex

luyuanhong 发表于 2020-6-3 18:16
题  沿网格线从 A(-3,-2) 到 B(5,2)，途中要经过 P(-1,1) 或 Q(-2,2) 的最短路径有几条？

解  一般来说 ...

陸老師 為何一定要選p,q 兩點分類？

luyuanhong

题目要求从 A 到 B 最短路径必须经过第二象限，选择 P(-1,1) 和 Q(-2,2) ，可以做到以下几点：

（1）因为 P,Q 在第二象限，所以任何从 A 到 B，途中经过 P 或 Q 的最短路径，必定经过第二象限。

（2）因为 P,Q 完全拦住了第二象限中的最短路径，所以任何经过第二象限的最短路径，必定经过 P 或 Q 。

（3）从 P,Q 的位置可以看出，经过 P 的最短路径，不会再经过 Q，经过 Q 的最短路径，不会再经过 P ，

这样就可以避免重复计算。

    从上面的分析可以知道，经过 P 或 Q 的最短路径，与经过第二象限的最短路径，是一一对应的。