OG 12 191题

isaxi · 发表于 2009-8-25 20:34:00

如果，求X到Y的最小长度的路径的数目。除了数数，还有什么解题办法。谢谢。[attachimg]72250[/attachimg]

[此贴子已经被作者于2009/8/25 20:36:09编辑过]

isaxi · 发表于 2009-8-26 21:07:00

自己顶。我解释一下，假设每个临近的节点之间都是一样长的。最小长度的意思是不能走回头路，也不能倒退（如X上1，右1，下1，就是倒退了）。

寒霜的眼泪 · 发表于 2009-8-26 22:38:00

数数应该是最快的方法了，OG给的就是比数数进化的，但是比数数慢，反正我数数半分钟不到搞定

isaxi · 发表于 2009-8-26 23:27:00

谢谢了。呵呵。就怕数错了。感觉有点象排列组合，但是还真想不出来怎么算。

huangyikai · 发表于 2009-8-26 23:40:00

可以只数横线啊，不用管竖线，一共是10条。

如果横向的第一步走的是最下面一条横线，则第二步可以有4个选择

如果走的是倒数第二条横线，则第二步只有3个选择（因为只能往上走）。

如果走的是倒数第三条横线，则第二步只有2个选择

如果走的是最上面一条横线，则第二步只有1个选择

btw，如果数竖线也是一样，只是因为有3列，所以麻烦一些

总之还是个排列组合的题~~

isaxi · 发表于 2009-8-27 09:55:00

非常感谢。

yorkkroy · 发表于 2010-3-29 11:00:56

个人感觉就是C(5,3),一共需要5步，只要任意选择3步，另外两步就自然而然决定了。C(5,3)=5×4×3/3×2=10

所属分类: GMAT考试