国际顶尖MBA申请交流平台--TOPWAY MBA

标题: [求助]OG 316 [打印本页]

作者: dhhgh11 时间: 2004-9-19 19:12 标题: [求助]OG 316

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?

以下引用版主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

请问有谁可再说明白些？

作者: himba 时间: 2004-9-19 19:16

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

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

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

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

也标上1。

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

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

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

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

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

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

欢迎光临国际顶尖MBA申请交流平台--TOPWAY MBA (http://forum.topway.org/)