计算化学公社
标题: 计算组合数的程序问题 [打印本页]
作者Author: zyj19831206 时间: 2019-9-20 18:47
标题: 计算组合数的程序问题
计算组合数C(n,m)。
从 n 个不同元素中每次取出 m 个不同元素
，不管其顺序合成一组，称为从 n 个元素中不重复地选取 m 个元素的一个组合。所有这样的组合的种数称为组合数。
如果你的程序使用int，则你的程序能正确计算的最大n是多少（此时对于所有的m，都是有效的）？
我编写的程序如下所示，编译没问题，但是总是运行不出结果，希望高手指点下。
#include"stdafx.h"
#include <iostream>
using namespace std;
int fac(int m, int k);
int main()
{
int m, k;
cout << "输入m,k:\n";
cin >> m >> k;
while (1){
if (m<k){
cout << "m,k的取值不正确,请重新输入\n";
cin >> m >> k;
}
else break;
}
cout << "m的k的组合数为:" << fac(m, k) << endl;
return 0;
}
int fac(int m, int k){
if (m<k)return -1;
int a = 1, b = 1, c = 1;
for (int i = m; i >= 1; i--)
a *= i;
for (int j = k; j >= 1; j--)
b *= j;
for (int l = m - k; l >= 1; l--)
c *= l;
return a / (b*c);
}
作者Author: snljty 时间: 2019-9-20 21:54
fac这个名字还以为是阶乘...
公式您可以稍微优化一下啊，这个计算量太大了，而且显然有一部分相同的数被乘了一遍又除了一遍，太浪费了。
最容易想到的，一个是C(m, k) = A(m, k) / k! = m * (m-1) * ... * (m - k + 1) / k!，这样至少少算了两次(m-k)!。
另外C(m, k) = C(m, m-k)，所以当2k>m的时候计算C(m, m-k)代替C(m, k)也可以明显降低计算量。
作者Author: snljty 时间: 2019-9-20 22:00
大多数编译器在主流电脑上int最大默认是2147483647，首先改成unsigned int就能大一倍，然后你算阶乘的话，13的阶乘就超过了2 ** 31 - 1，所以你这个写法m最大是12，不管k是多少，哪怕k=0，都算不了。
作者Author: zyj19831206 时间: 2019-9-20 22:25
明白，那您觉得这个源代码应该怎么修改呢？能否给个结果，多谢了！
作者Author: hxd_yi 时间: 2019-9-21 00:45
本帖最后由 hxd_yi 于 2019-9-21 00:51 编辑
fac可以改为：
int fac(int m, int n){
if (m<n)return 0;
int ans=1; if(n>m/2)n=m-n;
for(int i=1;i<=n;++i)
ans=ans*(n+1-i)/i;
return ans;
}
这个比你原来的能计算更大的c(m,n)
嫌不够大，可以把int改成unsiged long long,到2^64-1呢！
再不够，上所谓的高精度计算，要多少位？
作者Author: zyj19831206 时间: 2019-9-21 09:51
感觉将这个子程序修改为你的这段后，怎么运行结果都是1啊？
作者Author: hxd_yi 时间: 2019-9-21 11:36
ans=ans*(n+1-i)/i;这一句打错了，应该为ans=ans*(m+1-i)/i;
作者Author: zyj19831206 时间: 2019-9-21 16:52
貌似是可以计算了，对于比较大的数有负值？
作者Author: hxd_yi 时间: 2019-9-22 16:06
int型的溢出导致的，根据你最初的题意就是这个样子。
| 欢迎光临 计算化学公社 (http://bbs.keinsci.com/) |
Powered by Discuz! X3.3 |
