1

这是一个非常简单的程序，有 t 个测试用例，我们必须找到 nCr=n!/r!*(nr)!。所以它适用于较小的值，如 20C2，但不适用于较大的值，如 100C10。它给出 32C2=-6 ,100C10 浮点异常。如何使它为 1<=n<=r<=1000 ?? 注意：我不是要求 long double 或不想将其更改为 float。答案应该类似于 100C10 = 17310309456440 类似 989C45=?

#include<iostream>
using namespace std;
long long int fact(long long int num);
int main()
{
int t;
cin>>t;
long long int n[1000],r[1000],c[1000];
for(int i=0;i<t;i++)
{
cin>>n[i];
cin>>r[i];
}
for(int i=0;i<t;i++)
{
c[i]=fact(n[i])/(fact(r[i])*fact(n[i]-r[i])) ;
cout<<c[i];
}
return 0;
}
long long int fact(long long int num){
long long int k;
if(num==0)
num=1;
else
{
for(k=num-1;k>0;k--)
num=num*k;
}
return num;
}
4

2 回答 2

1

是时候接触一下数学了：

nCr = fact(n)/(fact(r)*fact(n-r))

一个例子使这更容易，让我们做 5C3：

5C3 = fact(5)/(fact(3)*fact(5-3))
    = fact(5)/(fact(3)*fact(2))
    = 5x4x3x2x1 / (3x2x1 * 2x1)
    = 5x4 / 2x1

所以我们可以看到一些因素会抵消；fact(n)如果完全溢出，这将非常有用。

定义一个范围阶乘：

rafa(a,b) = a*(a-1)*...*(b+1)*b where a > b
          = product(b..a)

然后

rafa(n,r) = fact(n)/fact(r)
-> nCr = rafa(n,r) / fact(r)

我们可以在这里停下来，我们将显着扩大我们可以计算值而不会溢出n的值的集合。r

加分

使用rafa(n,r)和fact(r)，我们可以看到，当r几乎与 一样大时n，则问题的大部分规模将取消。所以 100C97 = 100x99x98 / 3x2x1 = 100x33x49。

那么，考虑一个因子匹配算法（伪代码，很像 python）：

numerElems = [100,99,98]
initialDenomElems = [3,2,1]

# cancelFactors modifies numerElems values, returns un-cancelled denominator elements
def cancelFactors(numerElems, denomElems):
    finalDenomElems = []
    for denom in denomElems:
        for factor in factorise(denom):
            for idx,numer in enumerate(numerElems):
                if isFactorOf(factor, numer):
                    numerElems[idx] = numer/factor
                else
                    finalDenomElems.push(factor)
    return finalDenomElems;

然后，您可以执行分子元素的乘积除以剩余分母元素的乘积的最终计算。因为我们知道 nCr 总是返回一个整数结果，所以我们知道当使用 cancelFactors 时它总是会取消所有的因子。因此，该算法最大化了不溢出的 n,r 对的可能空间。然而，正如写的那样，它是 O(n^3 * f)，其中f是获取整数的所有因子的成本，所以它不会很快。但是，对于较大的 n 和 r 值，它可能是在不使用不同类型的情况下计算结果的唯一方法。

于 2014-11-21T12:34:12.410 回答
0

你有两个选择：

  1. 使用多精度库，例如 Boost 提供的库：

http://www.boost.org/doc/libs/1_53_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/egs/factorials.html

  1. 尽可能简化表达式。只要您的值仍然很小，这将起作用。看看分子和分母？你能在那里简化一些事情吗？当您改变 N 和 R 时，值如何变化？在某些情况下，这些部分结果中的一个较小。尝试将其用于您的优势。
于 2014-11-21T11:09:21.900 回答