c++ - 做组合时被零除

Question

我正在尝试计算数学组合。我使用的公式是 N! / K! (N-K)! .

我可以用 10 得到正确答案 ( N=5 ) , K=2 , 和 120来自 N=10 , K=3 .

但是当我尝试使用更大的数字(如 N=50)进行测试时, K=5.弹出整数除以零的错误。

我试图定义 finalAns与 long int但它也不起作用。有什么想法吗？

int N;
int init;
int K;
int factN = 1;
int factK = 1;
double finalAns;

cout << "Input of N = ";
cin >> N;
cout << "Input of K = ";
cin >> K;

int subs = N - K;
int factsubs = 1;

for (init = 1; init <= N; init++)
{

    factN = factN * init;
}
for (init = 1; init <= K; init++)
{

    factK = factK * init;
}
cout << "K is " << factK << endl;
for (init = 1; init <= subs; init++)
{

    factsubs = factsubs * init;
}

finalAns = factN / (factK * factsubs);
cout << N << "C" << K << " is " << finalAns << endl;

Answer 1

您需要改变一次乘法的方法。

• 不要一次性计算N!。
• 利用任何两个正整数相除都会减少最终结果的事实，因此有利于相除得到较低的中间值。

展开 N!/(N-K)! 的表达式* K! 以在中间 步骤中容纳尽可能多的除法运算，以减少溢出的机会。

不要分别计算N! 或(N-K)! 或K!，你更有可能面临溢出问题。取而代之的是，最终您需要对大数进行除法，为什么不在它变得大之前就这样做呢!

更多提示:

N!/(N-K)! = multiply i[N..N-K+1] one by one //not i[N..1] 

并且，检查 [2..K] 中值 j 的任何因子 (f) 是否完美地划分中间产品值 (p)，如果是，做除法:p = p/f 和 j = j/f。