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)ことがわかります。したがって、100C97 = 100x99x98 / 3x2x1 = 100x33x49 です。rn

次に、因子一致アルゴリズムを考えてみましょう (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 ペアの可能なスペースを最大化します。fただし、書かれているように、整数の約数をすべて取得するコストは O(n^3 * f) であるため、高速ではありません。ただし、n と r の値が大きい場合は、異なる型を使用せずに結果を計算する唯一の方法になる場合があります。

于 2014-11-21T12:34:12.410 に答える