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
.128013.9875.65038 ,%!è OVw*5e(8CR0pkojicE6S1vqA{d×:xy24fln-]9B3m=U)rh[u}s;b/.àt_gLéaP+N7 050H0n0/0@0x0P0)0h0y0P0@0)0)0X010/0x0t010406050)0%0W0W0@0!0L040B0v0P0%1c0v0Q0h020@0W0t0*0h0r0n1m0!0E0%0n0)050,1j1l1n1p1h0t041N1U051X0,1X1Z1U1h0H0x0D1416181a0#0x0;0#0P1;0#0/1f050 0+0P0n1,1719011:1=1@1=0/1}1 1{0/0+0v0H1p1|0!1V0/0#141s0)0t0@0Q1a0M01211.010O110n0Q1A0n1{2p2r2w232z1 2C0W2E040a0h0^0!0v0t0v0)0x1v1x0}2n0!0!0n0y2Z1N2G0Q1V0,2l2/0/2j2i2k0H2I1a1@0Q2B2W1{1)1+15222|0x2~0Q2f1*1{0t2(1V2-2/3g1i2q1x342x390!1m0P1f0h0C2,3k1g3j2H3m233o3q3s0M3v2r3x2-2{013C0@3r040h0V3G2.1h3J3A1a3M3O0h0N3S3I3k3K3Y3s0m3$3U3(3W3L0v3p3N3s0A3-3y3l1-3B3=3D3P0{3`3V3}3X3 3@3P0p433/453;3?3Z0T4b3z4d3*040C0s4i3|354e400C3u1O3w3.4j4r4l0C3F4w3H1W3e1N322=0H2_3K0y2f2O0|1*1V3d0n3f3w3$054O0}4W4z3n1f0y0@0 160Q0:2N0W3$0h3{3K0v1f0X4=4@3:1e040$4Y444r0W0x1f4v3i532x4 0S3-064y4q2x0u1f0}0O524c4r0k3s5n4%3B0O4)4+3N2r5s5h234 0o5A3)1f0Q5F4~1f0Z0J3-0h5P4?5a3B1f0x4|5S1a4_044{4E2.5R5o3n0+1f2L5J4d5D5.4A5w4,2r4/1G5;5b5L5O5Q4}4d5j040k1:1 5W5)5T045I5$3P604r5Z020;0/0*5#3g5(5t3X5U5{5C1f5N6c065Q6x6n5B6p044*5@4.0x0W583w6z4^4`676o3L5?5y4.4:6r1a4 516c6e4(045V6c6K3:5Z0R6N6A0155576U015c5~6y6(4k6Q4-0:6$6m6Z235Z6l6J706B6D6R6}6H6,6L040l7b3:6/044D6 5X015Z7e6%756=1f5E6Y7l7h7j747l7n7f6`6#7B6f1f6+7p7v564m6;4 0Z7E2x5Z0,0,7P6s047t59686B6~7y7Z7m1f0_7U1a7h6I4F7l7N6@6y7q0Q6{5^6T7u7%5Z0-6;7^040@0t0t2B0H7M7s807_6F88047O6v6^5P7@6q7I7}7)733H6_547K7.3T6x7q0y0C1f030h0x0y0x0h1x020P6j0h2L0o776|4:8f3g6w5 7l622(0/0%0!6b7k7%818N7`5`7|6O6W8a6a8d5d6v1N4!4V4G8^0,4J1N0/4L8}2@2:2e2g2=0@1~8`4J1T4$6-2(0W0:0O0@0u0n0:0#0V1f1F1H1J1L0h6u3i1!3x1U0^0v8Y0h0%1x83850P0h2#4Z4P6C5x4-0o0Q8f8@3P0}0%0K14170h850%0D2B0/0h0)203d2f0%0x2(7 9v1h1s3x1@1V9R6b9R0h1L9%0t1t13851c9%9q8K0@8K1w0;1K9A2#168K0x0)0/0n0d0h3N3=131 0h0!0?1j8I4+9}ai9H0?0w0.9(0/0v0y0u0?al119(0%0O2z9%2#2(0Q0D0v0L0n0!4?9R8(6S1G0$0Q8;9R9:9^1h9^9J4#9{9Kax9%1j0t0?0!0x0n9A9z0h0?0;3N0haCaf0PaaacaXaea81@ai0n0-0h0i1x0Da8an0!139g9.200;0!2r1)aX0y0~ajagbe9}1x1u11ah2r9%af0O3 0%aqaQ0?0y8YaRbxal0 0Qa51K8FbP1L0)109/bh1x9)ar0~2T9!20bm130H2rap204*130Ca+0x3x0,9?1h0#0C8B0H6V2(b/0R0}0R160RbK3pbM2O2Sa}9#9H20bJbL66a83:0#0n0@0}0!2}5j0h0#2(0O1a034Uc9cbcdcf0Wch2va41 1a0^aW1m38bI37620b0c1N0@2/c33x323K1n2Y0#1maj0K1f090$0q0:1x0X0h090+0n0;370Gb`1L0(06c48hd7d88h1z1B1D091Jcvc{c/0/0G9(8E0(8F0hc`0s090906c@0G0Q0R0C0(0I090H0Obt0y0G0M0o0M1x0R3t0Z0(dw0h0_3tdn1y1A1Cc{df2`09didk2X0hdn8G6i1Ddrdt0986d117d3098;991Y040`9z130W1w2?1w138C8E9C9*1n1c209)ch2NbWcma79Yc89#bg0=a81j2YebaWa8b?0Q139Cam1u2(9}0KaW8Dbx9:1%d{d}0%a2e99.e39H0%0hbp9%0ocv550)0Z0ha67qc+2lc.0nc:04090oc@c_c{dDdF0GdJ9P0fdP9O0_0C0Z0f0Qe^098Q6J2V9Ae!a{e$4+e(c;9O090;0n0E0)4-9%drf23HeF3xbM9@b~9yf57le#c-f9e)e+e.fk3$al1wam0h0+a|1xf6c,e%fye,0:0sdpe/dE0@dG0se^0G0C0ffWdnc`dCfT8x0C0X0Cf14Y0,a,059^fsaXfKf8c/fb0Q6h6jfB6cfD9D8q2xfvfMfbdvdxdzfRf(e;e?0R0Me}e_gae}e 0(f.g1eg0)3=bz9q05fpa-b~f_fwf{e*fOdwdydn0IfSgedK0Z0Igfe|dP0Qe`gOgce:fUe=gKfXgRgle^fRe-go9uf;a.fuf7gAfagCg9gF0hgHgdgV0MgMdKdydOdwe{f$0hg%fl2.1Nf;0,gwh6b~1hh80P3x1~aF0u1J0vaj9w04f@ehcKch9sg423g6fxg8c^gTf)gWe@gje{g!gnh43Pf4f^g,fLhwgC0QfdfffhbH0hg03gfn9a0Y9Dey20e(eC8Ceqbt2neufUasb4140n16hX1NhgaGhjhlc2c40xc601bka{bH0n0Rb$eu0R642A1f0jc+i49(b@aY9Kia660,9R05cr4dctcvaWcy2vcB0ncD0103i20xi4i6b@i9652E0hcO0ncQcS2r9$ag0QcXcZ0,c#1Nc%1(1*3K251?1^1`9b3K2K2B2D1f2Q0B0ya{0t9%0^0L2l1w4Y4U9b3h4Xin7l8%9M8)4;8l6O727+7r506;7-8:5e7q625l6;5q6d8+6-0Q5v9L6E8d7X4Xj25H8d5M7=jh1fcfja817#8p7q0vjl37jE5+04bt0Qfejt80jN5-jn3K5:jW3:j36E5_j67Y8,5L0djEjxjZ5/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`c3c51abQ8I8Y2O0qbM8X2(ioi!cucwiucAcCcElPlViIiKiM3?cUiQiSc!c$0ChmlXiwiy1_0/0t0)0J7SdE0-0k0x0u1d0n1)0@0-3=0;0,m4m60,0z0%0;0e0q0V0e0F0p2~0:0q0#1n1 0)msk;1fmi0;0g2~h2mucx9r0qk;l=al0Q0?8K200VfQ1m8E0C0p0C0Nh:0U0!mj9r0~0he00!bI20mXeQ0?0Da{aW3t0p0TmYaC0=0x0gfeal9~9B1xc.0#0?c.e52BeQjP4O0Rc}0Pm 9(a_8D3NahbzbbiJn53=a|cm13390W0+2(0)h@8{0~101204.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)