[求助]OG 316

clairec

OG 316

Pat will walk from intersection X to intersection Y along a route that is confined to the square grid of four streets and three avenues shown in the map above. How many routes from X to Y can Pat take that have the minium possible length?

(C) Ten

以下引用版主horsefish的解释
要使路线最短,经过2,3,4 的顺序一定是固定的, 而经过b,c的顺序也固定,否则不可能路线最短, 且必然经过2,3,4,b,c这5条线, 所以本题转化为2,3,4,b,c这5个元素的排列, 且满足顺序2,3,4,b,c, 则总的排列可能通过两种方法得到

1. 5个位置中选出两个位置被b,c且满足b在c前, 则为c(5,2),剩下的3个位置也必然俺顺序为2,3,4这种唯一可能,所以答案c(5,2)=10

2. 5个位置选出3个给2,3,4且必须满足2在3前,3在4前, 则为c(5,3),剩下的位置必然俺顺序b在c千面这种唯一可能,所以答案c(5,3)=10

请问有谁可再说明白些？

blackhorse

说得很明白了，否则你只好一条一条数，不过倒是数不了多久。

也可参考http://forum.chasedream.com/dispbbs.asp?BoardID=22&ID=64537

lugubrious

你先画一个4横3竖的一个网，X是左下角，Y是右上角。现在的问题就是在这个网格上，

从X到Y右几种走发，对吧。

现在你画的图是一个2×3的格子对吧（因为横竖分别是4，3条线）。

你现在在这个2×3的格子最左边的那条边的每个交点上都标上1，同样的，在底边的每个交点上

也标上1。

接下来要做一些小学算术，在方格的其它所有交点上都标上数，但右要求，

每个交点上的数字等于它下面和左边这两个数字的和。那么你看看左右Y点的数字是几。

现在我再说这个方法为什么能得出结果，当你标1时，其实是表示那些被标1得点，只有1中走

法可以到达，对吧，再说你算得哪些小加法，如果从两条来的路的可能走发分别是A和B，那么

这个交点的走发就应该是A＋B对吧。但是这是在不走冤枉路的情况下。

一切都说清除了吧，大功告成。

clairec

谢谢大家

请问lugubrious:如果排列组合我易错，便用此法对吧？

lugubrious

对头，这个方法简单易行。而且出题的也不会出超过几十行几十列的。

不过，如果你要记住一个公式也就行了：A，B分别是行数减1和列数减1（也就是横数的格子数）

C（A，A+B)就是走对角，最近走发的数量。

clairec

C（A，A+B）就是走对角，最近走发的数量--”走对角，最近走发的数量”是何意？是指像此题X及Y在对角线的位置、求X到Y的走法吗？

另外为何题目要强调the minimum possible length? 不是都一定要走5格吗？若求the maximum possible length，答案也一样吧？

lugubrious

就是不走冤枉路。你要是走来走去，走来走去的，绕圈圈，来回走，有无数种走发。

对交线什么的无所谓，像这种问题，在任意格子上的任意两点都可以看成是对角线方向。

clairec

Thank you.

erer

3楼太强了, 崇拜啊