É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.
- On complètera le code :
catalan_mem = [1]
def catalan(n):
i = len(catalan_mem)
while n >= i:
catalan_im1 = ...
catalan_i = ... // (i + 1)
catalan_mem.append(...)
i = ...
# ici n < len(catalan_mem)
return ...
Exemples
>>> catalan(2)
2
>>> catalan(3)
5
>>> catalan(5)
42
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-nlNone
A
Z