2022年 11月 4日

怎么使用python来实现计算组合数?

组合数:

从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。

公式:

C(n,m)=C(n-1,m-1)+C(n-1,m)

利用 math中的 factorial函数计算阶乘实现

  1. from math import factorial
  2.  
  3. # factorial 计算阶乘
  4.  
  5.  
  6. def CmbinationNumber(n,m):
  7.     if m <= n:
  8.         
  9.         a=factorial(n)/(factorial(n-m) * factorial(m))
  10.     return a
  11.  
  12. res = CmbinationNumber(50, 3)
  13. print(res)

运算结果:

利用递归实现

  1. def C(n, m):
  2.     if m == 0 or n == m:
  3.         return 1
  4.     return C(n - 1, m - 1) + C(n - 1, m)
  5.  
  6. print(C(50, 3))

运行结果:

使用递归会随着n和m的值增大,计算的时间会越来越长,因为利用的的递归开辟的栈较多,计算也会有重复