Soit {E} un ensemble muni d’une relation d’ordre {\preceq (}partielle ou totale). On dit que {(E,\preceq )} est « bien fondé » si les conditions équivalentes suivantes sont vérifiées :
- il n’existe pas de suite infinie strictement décroissante d’éléments de {E}
- toute partie non vide {A} de {E} admet au moins un élément minimal {a,} c’est-à-dire tel que {\forall x\in A,(x\preceq a\Rightarrow x=a)}
Soit à calculer {f(x),} où {f} est une fonction et {x} un élément d’un ensemble {(E,\preceq )} bien fondé. La mémo ̈ization est une technique d’optimisation du code informatique qui consiste à stocker en mémoire, au moins provi- soirement, les résultats {f(x^{\prime })(}avec {x^{\prime }\preceq x)} qui sont utiles au calcul de la valeur {f(x).}
7.2.1 Retour aux coefficients du binôme
La fonction tpascal renvoie le triangle de Pascal (pour les lignes de 0 à {n)} sous la forme d’un tableau de tableau d’entiers.
|
1 2 3 4 5 6 7 8 9 |
let tpascal n = let t = Array.make (n+1) [|1|] in for i = 1 to n do t.(i) <- Array.make (i+1) 1; for j = 1 to (i-1) do t.(i).(j) <- t.(i-1).(j-1) + t.(i-1).(j) done; done; t;; val tpascal : int -> int array array = <fun> |
|
1 2 3 4 5 6 7 8 |
tpascal 5;; - : int array array = [|[|1|]; [|1; 1|]; [|1; 2; 1|]; [|1; 3; 3; 1|]; [|1; 4; 6; 4; 1|]; [|1; 5; 10; 10; 5; 1|]|] |
On en déduit une fonction tcnp assez évidente de calcul de {\binom{n}{p}:} let tcnp n p = (tpascal n).(n).(p);;
Si on ne recherche que la ligne d’indice {n} du triangle de Pascal, on peut optimiser la complexité spatiale de la fonction tpascal. On écrit pour cela une fonction lpascal renvoyant seulement la ligne d’indice {n.} Dans la fonction lpascal, on notera (et on en comprendra la raison) que la boucle est de type downto.
|
1 2 3 4 5 6 7 8 9 |
let lpascal n = let t = Array.make (n+1) 0 in t.(0) <- 1; for i = 1 to n do for j = i downto 1 do t.(j) <- t.(j-1) + t.(j) done; done; t;; val lpascal : int -> int array = <fun> |
|
1 2 3 4 5 6 7 8 |
lpascal 6;; - : int array = [|1; 6; 15; 20; 15; 6; 1|] lpascal 7;; - : int array = [|1; 7; 21; 35; 35; 21; 7; 1|] lpascal 8;; - : int array = [|1; 8; 28; 56; 70; 56; 28; 8; 1|] lpascal 9;; - : int array = [|1; 9; 36; 84; 126; 126; 84; 36; 9; 1|] |
On en déduit une fonction lcnp assez évidente de calcul de {\binom{n}{p}:} let lcnp n p = (lpascal n).(p);;
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres