Nombres de Catalan (1)
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 nombre 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 catalan qui prend en paramètre un entier n et qui renvoie le nombre de Catalan d'indice n.
- On utilisera la liste
catalan_mempour conserver en mémoire les résultats, ce qui permet un accès ultérieur sans calcul. - On utilisera la variable
catalan_ipour désigner \(C_i\) etcatalan_im1pour désigner \(C_{i-1}\). - On sera capable de justifier à l'oral le commentaire placé dans le code.
Exemples
>>> catalan(2)
2
>>> catalan(3)
5
>>> catalan(5)
42
Code à compléter :
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
.9875.128013.65038 4EA2nygN )rPCq-;joàè{*u5(é:,V!st]h07w+8f/U6×3pOv1x=a_%ckm}iLBeS9l[Rb.d 050{0:0I0$0-0?0H0l0)0?0$0H0H0#010I0-0W010406050H0z0+0+0$0n0i040;0u0?0z1c0u0h0l020$0+0W0s0l0^0:1m0n0q0z0:0H050R1j1l1n1p1h0W041N1U051X0R1X1Z1U1h0{0-0Y1416181a0K0-0j0K0?1;0K0I1f050 0_0?0:1,1719011:1=1@1=0I1}1 1{0I0_0u0{1p1|0n1V0I0K141s0H0W0$0h1a0g01211.010Q110:0h1A0:1{2p2r2w232z1 2C0+2E040b0l0o0n0u0W0u0H0-1v1x0}2n0n0n0:0)2Z1N2G0h1V0R2l2/0I2j2i2k0{2I1a1@0h2B2W1{1)1+15222|0-2~0h2f1*1{0W2(1V2-2/3g1i2q1x342x390n1m0?1f0l0Z2,3k1g3j2H3m233o3q3s0g3v2r3x2-2{013C0$3r040l0V3G2.1h3J3A1a3M3O0l0d3S3I3k3K3Y3s0A3$3U3(3W3L0u3p3N3s0T3-3y3l1-3B3=3D3P0M3`3V3}3X3 3@3P0P433/453;3?3Z0=4b3z4d3*040Z0L4i3|354e400Z3u1O3w3.4j4r4l0Z3F4w3H1W3e1N322=0{2_3K0)2f2O0|1*1V3d0:3f3w3$054O0}4W4z3n1f0)0$0 160h0%2N0+3$0l3{3K0u1f0#4=4@3:1e040@4Y444r0+0-1f4v3i532x4 0J3-064y4q2x0*1f0}0Q524c4r0N3s5n4%3B0Q4)4+3N2r5s5h234 0B5A3)1f0h5F4~1f0m0D3-0l5P4?5a3B1f0-4|5S1a4_044{4E2.5R5o3n0_1f2L5J4d5D5.4A5w4,2r4/1G5;5b5L5O5Q4}4d5j040N1:1 5W5)5T045I5$3P604r5Z020j0I0s5#3g5(5t3X5U5{5C1f5N6c065Q6x6n5B6p044*5@4.0-0+583w6z4^4`676o3L5?5y4.4:6r1a4 516c6e4(045V6c6K3:5Z0r6N6A0155576U015c5~6y6(4k6Q4-0%6$6m6Z235Z6l6J706B6D6R6}6H6,6L040y7b3:6/044D6 5X015Z7e6%756=1f5E6Y7l7h7j747l7n7f6`6#7B6f1f6+7p7v564m6;4 0m7E2x5Z0R0R7P6s047t59686B6~7y7Z7m1f0O7U1a7h6I4F7l7N6@6y7q0h6{5^6T7u7%5Z0`6;7^040$0W0W2B0{7M7s807_6F88047O6v6^5P7@6q7I7}7)733H6_547K7.3T6x7q0)0Z1f030l0-0)0-0l1x020?6j0l2L0B776|4:8f3g6w5 7l622(0I0z0n6b7k7%818N7`5`7|6O6W8a6a8d5d6v1N4!4V4G8^0R4J1N0I4L8}2@2:2e2g2=0$1~8`4J1T4$6-2(0+0%0Q0$0*0:0%0K0V1f1F1H1J1L0l6u3i1!3x1U0o0u8Y0l0z1x83850?0l2#4Z4P6C5x4-0B0h8f8@3P0}0z0!14170l850z0Y2B0I0l0H203d2f0z0-2(7 9v1h1s3x1@1V9R6b9R0l1L9%0W1t13851c9%9q8K0$8K1w0j1K9A2#168K0-0H0I0:0E0l3N3=131 0l0n0C1j8I4+9}ai9H0C0t0v9(0I0u0)0*0Cal119(0z0Q2z9%2#2(0h0Y0u0i0:0n4?9R8(6S1G0@0h8;9R9:9^1h9^9J4#9{9Kax9%1j0W0C0n0-0:9A9z0l0C0j3N0laCaf0?aaacaXaea81@ai0:0`0l0X1x0Ya8an0n139g9.200j0n2r1)aX0)0~ajagbe9}1x1u11ah2r9%af0Q3 0zaqaQ0C0)8YaRbxal0 0ha51K8FbP1L0H109/bh1x9)ar0~2T9!20bm130{2rap204*130Za+0-3x0R9?1h0K0Z8B0{6V2(b/0r0}0r160rbK3pbM2O2Sa}9#9H20bJbL66a83:0K0:0$0}0n2}5j0l0K2(0Q1a034Uc9cbcdcf0+ch2va41 1a0oaW1m38bI37620a0c1N0$2/c33x323K1n2Y0K1maj0!1f090@0p0%1x0#0l090_0:0j370xb`1L0,06c48hd7d88h1z1B1D091Jcvc{c/0I0x9(8E0,8F0lc`0L090906c@0x0h0r0Z0,0U090{0Qbt0)0x0g0B0g1x0r3t0m0,dw0l0O3tdn1y1A1Cc{df2`09didk2X0ldn8G6i1Ddrdt0986d117d3098;991Y040k9z130+1w2?1w138C8E9C9*1n1c209)ch2NbWcma79Yc89#bg0.a81j2YebaWa8b?0h139Cam1u2(9}0!aW8Dbx9:1%d{d}0za2e99.e39H0z0lbp9%0Bcv550H0m0la67qc+2lc.0:c:04090Bc@c_c{dDdF0xdJ9P0GdP9O0O0Z0m0G0he^098Q6J2V9Ae!a{e$4+e(c;9O090j0:0q0H4-9%drf23HeF3xbM9@b~9yf57le#c-f9e)e+e.fk3$al1wam0l0_a|1xf6c,e%fye,0%0Ldpe/dE0$dG0Le^0x0Z0GfWdnc`dCfT8x0Z0#0Zf14Y0Ra,059^fsaXfKf8c/fb0h6h6jfB6cfD9D8q2xfvfMfbdvdxdzfRf(e;e?0r0ge}e_gae}e 0,f.g1eg0H3=bz9q05fpa-b~f_fwf{e*fOdwdydn0UfSgedK0m0Ugfe|dP0he`gOgce:fUe=gKfXgRgle^fRe-go9uf;a.fuf7gAfagCg9gF0lgHgdgV0ggMdKdydOdwe{f$0lg%fl2.1Nf;0Rgwh6b~1hh80?3x1~aF0*1J0uaj9w04f@ehcKch9sg423g6fxg8c^gTf)gWe@gje{g!gnh43Pf4f^g,fLhwgC0hfdfffhbH0lg03gfn9a0S9Dey20e(eC8Ceqbt2neufUasb4140:16hX1NhgaGhjhlc2c40-c601bka{bH0:0rb$eu0r642A1f0Fc+i49(b@aY9Kia660R9R05cr4dctcvaWcy2vcB0:cD0103i20-i4i6b@i9652E0lcO0:cQcS2r9$ag0hcXcZ0Rc#1Nc%1(1*3K251?1^1`9b3K2K2B2D1f2Q0;0)a{0W9%0o0i2l1w4Y4U9b3h4Xin7l8%9M8)4;8l6O727+7r506;7-8:5e7q625l6;5q6d8+6-0h5v9L6E8d7X4Xj25H8d5M7=jh1fcfja817#8p7q0ujl37jE5+04bt0hfejt80jN5-jn3K5:jW3:j36E5_j67Y8,5L0EjEjxjZ5/5L9t4xd78jjr786G8t6d7z6Mj7jo8bj%8d6Xj)k17Dk07c7H8#6Ojej/4r6?8g8hj^a!6}jaj9k9j!k2j{kn1f7okc6-7wkt7djajYk63Kkykf7Qku8.jG5%jI7GjakekD5K8ekz7SkB89kG69kKj}8m047*kp4dkPjv7%7;ki6^kkj4a#j(k+j81f9:kQ7C9E86jSkX76k;kml0jbhH8S8i7l8x8z8B8Ddo8H8J8Lkl8PjA8U1f8W8Y8!7$6Oj#787{k{kg1fk5k@k7lp7/k,1f8;8R8?9K8_2/d`c3c51abQ8I8Y2O0pbM8X2(ioi!cucwiucAcCcElPlViIiKiM3?cUiQiSc!c$0ZhmlXiwiy1_0I0W0H0D7SdE0`0N0-0*1d0:1)0$0`3=0j0Rm4m60R0e0z0j0(0p0V0(0f0P2~0%0p0K1n1 0Hmsk;1fmi0j0w2~h2mucx9r0pk;l=al0h0C8K200VfQ1m8E0Z0P0Z0dh:0/0nmj9r0~0le00nbI20mXeQ0C0Ya{aW3t0P0=mYaC0.0-0wfeal9~9B1xc.0K0Cc.e52BeQjP4O0rc}0?m 9(a_8D3NahbzbbiJn53=a|cm13390+0_2(0Hh@8{0~101204.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)