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 \(C_n\) que l'on peut calculer, par exemple, avec la formule suivante :

\[C_n = \begin{cases} 1 & \quad \text{ si } n = 0\\ C_{n-1}×\dfrac{2(2n - 1)}{n + 1} & \quad \text{ si } n > 0\\ \end{cases}\]

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\) et catalan_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 :
🐍 Script Python
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

🐍 Console Python
>>> catalan(2)
2
>>> catalan(3)
5
>>> catalan(5)
42
###
# 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-nlNone

A

Z

Retour en haut de la page