Combinaison avec répétition, différences de calcul

Question

J'ai un petit programme. Je dois calculer la combinaison avec la répétition.
Mon code:

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; 
} 

Pour n = 9 et k = 6 Wolfram alfa Je reçois 3003, mais dans ce programme est le résultat 44.

Pour moi, le code est très bien.

Answer 1

Avec n=9 et k=6 vous factorial(14) qui est Calculons 87,178,291,200 qui débordera un 4 octets int. Vous devez utiliser quelque chose comme long long pour obtenir un int de 8 octets si vous voulez utiliser cette formule.

Il existe de meilleures formules pour calculer les coefficients binomiaux qui ne reposent pas sur le calcul des factoriels complets qui effectuent ensuite la division. Voir Binomial coefficient in programming languages, la méthode directe (plutôt que d'utiliser la récursivité).

En C++, vous pouvez utiliser:

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; 
} 

Answer 2

Vous calculez (n + k-1) choisir k. Substiuer n = 9, k = 6, c'est 14choix6 (= 3003). Mais 14! prend plus de 36 bits à représenter, mais votre int a seulement 32 bits. Une meilleure mise en œuvre serait de simplifier n!/((N-k)! k!) À n (n-1) ... (n-k + 1)/k !. Ou vous pouvez utiliser le triangle pascal.