c – 计算组合时溢出
发布时间：2020-12-16 10:11:35 所属栏目：百科 来源：网络整理
导读：我正在尝试计算C中的组合C(40,20),但是C中的数据类型似乎无法正确处理此计算,即使我使用了长long数据类型.以下是我的代码： #include iostreamlong long fac(int x) { register long long i,f = 1; // Optimize with regFunction for(i = 1;i = x;i++) f *=
|
我正在尝试计算C中的组合C(40,20),但是C中的数据类型似乎无法正确处理此计算,即使我使用了长long数据类型.以下是我的代码：
#include <iostream>
long long fac(int x) {
register long long i,f = 1; // Optimize with regFunction
for(i = 1;i <= x;i++)
f *= i;
std::cout << f << std::endl;
return f;
}
// C(n,r) = n!/r!(n-r)!
long long C(long long n,long long r) {
return fac(n) / (fac(r) * fac(n - r));
}
int main(int argc,char const *argv[]) {
std::cout << C(40,20) << std::endl;
return 0;
}
有什么想法解决这个问题吗？ 解决方法
在乘法后立即执行除法,立即计算C：
long long C(long long n,long long r)
{
long long f = 1; // Optimize with regFunction
for(auto i = 0; i < r;i++)
f = (f * (n - i)) / (i + 1);
return f ;
}
结果应该是精确的(没有余数的除法,直到溢出),因为(i 1)中存在的任何整数因子已经存在于(n -i)中. (不应该太难证明) （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |