怎么用C++编一个计算C（n,k）的程序呀？谢谢呢~

Question

如题所述

Answer 1

实际中应该避免计算阶乘, 因为阶乘很容易暴掉;
使用公式, Binomial(n, i) = (n)/(i) * (n-1)/(i-1) * ... * (n-(i-1))/(i-(i-1)) 可以避免使用阶乘. 当然, 注意到 Binomial(n, k) = Binomial(n, n-k), 可以取 k 和 n-k 中较小的一个做为i进行计算. 这等价于迭代公式:
Binomial(n,k) = n/k * Binomial( n-1, k-1), with Binomial(1, k) = 1 和Binomial(n,1) = n.

注意到 ( n/k)^k <= Binomial(n,k) <= (n*e/k)^k. 事先应该先做好估计是否会超出整型的范围. 如果超出整型范围可以使用 long型, double 型. 也可以转而计算log(Binomial( n, k) ), 所有二项式,阶乘运算(相乘除)完成后最后再取 exp.

Answer 2

int Cnk(int n, int k)
{
int b = 1, c = 1, temp = 1;
int i ;
if( (n <= 0) || (k < 0) || (k > n) )
return -1; //错误参数，返回-1
if( (0 == k) || (n == k) )
return 1; //等于1的情况
if( k > (n - k) )
k = n - k; //根据组合性质减少计算量
for(i = 1; i <= k; ++i)
temp *= i;//计算k阶乘
b = temp;
for( ; i <= n - k; ++i)
temp *= i; //计算n-k阶乘
c = temp;
for( ; i <= n; ++i)
temp *= i; //计算n阶乘
return temp / (b * c);
}
patriot7 同学把公式记错了。

Answer 3

#include<stdio.h>

void main()
{
__int64 n,m,i;
__int64 ans=1;
scanf("%I64d%I64d",&n,&m);

if(n-m<m)m=n-m;//利用C(n,m)=C(n,n-m)减小计算量
for(i=1;i<=m;i++)
{
ans*=n-i+1;
ans/=i;//利用了连续i个数之中必有一个是i的倍数的原理，这里可以保证整除
}
printf("%I64d\n",ans);
}本回答被提问者采纳

Answer 4

#include <iostream>

int main()
{
int n, k, numerator, denominator;

std::cout << "输入n的值：";
std::cin >> n;

std::cout << "输入k的值：";
std::cin >> k;

numerator = n;
denominator = k;

while(k > 1)
{
numerator *= --n;
denominator *= --k;
}

std::cout << numerator/denominator << std::endl;

return 0;
}