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 paires de parenthèses, il y a expressions bien parenthésées.
()()
(())
Pour paires de parenthèses, il y a expressions bien parenthésées.
()()()
(())()
()(())
(()())
((()))
On admettra que le nombres d'expressions bien parenthésées contenant paires de parenthèses est le nombre de Catalan 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 et catalan_im1 pour désigner .
On sera capable de justifier à l'oral le commentaire placé dans le code.
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
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 renvoyer catalan_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.
catalan_mem=[1]defcatalan(n):foriinrange(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)returncatalan_mem[n]
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.