Énumération des expressions bien parenthésées⚓︎
Expression bien parenthésée
Une expression bien parenthésée est une chaine de caractères composée d'autant de (
que de )
et où chaque parenthèse ouvrante est placée avant la fermante qui lui correspond.
()(())
et((()))()
sont bien parenthésées)()(
et())(()
ne sont pas bien parenthésées.
- Pour \(2\) paires de parenthèses, il y a \(2\) expressions bien parenthésées.
()()
(())
- Pour \(3\) paires de parenthèses, il y a \(5\) expressions bien parenthésées.
()()()
(())()
()(())
(()())
((()))
On admettra que le nombres d'expressions bien parenthésées contenant \(n\) paires de parenthèses est le nombre de Catalan \(C_n\) que l'on peut calculer, par exemple, avec la formule suivante :
Objectif : Écrire une fonction telle que catalan(n)
renvoie le nombre de Catalan d'indice n
.
- On utilisera la liste
catalan_mem
pour conserver en mémoire les résultats, ce qui permet un accès ultérieur sans calcul. - On utilisera la variable
catalan_i
pour désigner \(C_i\) etcatalan_im1
pour désigner \(C_{i-1}\). - On sera capable de justifier à l'oral le commentaire placé dans le code.
Exemples
>>> catalan(2)
2
>>> catalan(3)
5
>>> catalan(5)
42
Code à compléter :
catalanpy-undmem = [1]bksl-nlbksl-nldef catalan(n):bksl-nl i = len(catalanpy-undmem)bksl-nl while n >= i:bksl-nl catalanpy-undim1 = ...bksl-nl catalanpy-undi = ... // (i + 1)bksl-nl catalanpy-undmem.append(...)bksl-nl i = ...bksl-nl # ici n < len(catalanpy-undmem)bksl-nl return ...bksl-nlbksl-nl# testsbksl-nlassert catalan(2) == 2bksl-nlassert catalan(3) == 5bksl-nlassert catalan(5) == 42bksl-nlbksl-nlbksl-nlcatalanpy-undmem = [1]bksl-nlbksl-nldef catalan(n):bksl-nl i = len(catalanpy-undmem)bksl-nl while n >= i:bksl-nl catalanpy-undim1 = catalanpy-undmem[i - 1]bksl-nl catalanpy-undi = catalanpy-undim1 py-str 2 py-str (2py-stri - 1) // (i + 1)bksl-nl catalanpy-undmem.append(catalanpy-undi)bksl-nl i += 1bksl-nl # ici n < len(catalanpy-undmem)bksl-nl return catalanpy-undmem[n]bksl-nlbksl-nlbksl-nl# testsbksl-nlassert catalan(2) == 2bksl-nlassert catalan(3) == 5bksl-nlassert catalan(5) == 42bksl-nlbksl-nlbksl-nl
A
Pour un appel de catalan(n)
deux cas peuvent se produire.
n
est plus petit que la longueur de la liste, alors le résultat est déjà stocké, il suffit de renvoyercatalan_mem[n]
.n
est supérieur ou égal à la longueur de la liste. On va alors faire grandir cette liste en utilisant la formule de récurrence, tant que nécessaire. On se retrouve alors dans le cas 1.
Preuve de la formule⚓︎
Nous montrons ici une partie seulement de la preuve. La suite sera dans un autre exercice.
Nous partirons du fait (admis) que \(C_n = \dfrac{(2n)!}{(n+1)!n!}\) pour \(n\geqslant 0\).
- Pour \(n = 0\), on a bien \(C_0 = \dfrac{0!}{1!0!} = \dfrac11=1\)
- Pour \(n>0\), on a \(C_{n-1} = \dfrac{(2n-2)!}{(n-1)!n!}\), de sorte que
- \(C_{n-1} × \dfrac{(2n)×(2n-1)}{n(n+1)} = \dfrac{(2n)!}{(n+1)!n!} = C_n\)
- \(C_{n-1} × \dfrac{2×(2n-1)}{n+1} = C_n\)
Pour la formule : \(C_n = \dfrac{(2n)!}{(n+1)!n!}\) pour \(n\geqslant 0\).
Un autre exercice sera consacré à cela.
Variante sans while
⚓︎
catalan_mem = [1]
def catalan(n):
for i in range(len(catalan_mem), n):
catalan_im1 = catalan_mem[i - 1]
catalan_i = catalan_im1 * 2 * (2*i - 1) // (i + 1)
catalan_mem.append(catalan_i)
# ici n < len(catalan_mem)
return catalan_mem[n]
Culture⚓︎
Eugène Charles Catalan, né le 30 mai 1814 à Bruges et mort le 14 février 1894 à Liège, est un mathématicien franco-belge, spécialiste de la théorie des nombres.
Z