重複組合，計算差異

我有一個小程序。我必須重複計算組合。
我的代碼：重複組合，計算差異

int factorial(int a){ 

    if (a<0) 
    return 0; 
    if (a==0 || a==1) 
    return 1; 
    return factorial(a-1)*a; 
} 
long int combinationWithRepetion(int n, int k){ 
    long int a,b,wyn=0; 

    wyn=factorial(n+(k-1))/(factorial(k)*factorial(n-1)); 

    return wyn; 
} 
int main() 
{ 
    int k,n=0; 
    cout<<"Give n: "; 
    cin>>n; 
    cout<<"Give k: "; 
    cin>>k; 
    cout<<"combination With Repetion for n="<<n<< 
    " k="<<k<<".\n Is equal to "<<combinationWithRepetion(n,k)<<endl; 
    return 0; 
}

對於n = 9，K = 6沃爾弗拉姆的阿爾法我拿到3003，但在這個程序的結果是44

對我的代碼是好的。

來源

2011-11-06 Błażej

你會相信誰？ Wolfram Alpha或你的代碼？ –

@MitchWheat，他自己的代碼，顯然！ – Marlon

@MitchWheat，但你對代碼的想法，也許我想念什麼？ –

隨着n=9和k=6你計算factorial(14)這是87,178,291,200這將溢出4字節int。如果你想使用這個公式，你需要使用像long long這樣的東西來得到一個8字節的int。

有計算不依賴於計算階乘滿然後做除法二項式係數更好的公式。見Binomial coefficient in programming languages，直接方法（而不是遞歸）。

在C++中可以使用：

int binomial(int N, int K) { 
    if(K > N - K) 
    K = N - K; 
    int c = 1; 
    for(int i = 0; i < K; ++i) { 
    c *= (N - i); 
    c /= (i + 1); 
    } 
    return c; 
}

來源

2011-11-06 07:47:46 JohnPS

在一個長64位的平臺上，對「long long factorial（long long a）」的單行更改足以使其工作。 –

@DavidSchwartz該死的，謝謝:) –

@大衛·施瓦茨 - 這將工作，但由於階乘長得很快就會溢出了'階乘（21）'，所以我加了鏈接到一個更好的方式來計算二項式係數不計算第一個階乘。 – JohnPS

那麼，你是計算（N + K-1）選擇k。取消n = 9，k = 6，它是14選擇6（= 3003）。但是14！需要超過36位來表示，但你的int只有32位。更好的實現是簡化N！/（（N-K）！ķ！）到n（N-1）...（N-K + 1）/ K！或者你可以使用pascal三角形。

來源

2011-11-06 08:05:34 FiniteA

重複組合，計算差異

回答

相關問題