Triangle de Pascal
Formule du coefficient binomial dit du triangle de Pascal, avec $1\leq k \leq n$ :
et :
On a déjà vu l'approche récursif. Passons à l'approche itérative.
V1
Créez un algorithme rendant une matrice triangulaire inférieure $B$ telle que $B[n][k] = \binom{n}{k}$.
Sa signature devra être :
algorithme binom_matrice(n: entier) → [[entier]]:Vous pourrez créer itérativement chaque ligne en utilisant la ligne créé à l'itération précédente pour créer la ligne actuelle.
Utilisez l'algorithme binom_matrice(n: entier) → [[entier]] pour créer l'algorithme itératif de signature :
algorithme binom(n: entier, k:entier) → entiercalculant $\binom{n}{k}$.
Donnez-en sa complexité spatiale et temporelle.
V2
Comme l'algorithme binom_matrice(n: entier) → [[entier]] n'a besoin que de la ligne précédente pour créer la ligne de l'itération actuelle, on peut améliorer la complexité spatiale de l'algorithme binom(n: entier, k:entier) → entier :
Créez l'algorithme ligne_suivante(l: [entier]) → [entier] qui à partir de la liste $l= [\binom{n}{0}, \dots, \binom{n}{n}]$ rend la liste $[\binom{n+1}{0}, \dots, \binom{n+1}{n+1}]$
Donnez-en sa complexité spatiale et temporelle.
Utilisez l'algorithme ligne_suivante(l: [entier]) → [entier] pour améliorer la complexité spatiale de l'algorithme binom(n: entier, k:entier) → entier.
Enfin, pour calculer binom(n: entier, k:entier) → entier on a pas besoin de toute la ligne de la matrice :
Modifiez l'algorithme ligne_suivante pour le rendre de signature ligne_suivante(l: [entier], k: entier) → [entier] tel que si $l= [\binom{n}{0}, \dots, \binom{n}{\min(k, n)}]$ rend le tableau $[\binom{n+1}{0}, \dots, \binom{n+1}{\min(k, n+1)}]$.
Utilisez le dans binom(n: entier, k:entier) → entier pour que sa complexité spatiale soit en $\mathcal{O}(k)$.
v3
Il faut 2 tableaux de taille au plus $k$ pour faire fonctionner l'algorithme précédent. On peut faire mieux !
On va ici utiliser des listes car on va chercher à modifier et à faire grandir le paramètre d'entrée, ce qu'on ne peut pas faire avec un tableau.
En remplissant la ligne courante de droite à gauche montrez que l'on peut modifier ligne_suivante pour le rendre de signature ligne_suivante(l: Liste<entier>, k: entier) → [entier] telle que si $l= [\binom{n}{0}, \dots, \binom{n}{\min(k, n)}]$ en entrée, elle est modifiée en la liste $[\binom{n+1}{0}, \dots, \binom{n+1}{\min(k, n+1)}]$.
Utilisez le dans binom(n: entier, k:entier) → entier.
Cette dernière optimisation ne change pas la complexité spatiale en $\mathcal{O}$, elle ne fait que la diminuer par 2. Cette optimisation est cependant significative si $k$ est grand.