Le binome de newton C(n,p)

Voici une implémentation du calcul du Binome de newton, par 2 méthodes l'une brute et l'autre optimisé.

/**
 * Calcul du binome de newton par la définition suivante
 * C(n.0)=C(n,n)=1 et C(n,p)=C(n-1,p)+C(n-1,p-1)
*/
public class BinomeNewton {
    static long C[][];
    /**
 * Version pas efficace du tout! pourquoi?
 */
public static void initC(int n) {
C=new long[n][n];
for (int i=0; i < n; i++) for (int j=0;j < n; j++) C[i][j]=-1;
}
public static long calculCBrute(int n, int p) {
if ((p==0) || (p==n)) return 1;
else return (calculCBrute(n-1,p)+calculCBrute(n-1,p-1));
}
/**
 * Version améliorée utilisation de mémorisation
 */
public static long getC(int n, int p) {
   /* La valeur est déjà calculé? retour direct */
if (C[n][p] != -1) return C[n][p];
//Sinon faire le calcul et stocker la valeur
else return (C[n][p]=calculC(n,p));
}
public static long calculC(int n, int p) {
if ((p==0) || (p==n)) return 1;
else return (getC(n-1,p)+getC(n-1,p-1));
}
/**
 * Pour voir la différence entre les 2 méthodes essayez
 * java BinomeNewton 100 50 b
 * et
 * java BinomeNewton 100 50 o
 */
public static void main(String a[]) {
int n = Integer.parseInt(a[0]);
int p = Integer.parseInt(a[1]);
char mode = a[2].charAt(0); //Mode b : brute, o : pbtimisé
if (mode == 'o') {
initC(n);
System.out.printf("C(%d,%d)=%d\n",n,p,calculC(n,p));
} else System.out.printf("C(%d,%d)=%d\n",n,p,calculCBrute(n,p));
}
}
ċ
BinomeNewton.java
(1k)
Pascal Fares,
22 juil. 2011 à 02:39
Comments