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
.65038.128013.9875 s3_8èufvy 7naS1me(P4CV2:jtwi][hE*)6Oo;bcdUg/0làqABp!.rL-,}=+Nk%{95R×xé 050R0t0C0p0E0W0d0m0Q0W0p0d0d0-010C0E0#010406050d0i0s0s0p0(0l040q0N0W0i1c0N0o0m020p0s0#0O0m0^0t1m0(0Y0i0t0d050U1j1l1n1p1h0#041N1U051X0U1X1Z1U1h0R0E0k1416181a0H0E0T0H0W1;0H0C1f050 0P0W0t1,1719011:1=1@1=0C1}1 1{0C0P0N0R1p1|0(1V0C0H141s0d0#0p0o1a0z01211.010j110t0o1A0t1{2p2r2w232z1 2C0s2E040b0m0v0(0N0#0N0d0E1v1x0}2n0(0(0t0Q2Z1N2G0o1V0U2l2/0C2j2i2k0R2I1a1@0o2B2W1{1)1+15222|0E2~0o2f1*1{0#2(1V2-2/3g1i2q1x342x390(1m0W1f0m0r2,3k1g3j2H3m233o3q3s0z3v2r3x2-2{013C0p3r040m0e3G2.1h3J3A1a3M3O0m0w3S3I3k3K3Y3s0@3$3U3(3W3L0N3p3N3s0L3-3y3l1-3B3=3D3P0n3`3V3}3X3 3@3P0g433/453;3?3Z0?4b3z4d3*040r0V4i3|354e400r3u1O3w3.4j4r4l0r3F4w3H1W3e1N322=0R2_3K0Q2f2O0|1*1V3d0t3f3w3$054O0}4W4z3n1f0Q0p0 160o0f2N0s3$0m3{3K0N1f0-4=4@3:1e040G4Y444r0s0E1f4v3i532x4 0F3-064y4q2x0:1f0}0j524c4r0D3s5n4%3B0j4)4+3N2r5s5h234 0u5A3)1f0o5F4~1f0K0A3-0m5P4?5a3B1f0E4|5S1a4_044{4E2.5R5o3n0P1f2L5J4d5D5.4A5w4,2r4/1G5;5b5L5O5Q4}4d5j040D1:1 5W5)5T045I5$3P604r5Z020T0C0O5#3g5(5t3X5U5{5C1f5N6c065Q6x6n5B6p044*5@4.0E0s583w6z4^4`676o3L5?5y4.4:6r1a4 516c6e4(045V6c6K3:5Z0*6N6A0155576U015c5~6y6(4k6Q4-0f6$6m6Z235Z6l6J706B6D6R6}6H6,6L040J7b3:6/044D6 5X015Z7e6%756=1f5E6Y7l7h7j747l7n7f6`6#7B6f1f6+7p7v564m6;4 0K7E2x5Z0U0U7P6s047t59686B6~7y7Z7m1f0.7U1a7h6I4F7l7N6@6y7q0o6{5^6T7u7%5Z0%6;7^040p0#0#2B0R7M7s807_6F88047O6v6^5P7@6q7I7}7)733H6_547K7.3T6x7q0Q0r1f030m0E0Q0E0m1x020W6j0m2L0u776|4:8f3g6w5 7l622(0C0i0(6b7k7%818N7`5`7|6O6W8a6a8d5d6v1N4!4V4G8^0U4J1N0C4L8}2@2:2e2g2=0p1~8`4J1T4$6-2(0s0f0j0p0:0t0f0H0e1f1F1H1J1L0m6u3i1!3x1U0v0N8Y0m0i1x83850W0m2#4Z4P6C5x4-0u0o8f8@3P0}0i0`14170m850i0k2B0C0m0d203d2f0i0E2(7 9v1h1s3x1@1V9R6b9R0m1L9%0#1t13851c9%9q8K0p8K1w0T1K9A2#168K0E0d0C0t0+0m3N3=131 0m0(0{1j8I4+9}ai9H0{0B0X9(0C0N0Q0:0{al119(0i0j2z9%2#2(0o0k0N0l0t0(4?9R8(6S1G0G0o8;9R9:9^1h9^9J4#9{9Kax9%1j0#0{0(0E0t9A9z0m0{0T3N0maCaf0WaaacaXaea81@ai0t0%0m0M1x0ka8an0(139g9.200T0(2r1)aX0Q0~ajagbe9}1x1u11ah2r9%af0j3 0iaqaQ0{0Q8YaRbxal0 0oa51K8FbP1L0d109/bh1x9)ar0~2T9!20bm130R2rap204*130ra+0E3x0U9?1h0H0r8B0R6V2(b/0*0}0*160*bK3pbM2O2Sa}9#9H20bJbL66a83:0H0t0p0}0(2}5j0m0H2(0j1a034Uc9cbcdcf0sch2va41 1a0vaW1m38bI37620c0a1N0p2/c33x323K1n2Y0H1maj0`1f090G0x0f1x0-0m090P0t0T370=b`1L0,06c48hd7d88h1z1B1D091Jcvc{c/0C0=9(8E0,8F0mc`0V090906c@0=0o0*0r0,0_090R0jbt0Q0=0z0u0z1x0*3t0K0,dw0m0.3tdn1y1A1Cc{df2`09didk2X0mdn8G6i1Ddrdt0986d117d3098;991Y040/9z130s1w2?1w138C8E9C9*1n1c209)ch2NbWcma79Yc89#bg0)a81j2YebaWa8b?0o139Cam1u2(9}0`aW8Dbx9:1%d{d}0ia2e99.e39H0i0mbp9%0ucv550d0K0ma67qc+2lc.0tc:04090uc@c_c{dDdF0=dJ9P0$dP9O0.0r0K0$0oe^098Q6J2V9Ae!a{e$4+e(c;9O090T0t0Y0d4-9%drf23HeF3xbM9@b~9yf57le#c-f9e)e+e.fk3$al1wam0m0Pa|1xf6c,e%fye,0f0Vdpe/dE0pdG0Ve^0=0r0$fWdnc`dCfT8x0r0-0rf14Y0Ua,059^fsaXfKf8c/fb0o6h6jfB6cfD9D8q2xfvfMfbdvdxdzfRf(e;e?0*0ze}e_gae}e 0,f.g1eg0d3=bz9q05fpa-b~f_fwf{e*fOdwdydn0_fSgedK0K0_gfe|dP0oe`gOgce:fUe=gKfXgRgle^fRe-go9uf;a.fuf7gAfagCg9gF0mgHgdgV0zgMdKdydOdwe{f$0mg%fl2.1Nf;0Ugwh6b~1hh80W3x1~aF0:1J0Naj9w04f@ehcKch9sg423g6fxg8c^gTf)gWe@gje{g!gnh43Pf4f^g,fLhwgC0ofdfffhbH0mg03gfn9a0S9Dey20e(eC8Ceqbt2neufUasb4140t16hX1NhgaGhjhlc2c40Ec601bka{bH0t0*b$eu0*642A1f0yc+i49(b@aY9Kia660U9R05cr4dctcvaWcy2vcB0tcD0103i20Ei4i6b@i9652E0mcO0tcQcS2r9$ag0ocXcZ0Uc#1Nc%1(1*3K251?1^1`9b3K2K2B2D1f2Q0q0Qa{0#9%0v0l2l1w4Y4U9b3h4Xin7l8%9M8)4;8l6O727+7r506;7-8:5e7q625l6;5q6d8+6-0o5v9L6E8d7X4Xj25H8d5M7=jh1fcfja817#8p7q0Njl37jE5+04bt0ofejt80jN5-jn3K5:jW3:j36E5_j67Y8,5L0+jEjxjZ5/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`c3c51abQ8I8Y2O0xbM8X2(ioi!cucwiucAcCcElPlViIiKiM3?cUiQiSc!c$0rhmlXiwiy1_0C0#0d0A7SdE0%0D0E0:1d0t1)0p0%3=0T0Um4m60U0I0i0T0;0x0e0;0Z0g2~0f0x0H1n1 0dmsk;1fmi0T0h2~h2mucx9r0xk;l=al0o0{8K200efQ1m8E0r0g0r0wh:0!0(mj9r0~0me00(bI20mXeQ0{0ka{aW3t0g0?mYaC0)0E0hfeal9~9B1xc.0H0{c.e52BeQjP4O0*c}0Wm 9(a_8D3NahbzbbiJn53=a|cm13390s0P2(0dh@8{0~101204.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)