如何计算相交路径的个数？
答案 = 1750 对。题目是从知乎过来的。后面我会给出一个笨的解法。我特别感兴趣的是终极目标。
孤立路数量 = 总数量 - 交叉路数量
= {A-B数量}×{C-D数量} - {A-D数量}×{C-B数量}
譬如:主帖 = {70}×{70} - {210}×{15}=1750。
当然,A,D = 矩形,C 在下边,B 在上边, 且在 C,D 之间。
这是一个猜想, 会有反例吗？欢迎网友批评！谢谢各位网友！新年快乐！ 横坐标相同时候，AB路径的纵坐标都大于CD路径的纵坐标，程序很容易搞定 2#的猜想是正确的。
A↗B与C↗D的路径若相交的话，假定相交路段为E↗F，那么A↗E↗F↗B+C↗E↗F↗D=A↗E↗F↗D+C↗E↗F↗B
而A↗D与C↗B总是要相交的，假定相交路段为E↗F，那么A↗E↗F↗D+C↗E↗F↗B=A↗E↗F↗B+C↗E↗F↗D
所以A↗B与C↗D的相交路径与{A↗D}×{C↗B}是一一对应的。
题目中的图已经给出了暗示。 我特别感兴趣的是终极目标。试试给出通项公式。
A,D = 矩形,C 在矩形下面的边,B 在矩形上面的边, B 在 C,D 之间。
记 A = (0,0),C = (C,0),B = (B,n),D = (D,n),
孤立路数量 = 总数量 - 交叉路数量
= {A-B数量}×{C-D数量} - {A-D数量}×{C-B数量}
= \(\D\bigg(\frac{((B - 0) + n)!\ \ }{(B - 0)! n!}\bigg)\bigg(\frac{((D - C) + n)!\ \ }{(D - C)! n!}\bigg) - \bigg(\frac{((D - 0) + n)!\ \ }{(D - 0)! n!}\bigg)\bigg(\frac{((B - C) + n)!\ \ }{(B - C)! n!}\bigg)\)
在这里:1 ≤ C ≤ D/2,C ≤ B ≤ D - C,D = 任意数,n = 任意数。
譬如:主帖 = {C,B,D} ={2,4,6}。
孤立路数量 = \(\D\bigg(\frac{((4 - 0) + n)!\ \ }{(4 - 0)! n!}\bigg)\bigg(\frac{((6 - 2) + n)!\ \ }{(6 - 2)! n!}\bigg) - \bigg(\frac{((6 - 0) + n)!\ \ }{(6 - 0)! n!}\bigg)\bigg(\frac{((4 - 2) + n)!\ \ }{(4 - 2)! n!}\bigg)\)
n = 1, 2, 3, 4, 5, 6, ...,得到这样一串数: 4, 57, 385, 1750, 6174, 18228, 47124, 109890, 235950, 473473, 897897, 1623076, 2815540, 4712400, 7643472, 12058236, 18558288, 27935985, 41220025, ...
n = 4 =主帖: 孤立路数量 =1750。
再譬如:{C,B,D} ={1,3,5}。
孤立路数量 = \(\D\bigg(\frac{((3 - 0) + n)!\ \ }{(3 - 0)! n!}\bigg)\bigg(\frac{((5 - 1) + n)!\ \ }{(5 - 1)! n!}\bigg) - \bigg(\frac{((5 - 0) + n)!\ \ }{(5 - 0)! n!}\bigg)\bigg(\frac{((3 - 1) + n)!\ \ }{(3 - 1)! n!}\bigg)\)
n = 1, 2, 3, 4, 5, 6, ...,得到这样一串数: 2, 24, 140, 560, 1764, 4704, 11088, 23760, 47190, 88088, 156156, 264992, 433160, 685440, 1054272, 1581408, 2319786, 3335640, 4710860, 6545616, ...
再譬如:{C,B,D} ={2,6,9}。
孤立路数量 = \(\D\bigg(\frac{((6 - 0) + n)!\ \ }{(6 - 0)! n!}\bigg)\bigg(\frac{((9 - 2) + n)!\ \ }{(9 - 2)! n!}\bigg) - \bigg(\frac{((9 - 0) + n)!\ \ }{(9 - 0)! n!}\bigg)\bigg(\frac{((6 - 2) + n)!\ \ }{(6 - 2)! n!}\bigg)\)
n = 1, 2, 3, 4, 5, 6, ...,得到这样一串数:6, 183, 2380, 19250, 113652, 534534, 2114112, 7290855, 22493900, 63269206, 164588424, 400450232, 919413040, 2006411400, 4186514112, 8393685366, ...
通项公式不成熟。欢迎网友批评！谢谢各位网友！新年快乐！ 给出笨的解法。
记 A = (00),C = (20),B = (44),D = (64),
交叉路只会出现在{23, 22, 21, 33, 32, 31, 43, 42, 41}这九个点上。
基本思路: 甲的孤立路×乙的孤立路。
甲从A——B(不过C),有55条路可走。55 = 5 + 4×3 + 3×6 + 2×10
甲的孤立路×乙的孤立路。
甲不过九个点 = 5×55,
过23,33,43 = 4×35,
过23,33 = 4×47,
过23 = 4×53,
过22,32,42,43 = 3×17,
过22,32,33,43 = 3×26,
过22,32,33 = 3×32,
过22,23,33,43 = 3×32,
过22,23,33 = 3×42,
过22,23 = 3×46,
过21,31,41,42,43 = 2×5,
过21,31,32,42 = 2×9,
过21,31,32,33,43 = 2×12,
过21,31,32,33 = 2×14,
过21,22,32,42,43 = 2×13,
过21,22,32,33,43 = 2×19,
过21,22,32,33 = 2×23,
过21,22,23,33,43 = 2×22,
过21,22,23,33 = 2×28,
过21,22,23 = 2×30,
合计: 5×55+4×(35+47+53)+3×(17+26+32+32+42+46)+2×(5+9+12+14+13+19+23+22+28+30) = 1750
55 = 5 + 4×3 + 3×6 + 2×10
页:
[1]