最快的组合数算法之Python实现

原理：以Cni(8,3)为例，按定义式将其展开为(8*7*6*5*4*3*2*1)/(3*2*1)/(5*4*3*2*1)，对于8到6之间的数，分子上出现一次而分母上没出现；5到3之间的数分子、分母上各出现一次；3到1之间的数分子上出现一次而分母上出现两次。 优势：避免了求阶乘的计算，同时也避免了n太大而导致无法使用长整型变量来表示其阶乘（大多数编程语言中都存在这个问题，当然了Python不存在这个问题）。 补充：关键在于算法，可以使用任意其他语言改写程序，但当组合数结果超出了其他语言中长整型变量的表示范围时同样无法使用，使用Python不存在这个问题。 def Cni(n,i):

if not (isinstance(n,int) and isinstance(i,int) and n>=i):

print 'n and i must be integers and n must be larger than or equal to i.'

return

result = 1

Min, Max = min(i,n-i), max(i,n-i)

for i in range(n,0,-1):

if i>Max:

result *= i

elif i<=Min:

result /= i

return result

print Cni(6,2)