整数运算计算组合数C(n, k)

计算组合数$C_n^k$的公式为

$$
C_n^k = \frac{n!}{k! \times (n - k)!}
$$

由于用到了阶乘,极容易导致数据溢出,应用中应采用边乘边除的方法。除法一般需要用到浮点数,但通过数论中的定理,可以通过整数运算实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
int C(int n, int k)
{
long long s = 1;
int x = 1;
if(k > n - k) k = n - k;
for(int i = n; i > n - k; i--)
{
s *= i;
s /= x;
x++;
}
return (int)s;
}

代码如下如果想测试你自己的实现,请移步POJ 2249题


版权声明

The Bloom of Youth by KUANG Qi is licensed under a Creative Commons BY-NC-ND 4.0 International License.
况琪创作并维护的锦瑟华年博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于The Bloom of Youth | 锦瑟华年博客( http://kuangqi.me ),版权所有,侵权必究。

本文永久链接:http://kuangqi.me/programming/combination-calculation/