-1

我想用C做一个数学组合计算器。例如，5组合2是10。即使使用unsigned long long类型，我的程序中也会出现溢出问题。输入源是 n 和 m。每个数字都是 (5<= n,m <= 100) 和 (m<=n) 绑定的。另外，我在下面附上了我的代码。有没有我不知道的更大数字类型或解决方案？请告诉我。提前感谢您的帮助。

#include <stdio.h>
static unsigned long long gcd(unsigned long long a, unsigned long long b)
{
if(a<b)
    return gcd(b, a);
if(b==0)
    return a;
return gcd(b, a%b);
}

int main()
{
unsigned long long n, m1, m2, i, j, temp, denominator[101] = {1,}, numerator[101] = {1,}, total_de = 1, total_nu = 1, gcd_result;

scanf("%llu %llu",&n, &m1);
m2 = n - m1;
if(m2 < m1)
{
    temp = m1;
    m1 = m2;
    m2 = m1;
}// m1 is small

denominator[0] = 1; numerator[0] = 1;
for(i=1; i<=m1; i++)
{
    denominator[i] = n--;
    numerator[i] = i;
}

for(i = 1; i<=m1; i++)
{
    for(j = 1; j<=m1; j++)
    {
        gcd_result = gcd(denominator[i], numerator[j]);
        denominator[i] /= gcd_result;
        numerator[j] /= gcd_result;
    }
}

for(i = 1; i<=m1; i++)
{
    total_de *= denominator[i];
    total_nu *= numerator[i];
}
// sometimes overflow happened
printf("%llu\n",total_de/total_nu);

return 0;
}
4

3 回答 3

4

我建议使用允许任意精度的库，例如GMP。

于 2013-02-16T15:06:42.867 回答
2

处理大量但已知最大长度的一种方法是通过数组。您可以将数字分成几部分并将每个部分存储在单独的数组元素中。

另一种方法是，使用链表来处理大量最初未知的长度。原理保持不变，将数字分成更小的部分并存储在列表的单独节点中。

无论哪种情况，您都必须编写自己的函数来处理您需要完成的算术运算。总的来说，这将是一个有趣的编程练习 :)

于 2013-02-16T15:10:28.447 回答
0

通过使用帕斯卡三角形，我可以更有效地解决我的解决方案。不使用乘法。溢出问题通过整数分隔数字解决。

于 2013-02-17T10:26:26.693 回答