计算组合数的程序问题

zyj19831206

计算组合数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);
}

snljty

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)也可以明显降低计算量。

snljty

snljty 发表于 2019-9-20 21:54
fac这个名字还以为是阶乘...
公式您可以稍微优化一下啊，这个计算量太大了，而且显然有一部分相同的数被乘 ...

大多数编译器在主流电脑上int最大默认是2147483647，首先改成unsigned int就能大一倍，然后你算阶乘的话，13的阶乘就超过了2 ** 31 - 1，所以你这个写法m最大是12，不管k是多少，哪怕k=0，都算不了。

zyj19831206

snljty 发表于 2019-9-20 22:00
大多数编译器在主流电脑上int最大默认是2147483647，首先改成unsigned int就能大一倍，然后你算阶乘的话 ...

明白，那您觉得这个源代码应该怎么修改呢？能否给个结果，多谢了！

hxd_yi

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呢！
再不够，上所谓的高精度计算，要多少位？

zyj19831206

hxd_yi 发表于 2019-9-21 00:45
fac可以改为：
int fac(int m, int n){
    if (mm/2)n=m-n;

感觉将这个子程序修改为你的这段后，怎么运行结果都是1啊？

hxd_yi

zyj19831206 发表于 2019-9-21 09:51
感觉将这个子程序修改为你的这段后，怎么运行结果都是1啊？

ans=ans*(n+1-i)/i;这一句打错了，应该为ans=ans*(m+1-i)/i;

zyj19831206

hxd_yi 发表于 2019-9-21 11:36
ans=ans*(n+1-i)/i;这一句打错了，应该为ans=ans*(m+1-i)/i;

貌似是可以计算了，对于比较大的数有负值？

hxd_yi

zyj19831206 发表于 2019-9-21 16:52
貌似是可以计算了，对于比较大的数有负值？

int型的溢出导致的，根据你最初的题意就是这个样子。