Aller au contenu

É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 Cn que l'on peut calculer, par exemple, avec la formule suivante :

Cn={1 si n=0Cn1×2(2n1)n+1 si n>0

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 Ci et catalan_im1 pour désigner Ci1.
  • On sera capable de justifier à l'oral le commentaire placé dans le code.

Exemples

🐍 Console Python
>>> catalan(2)
2
>>> catalan(3)
5
>>> catalan(5)
42

Code à compléter :

###
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 ...
# tests
assert catalan(2) == 2
assert catalan(3) == 5
assert catalan(5) == 42
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
# testsbksl-nlassert catalan(2) == 2bksl-nlassert catalan(3) == 5bksl-nlassert catalan(5) == 42bksl-nlbksl-nl# autres testbksl-nlbksl-nlassert catalan(8) == 1430bksl-nlassert catalan(6) == 132bksl-nlbksl-nlbksl-nlA000108 = [bksl-nl 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,bksl-nl 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700,bksl-nl 1767263190, 6564120420, 24466267020, 91482563640, 343059613650,bksl-nl 1289904147324, 4861946401452, 18367353072152, 69533550916004,bksl-nl 263747951750360, 1002242216651368, 3814986502092304,bksl-nl]bksl-nlbksl-nlfor i, resultat in enumerate(A000108):bksl-nl assert catalan(i) == resultat, f"Erreur avec i = {i}"bksl-nlbksl-nl 5/5

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