估计大家都做过这么一道题，就是求从大小为m×n的矩形网格左下角到右上角一共有几种走法。m、n为格子的数量，不是经纬线的数量。问题是用计算机解这个问题时需要计算m+n与n的组合数（或者m，两者相等），如果直接用M+N的阶乘除以m的阶乘与n的阶乘的积来得到商，那么由于m+n的阶乘增长速度飞快，很小的数，比如m+n=10就会导致用32位整数保存这个结果时发生溢出。所以我想到的办法是不计算m、n中较大的数的阶乘，直接消去。（假设m是较大的数）然后从m+1开始计算，(m+1)/1,(m+2)/2，(m+3)/3……（m+n）/n;然后把这些商乘起来，作为结果。
这里就有一个问题：如何证明这么做的过程中每一个商都是整数？（因为计算机在规定了结果类型是整数之后就不会保存结果的小数部分，必须保证每个商都是整数。）如果不是每个商都是整数，怎么求这个结果才是正确的？

楼主的问题好像就是求组合数.百度上有很多程序.如果非得自己做个程序,可以这样,先算除法,把分子除干净了,就不大会溢出了.没学过计算机,不知是否可行

回复：2楼
“把分子除干净”的前提是要知道分子究竟是多少。所以说还是要先求出M+N的阶乘——而这，正是我要避免的情形。

楼主那样除不能保证结果都是整数,应该经过判断吧,商是整数就取商,不是就不除,反正最后总能把分子除干净

楼主那样除不能保证结果都是整数,应该经过判断吧,商是整数就取商,不是就不除,反正最后总能把分子除干净

回复：4楼
哦，抱歉。我说的不对。我的算法是设一个数a=1，不断地让a先乘m+1然后再除以1、先乘m+2再除以2……直到n。不是分别保存每个商。

这样呢?分子的每个因数与分母的每个因数做除法,保留整数,然后乘.貌似很笨.不行的话找算法大牛吧,这个我不行,只能说说想法,具体操作就悲剧了

给个例吧
计算C(4,5)
5/1*4/2*3/3*2/4
从左到右运算,每步都是整数(由数论性质保证),也很难溢出(除非结果本来就溢出)
如果想绝对防止溢出,那就要特殊处理了

尾随楼上

回复：8楼
谢谢8楼给的信心，不然我也不会开始证明这个问题。我这样想的，分母部分增长至N时，分子是一个“n个连续的整数”相乘所得的数，这n个因数中必有一个是n的整数倍。所以这样算一定是没有非整除情况出现的。

了解了...