-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

大きな数を処理する方法の 1 つですが、最大長がわかっている場合は、配列を使用する方法があります。数値を部分に分割し、各部分を個別の配列要素に格納できます。

もう 1 つの方法は、リンクされたリストを使用して、最初は不明な長さの多数を処理することです。原則は同じままで、数値をより小さな部分に分割し、リストの別々のノードに保存します。

どちらの場合でも、実行する必要がある算術演算を処理するために、独自の関数を作成する必要があります。全体として、興味深いプログラミング演習になるでしょう:)

于 2013-02-16T15:10:28.447 に答える
0

パスカルの三角形を使用すると、解をより効率的に解くことができます。乗算を使用せずに。また、オーバーフローの問題は、整数区切り桁によって解決されます。

于 2013-02-17T10:26:26.693 に答える