Coefficient binomial en Java (adaptant la source suivante)

Question

J'ai 2 paramètres et je veux que la méthode retourne un résultat int .. J'ai reçu ce code mais je ne comprends pas tout à propos de binoms etc et je ne sais pas comment le "convertir" a double BC[126][126]; défini quelque part au-dessus. Mais je n'ai pas besoin que je veux juste un résultat pour ces n et m. (Je sonne probablement comme numpty pour mettre comme ça)

private void binom(int n, int m) { 
    int i, j; 

    if (n>=0) 
     if (m>n||m<0) System.err.println("Illegal m!!\n"); 

     else { 
      for(i=0;i<=n;i++) BC[i][0] = 1; 
      for(i=1;i<=m;i++) BC[0][i] = 0; 
      for(j=1;j<=m;j++) for(i=1;i<=n;i++) 
       BC[i][j] = BC[i-1][j-1] + BC[i-1][j]; 
     } 

    else System.err.println("Negative n!!\n"); 
} 

Answer 1

Vous pouvez tout simplement revenir BC[n][m] qui est l'élément que vous calculez avec les trois cycles pour ..

par la façon dont vous avez au moins trois implémentations possibles :

• récursif trivial
• celui-ci (programmation dynamique)
• en utilisant la formule n!/(n-m)!m! ce qui est pas bon car les opérations de fait sont ennuyeux

Une correction: votre approche serait la programmation dynamique si vous évitez de recalculer tous les coefficients à chaque fois que la méthode est invoquée, mais ce n'est pas votre cas ..

Answer 2

voir l'article Computing Binomial Coefficients un exemple avec une complexité comparable, O (n), mais en utilisant seulement O (n) espace au lieu de O (n).