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)); } } |
Accueil > Les algorithmes récursifs >
