走格子题的简便算法

xhn

看了数学机经的讨论，感觉对那种给了几横几竖交叉成一片格子然后让算从A点走到B点有多少条最短路线的题目给出的算法比较麻烦，我想到一种简单的算法，和大家分享一下，希望对大家能有所帮助，同时也激励自己为自己的考试攒人品，哈哈。

我的分析过程是这样的（以3*5的格子为例，横着需要走三个，竖着需要走五个）：

从A到B走最短路线不论怎样走，都要走3个横，5个竖，一共要走8个。那么任意一条已定的路线（大家可以在草稿纸上画出一个路线，然后用每一步走的是“横”还是“竖”把这条路线念出来），只对应唯一的一种表述方法（即3个“横”和5个“竖”的一种排列组合）；而反过来，任意一种表述方法，比如我说“横横竖竖横竖竖竖”，那照此在草纸上画，也只得到唯一的一条路线。

到这大家就应该可以看出了，从A到B的路线，和3横5竖的排列是一种一一对应的关系。

所以这种题就和“一共有8个位置，任选3个位置放‘横’，剩下5个位置放‘竖’”是一个意思一个算法，即C38

感觉自己说的很罗嗦，见谅~~~

JamesJl

对的 我第一感觉就觉得高中时用排列组合算过这种题 研究了半天 也想起了这个办法 呵呵

leeyuan1

清楚明了，有收获，谢谢

cxyxiaoxiao

感谢LZ!

crgo

很经典，谢谢！

Boot

这题我记得好像是属于离散数学方面的概念的。
而且是最简单的那种。。。
离散数学已经全部都忘记了。shit！！

anyway，我觉得这个方法也不错，算出来和答案对不？

fatfatsheep

非常好

conniequan

辛苦lz了！

bluefirmamen

非常感谢！

点金

谢谢lz~~