3

我写了一个函数来计算 C 中两个数字的 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;
        }
     }

谢谢

Ĵ

更新：这些是没有重复的排列，

我也试过

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

您可能想使用bignums进行计算，也许使用GMP库。如果你切换到 C++，你a+b甚至可以使用熟悉的符号，使用C++ 类接口到 GMP。如果您停留在纯 C 语言中，则需要小心使用特定的例程，例如mpz_add进行加法。

顺便说一句，某些语言（例如Common Lisp）本机支持 bignums（无需修改处理普通数字的源代码）。您可能想尝试使用SBCL（至少在 Linux 上）。

当然，bignum 算术（一门非常复杂的学科）比原生算术要慢。

C 本身不支持 Bignums，你需要使用一个库（或者实现你自己的库，这是无意义的：bignums 的好的算法很难理解和实现，所以最好使用现有的库）。

PS。long long不会有什么帮助，因为它仍然是 64 位。一些 GCC 编译器和目标处理器可能支持__int128即 128 位整数，但您确实需要 bignums。

于 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 回答