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 *VANm;rp)_j:+v/L56è1!]d}0kE[4=×asUf7Cy2l9àuxtgoRS8wé.%(qn,b3{Oec -PihB 050z0;0V0I0_0Q0J0?0=0Q0I0J0J0G010V0_0k010406050J0T0h0h0I0j0O040Z0X0Q0T1c0X0+0?020I0h0k0i0?0Y0;1m0j0*0T0;0J050r1j1l1n1p1h0k041N1U051X0r1X1Z1U1h0z0_0q1416181a0`0_0W0`0Q1;0`0V1f050 0-0Q0;1,1719011:1=1@1=0V1}1 1{0V0-0X0z1p1|0j1V0V0`141s0J0k0I0+1a0P01211.010L110;0+1A0;1{2p2r2w232z1 2C0h2E040a0?0^0j0X0k0X0J0_1v1x0}2n0j0j0;0=2Z1N2G0+1V0r2l2/0V2j2i2k0z2I1a1@0+2B2W1{1)1+15222|0_2~0+2f1*1{0k2(1V2-2/3g1i2q1x342x390j1m0Q1f0?0w2,3k1g3j2H3m233o3q3s0P3v2r3x2-2{013C0I3r040?0.3G2.1h3J3A1a3M3O0?0F3S3I3k3K3Y3s0t3$3U3(3W3L0X3p3N3s0u3-3y3l1-3B3=3D3P0M3`3V3}3X3 3@3P0!433/453;3?3Z0R4b3z4d3*040w0B4i3|354e400w3u1O3w3.4j4r4l0w3F4w3H1W3e1N322=0z2_3K0=2f2O0|1*1V3d0;3f3w3$054O0}4W4z3n1f0=0I0 160+0m2N0h3$0?3{3K0X1f0G4=4@3:1e040E4Y444r0h0_1f4v3i532x4 0y3-064y4q2x0C1f0}0L524c4r0#3s5n4%3B0L4)4+3N2r5s5h234 0)5A3)1f0+5F4~1f0l0o3-0?5P4?5a3B1f0_4|5S1a4_044{4E2.5R5o3n0-1f2L5J4d5D5.4A5w4,2r4/1G5;5b5L5O5Q4}4d5j040#1:1 5W5)5T045I5$3P604r5Z020W0V0i5#3g5(5t3X5U5{5C1f5N6c065Q6x6n5B6p044*5@4.0_0h583w6z4^4`676o3L5?5y4.4:6r1a4 516c6e4(045V6c6K3:5Z0@6N6A0155576U015c5~6y6(4k6Q4-0m6$6m6Z235Z6l6J706B6D6R6}6H6,6L040d7b3:6/044D6 5X015Z7e6%756=1f5E6Y7l7h7j747l7n7f6`6#7B6f1f6+7p7v564m6;4 0l7E2x5Z0r0r7P6s047t59686B6~7y7Z7m1f0p7U1a7h6I4F7l7N6@6y7q0+6{5^6T7u7%5Z0%6;7^040I0k0k2B0z7M7s807_6F88047O6v6^5P7@6q7I7}7)733H6_547K7.3T6x7q0=0w1f030?0_0=0_0?1x020Q6j0?2L0)776|4:8f3g6w5 7l622(0V0T0j6b7k7%818N7`5`7|6O6W8a6a8d5d6v1N4!4V4G8^0r4J1N0V4L8}2@2:2e2g2=0I1~8`4J1T4$6-2(0h0m0L0I0C0;0m0`0.1f1F1H1J1L0?6u3i1!3x1U0^0X8Y0?0T1x83850Q0?2#4Z4P6C5x4-0)0+8f8@3P0}0T0U14170?850T0q2B0V0?0J203d2f0T0_2(7 9v1h1s3x1@1V9R6b9R0?1L9%0k1t13851c9%9q8K0I8K1w0W1K9A2#168K0_0J0V0;0,0?3N3=131 0?0j0$1j8I4+9}ai9H0$0n0S9(0V0X0=0C0$al119(0T0L2z9%2#2(0+0q0X0O0;0j4?9R8(6S1G0E0+8;9R9:9^1h9^9J4#9{9Kax9%1j0k0$0j0_0;9A9z0?0$0W3N0?aCaf0QaaacaXaea81@ai0;0%0?0:1x0qa8an0j139g9.200W0j2r1)aX0=0~ajagbe9}1x1u11ah2r9%af0L3 0TaqaQ0$0=8YaRbxal0 0+a51K8FbP1L0J109/bh1x9)ar0~2T9!20bm130z2rap204*130wa+0_3x0r9?1h0`0w8B0z6V2(b/0@0}0@160@bK3pbM2O2Sa}9#9H20bJbL66a83:0`0;0I0}0j2}5j0?0`2(0L1a034Uc9cbcdcf0hch2va41 1a0^aW1m38bI37620b0c1N0I2/c33x323K1n2Y0`1maj0U1f090E0N0m1x0G0?090-0;0W370/b`1L0A06c48hd7d88h1z1B1D091Jcvc{c/0V0/9(8E0A8F0?c`0B090906c@0/0+0@0w0A0H090z0Lbt0=0/0P0)0P1x0@3t0l0Adw0?0p3tdn1y1A1Cc{df2`09didk2X0?dn8G6i1Ddrdt0986d117d3098;991Y040g9z130h1w2?1w138C8E9C9*1n1c209)ch2NbWcma79Yc89#bg0sa81j2YebaWa8b?0+139Cam1u2(9}0UaW8Dbx9:1%d{d}0Ta2e99.e39H0T0?bp9%0)cv550J0l0?a67qc+2lc.0;c:04090)c@c_c{dDdF0/dJ9P0xdP9O0p0w0l0x0+e^098Q6J2V9Ae!a{e$4+e(c;9O090W0;0*0J4-9%drf23HeF3xbM9@b~9yf57le#c-f9e)e+e.fk3$al1wam0?0-a|1xf6c,e%fye,0m0Bdpe/dE0IdG0Be^0/0w0xfWdnc`dCfT8x0w0G0wf14Y0ra,059^fsaXfKf8c/fb0+6h6jfB6cfD9D8q2xfvfMfbdvdxdzfRf(e;e?0@0Pe}e_gae}e 0Af.g1eg0J3=bz9q05fpa-b~f_fwf{e*fOdwdydn0HfSgedK0l0Hgfe|dP0+e`gOgce:fUe=gKfXgRgle^fRe-go9uf;a.fuf7gAfagCg9gF0?gHgdgV0PgMdKdydOdwe{f$0?g%fl2.1Nf;0rgwh6b~1hh80Q3x1~aF0C1J0Xaj9w04f@ehcKch9sg423g6fxg8c^gTf)gWe@gje{g!gnh43Pf4f^g,fLhwgC0+fdfffhbH0?g03gfn9a0K9Dey20e(eC8Ceqbt2neufUasb4140;16hX1NhgaGhjhlc2c40_c601bka{bH0;0@b$eu0@642A1f0ec+i49(b@aY9Kia660r9R05cr4dctcvaWcy2vcB0;cD0103i20_i4i6b@i9652E0?cO0;cQcS2r9$ag0+cXcZ0rc#1Nc%1(1*3K251?1^1`9b3K2K2B2D1f2Q0Z0=a{0k9%0^0O2l1w4Y4U9b3h4Xin7l8%9M8)4;8l6O727+7r506;7-8:5e7q625l6;5q6d8+6-0+5v9L6E8d7X4Xj25H8d5M7=jh1fcfja817#8p7q0Xjl37jE5+04bt0+fejt80jN5-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`c3c51abQ8I8Y2O0NbM8X2(ioi!cucwiucAcCcElPlViIiKiM3?cUiQiSc!c$0whmlXiwiy1_0V0k0J0o7SdE0%0#0_0C1d0;1)0I0%3=0W0rm4m60r0D0T0W0(0N0.0(0f0!2~0m0N0`1n1 0Jmsk;1fmi0W0v2~h2mucx9r0Nk;l=al0+0$8K200.fQ1m8E0w0!0w0Fh:0{0jmj9r0~0?e00jbI20mXeQ0$0qa{aW3t0!0RmYaC0s0_0vfeal9~9B1xc.0`0$c.e52BeQjP4O0@c}0Qm 9(a_8D3NahbzbbiJn53=a|cm13390h0-2(0Jh@8{0~101204.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)