3

C で 2 つの数値の nPr を計算する関数を作成しました。大きな数値を処理するように適応させるのを手伝ってくれませんか?

最大 1x10^12 の値を計算できる必要があります。さまざまなデータ型を試しましたが、非常に行き詰まっています。

#include<stdio.h>
    #include<math.h>

int main()
    {
        long int n=49,k=6;
            printf("%li nPr %li = %li\n\n",n,k,nPr(n,k));

        return 0;

    }      

long nPr(long int n, long int k);
     long nPr(long int n, long int k){

        if (n < 0 ){
            printf("\nERROR - n is less than 0\n\n");
            return -1;
        }

        if (k > n ){
            printf("\nERROR - k is greater than n\n\n");
            return -1;
        }

        else {
            long int i,result = 1,c=n+1-k;

            for(i=c; i<=n; i++)
            {
                result = result * i;
            }
            return result;
        }
     }

ありがとう

J

更新:これらは反復なしの順列です。

私も試しました

long long nPr(long long int n, long long int k);
long long nPr(long long int n, long long int k){

    if (n < 0 ){
        printf("\nERROR - n is less than 0\n\n");
        return -1;
    }

    if (k > n ){
        printf("\nERROR - k is greater than n\n\n");
        return -1;
    }

    else {
        long long int i,result = 1,c=n+1-k;

        for(i=c; i<=n; i++)
        {
            result = result * i;
        }
        return result;
    }
 }

しかし、それは何の違いもないように見えました

4

2 に答える 2

4

おそらくGMPライブラリを使用して、 bignumsを使用して計算したい場合があります。C++ に切り替えると、 GMP への C++ クラス インターフェイスを使用して、bignum に対しても使い慣れた表記法を使用できます。純粋な C を使用している場合は、特定のルーチン (加算用のmpz_addなど) を慎重に使用する必要があります。a+b

ところで、一部の言語 ( Common Lispなど) は bignum をネイティブにサポートしています (通常の数値で動作するソース コードを変更する必要はありません)。SBCLを試してみることをお勧めします(少なくとも Linux では)。

もちろん、bignum 算術 (非常に複雑な主題) は、ネイティブ算術よりも低速です。

Bignum は C でネイティブにサポートされていないため、ライブラリを使用する必要があります (または、ライブラリ自体を実装する必要があります。これはナンセンスです。bignum の優れたアルゴリズムは理解しにくく、実装するのが難しいため、既存のライブラリを使用することをお勧めします)。

PS。long longまだ64ビットなので、あまり役に立ちません。一部の GCC コンパイラとターゲット プロセッサは__int128、つまり 128 ビット整数をサポートしている場合がありますが、実際には bignum が必要です。

于 2012-10-21T17:06:45.710 に答える
1

除算時に階乗を完全に評価する必要はありません。これにより、整数オーバーフローのリスクが軽減されます (効率が向上します)。

long factorialDivision(int topFactorial, int divisorFactorial)
{
    long result = 1;
    int i;
    for (i = topFactorial; i > divisorFactorial; i--)
        result *= i;
    return result;
}

long factorial(int i)
{
    if (i <= 1)
        return 1;
    return i * factorial(i - 1);
}

long nPr(int n, int r)
{
    // naive: return factorial(n) / factorial(n - r);
    return factorialDivision(n, n - r);
}

long nCr(int n, int r)
{
    // naive: return factorial(n) / factorial(r) * factorial(n - r);
    return nPr(n, r) / factorial(r);
}
于 2015-04-09T13:31:12.497 に答える