É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}\]
Exercice
Coder une fonction nb_catalan qui prend un entier n en paramètre et qui renvoie le nombre de Catalan d'indice n après avoir complété, si besoin, la liste des résultats mémorisés catalan_mem.
Il est important d'effectuer la division en dernier, et que son résultat soit un entier.
- Contraintes
-
- \(0 \leqslant n < 2048\)
- Fonction récursive interdite
- Modules
mathetfunctoolsinterdits - Code source limité à 2000 caractères
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 x/.r;nbylae%u)*d63×Am(P+02è-U],59fq!7B}8 N_o={pcwgv41`kRéhtsSàLC[i:E 050q0l0+0k0=0j0,0P0W0j0k0,0,0T010+0=0V010406050,0n0v0v0k0e0i040-0S0j0n180S0g0P020k0v0V0f0P0(0l1i0e0J0n0l0,050c1f1h1j1l1d0V04051Q1J1T0c1Q1d0q0=0Z101214160*0=0Y0*0j1+0*0+1b050{0h0j0l1$1315011*1,1.1,0+1@1_1=0+0e1R0+0*1{1(010I0}0l0g1w0l01101o0,0V0k0g160A1=2o2q2c1}2f1_2i0v2k040a0P0x0e0S0V0S0,0=1r1t0_2m0e0e0l0W2O1J2v0g1R0c2a2!2729281?0q2x161.0g2h2L1=1Z1#111|2.0=2:0g0S2@1=0V2T1R2Y2!351e2p1t2_2d2~0e1i0j1b0P0#2X391c382w3b1}3d3f3h0A3k2q3m2Y2-013r0k3g040P0s3v2Z1d3y3p163B3D0P0!3H3x393z3N3h0G3R3J3T3L3A0S3e3C3h0r3Y3n3a1%3q3%3s3E0L3,3K3/3M3;3)3E0O3^3!3`3$3(3O0H403o423V040#0z473.2`433=0#3j1K3l1U331J2@2%0q292,3#0W2 2D0^1!1R320l344m4l3w054w0_4E484g0g1b0W0k0{120g0R2C0v3R0P3-3z0S1b0T4Y4!3#1a040;3R4*420v0=1b4k373_4g4,0E3Y3Z4M2d0%1b0_0I4/4`2d0X3h56414N0I1b0g0h0R4Q4S2q5b501}4,0w5m4f3c5f5r3z4,0o0?4e3z593E0P5E5v3#0,0q1b015L5A5H5J5D5E0:0S1x0j0B0+0l0F0P2M0P0h1H0S2|5Z120P1.0,5X0P0$5j3C2q4V1C0$5N425I3h5E1A2h0Z5)1`5?4T5_0v0;0g0E0P0?5-1`2~0v0h2T0P2Q0:4R5@2P002|1Z0W6g5|4g5~5Q0P5L013Y604Z571}52040I3%4)6G3M1b0%6M5c2d0S5C2|6R5n3M0h1b0e2q0Y0l5G425p6*4N6!042A6-2d6,4G2Z4:4N4P6o674W6=5o1b0o0F6X5s3q5u6^3E6`6T1b0y753z4=4@70165x5z79066E6E7b77040W0R6Q796F6S1}4$044(7x7r6O7t6}5^6 797F014,4.7L6N3A6P7f3#7B0C7U4;4?4b7j7N1b4}7E7R7B0p7Y4g7h043u7*7z167,7.6?1b5q7Q7@017:7=357y6Y017_7?854O047w837M7W7`1}7:4^4m7R5x8g7^1b0c0c8n7%047}4_7 8a8c3l84768o047e888C807!8j4H8l726D7p5F7R8a667J1C7$7B0d7$8a0k0V0V2h0q7$6@8w894P7v8*8N7n7q7R6I2T0+0n0e0g8s8S7I4U7K8,8H7O8Z78935w7(3,0c4J4D4n9e0c4q1J0+4s9j2*2#0k1^9g4q1P4L8H2T0v0R0I0k0%0l0R0*0s1b1B1D1F1H6d4/1W3m2@3z0k0q0v1s2N0=1s0P2~5X1b1P9Q9S9U2O0C180+25042H0l0n0Z1`2Q5,6K3e0n1_1U9O1!9Q0e2N0*1i5X0b1b090;0:0R1t0T0P095%0Y2|0U4Q0,1H0N060#8Parasat5E1v1x1z091F9Rafa60+0U5!0=0P0N9Y0Pae0z090906ab0U0g0C0#0N0t090q0I6$0W0U0A0w0A1t0C3i0o0NaS0P0y3iaJ1u1w1yafaA2,09aDaF5#aJ1t020Y0+1zaNaP098(ak13an097)9s1S040Q0S0n0 9T0g271s0 0=0WaH0n2:0P2p0e181`am9|1C2h0+6l1`5,4C9=0l0d0P0/0k5!0n2NbC0l6$6l2q0 bw0P0k1q6k0l0bbWbu6u8Y9N9tbkbmby1j182I0g0 0q0n0P9z2N0P0w9R4=0,0o0P9J8Ba1a3a5b*a80wabadafaZa#0Ua)0g0o0Ka/0w0g0y0#cp0gcq090o4Y2K8{ca3#1jcc4Rce0409cs096(0J0,4TbHaNcA79b/1X059|3m1.9/bl0ecE42cG2acda7cKcsaL0PcT3R5Z9XbR0h0=2hc)4gc+a4cIc.cLab0zc;aYa!0ka$0zcq0U0#0KdcaJaed8a#4j0T0#cz9Mc#1dc#0xc%c~2dd0c-cf0gb4b6c?79c^1tbR7Mdyd2cfaRaTaVd7ckdacma*0C0AcpcrdOcwcycU355Z2Q0,3%5:9JcY0jc!0=9ucbc,dLc/dNaUaJ0tcjd9a$cn0o0tcnaUa.aScscua.dQd dTcodde8cv0Kcxdi0Pchdp7L0cdr05c#dJa2d@a6dM0RaSd{0Pd}dkdS0Ae3dUcva/ctdPaeemd$4Feq0ccZ1depd;eTeS051^0S0W0%1F0S5X3m1QducD9_3;bE6ddw1}dKewd_acebcle1efeKd!0Nen83cCc(etcHe^cL0gcN0lcPcRc=f23lcWe*040DdHb(1`b*b,btbVbX4wb{da0e0)0P0.100l12fieTeZe#e%e)eTbh9PcF9(0g9V9XfI2D9$fNbofQaT9,9.0:9|8`2T9~9t05bR0*2T0I1)230V0,0?8qa!0d0X0=0%190l1Z0k0d3%0Y0cf{f}0c0@0n0Y0m0:0s0m0u0O2:0R0:0*1j1_0,gj901bg90Y0Bbxgkgm9K6n5k8}0c0k045Z0gfy1_3Fd61iaH0#0O0#0!fz0P0M0ega9K0`0P9TbA6f3igQ0I0)0Za2bW3i0O0HgQfA0/0=0B6(5Z1HbHb#a50*0)a5btc|1td90g4w0C5%0jg^5!0V0)bu3C0=5/9@bJbR2a0)3%c|bI0 6h6j1HfE4p4AfK0`0|0~04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)