Nombres de Catalan (2)

Série d'exercices

Cet exercice fait partie d'une série :

Combien y-a-t-il d'arbres binaires d'une taille donnée ?

Il y a 1 arbre binaire de taille 0.
Il y a 1 arbre binaire de taille 1.
Il y a 2 arbres binaires de taille 2.
Il y a 5 arbres binaires de taille 3.
Il y a 14 arbres binaires de taille 4.

Arbres binaires de taille 4

Les 14 arbres binaires de taille 4, peuvent être répartis en fonction de la taille des sous arbres.

Il y a un nœud racine et 3 autres nœuds à répartir à gauche ($t_g$) et à droite ($t_d$).

\[(1 + t_g + t_d = 4)\]

$(t_g=0, t_d=3)$

$(t_g=1, t_d=2)$

$(t_g=2, t_d=1)$

$(t_g=3, t_d=0)$

Objectif : écrire une fonction nb_arbres_binaires qui prend en paramètre un entier net qui renvoie le nombre d'arbres binaires de taille n. Il existe plusieurs méthodes de calcul. Nous utilserons dans cet exercice les nombres de Catalan.

Si la taille $n$ vaut zéro,
- renvoyer $1$. Il y a un seul arbre à zéro nœud, un arbre vide.
Sinon,
- l'arbre possède une racine et deux sous-arbres. Les tailles possibles pour les sous-arbres sont :
  - $0$ à gauche et $n-1$ à droite
  - $1$ à gauche et $n-2$ à droite
  - $2$ à gauche et $n-3$ à droite
  - ...
  - $n-3$ à gauche et $2$ à droite
  - $n-2$ à gauche et $1$ à droite
  - $n-1$ à gauche et $0$ à droite
- renvoyer la somme du nombre d'arbres dans chaque cas.

Indices

Pour un arbre binaire de taille $5$, il y a un nœud racine et $4$ autres nœuds. Ces derniers peuvent se répartir en $(0, 4)$, $(1, 3)$, $(2, 2)$, $(3, 1)$, $(4, 0)$ à gauche et à droite.

Pour $(0, 4)$, il y a
- $1$ sous-arbre à gauche possible, à 0 nœud,
- $14$ sous-arbres à droite possibles à 4 nœuds,
- ainsi $1×14$ possibilités de choisir un arbre binaire de taille $0$ à gauche et de taille $4$ à droite.
Pour $(1, 3)$, il y a
- $1$ sous-arbre à gauche possible à 1 nœud,
- $5$ sous-arbres à droite possibles à 3 nœuds,
- donc $1×5$ possibilités pour ce cas.
Pour $(2, 2)$, il y a $2×2$ possibilités.
Pour $(3, 1)$, il y a $5×1$ possibilités.
Pour $(4, 0)$, il y a $14×1$ possibilités.

Il y a donc $1×14 + 1×5 + 2×2 + 5×1 + 14×1 = 42$ arbres binaires de taille $5$.

On stocke les résultats qui sont utilisés souvent dans une liste catalan_mem, cette liste commence avec [1, 1, 2, 5, 14, 42]. Il est très utile de mettre à jour cette liste dès que possible.

Exemples

🐍 Console Python

>>> nb_arbres_binaires(3)
5
>>> nb_arbres_binaires(4)
14
>>> nb_arbres_binaires(5)
42

Code à compléter :

Évaluations restantes : 10/10

.128013s3_8èufvIy n7aêS1me(P2C4:jtwi][h*)6Oo;bcdgM/0làqp.rL-R,=+Nk95Jxé050P0t0B0o0D0U0b0l0O0U0o0b0b0(010B0D0X010406050b0g0s0s0o0Z0k040q0L0U0g140L0m0l020o0s0X0M0l0$0t1e0Z0W0g0t0b050S1b1d1f1h190X041F1M051P0S1P1R1M190P0D0i0|0~10120G0D0Q0G0U1)0G0B17050@0N0U0t1!0 11011(1*1,1*0B1=1@1:0B0N0L0P1h1;0Z1N0B0G0|1k0b0X0o0m120w011_1$010h0_0t0m1s0t1:2h2j2o1{2r1@2u0s2w040a0l0v0Z0L0X0L0b0D1n1p0=2f0Z0Z0t0O2R1F2y0m1N0S2d2%0B2b2a2c0P2A121,0m2t2O1:1X1Z0}1`2;0D2?0m271Y1:0X2W1N2#2%381a2i1p2|2p310Z1e0U170l0r2!3c183b2z3e1{3g3i3k0w3n2j3p2#2:013u0o3j040l0c3y2$193B3s123E3G0l0y3K3A3c3C3Q3k0-3U3M3W3O3D0L3h3F3k0J3#3q3d1#3t3*3v3H0n3/3N3=3P3@3,3H0e3{3%3}3)3+3R0,433r453Y040r0T4a3;2}463^0r3m1G3o3$4b4j4d0r3x4o3z1O361F2`2*0P2.3C0O272G0;1Y1N350t373o3U054G0=4O4r2p0O0r17030l0j0m2Q0D3F0D0b0o2R0l0P0o0l0~0l1b2Q1^0=0{0Z0:1b0U0@0B1E4w3L3:3X170O4-3F2j0d2F0s3U0l563(0L170(5g5i4516040F4Q3|4j0s0D174n3a5u2p5q0E3#064q4i2p0+170=0h5t444j0C3k5O4V3t0h170m0N0d1f0N2W0b0d0N2 0^5%5T5I1{5q0u5.57040m5?3(5q0I0z3#0l605h5B1{5K040D5N543H5o4s5X5n63125k04020Q0B0M5m69625P3f0N172D5`5p175=696b3f585a0~0m5d1y6v4j5|5~6906616O6p5U3P170b0L1d0t0d5953386Q5/6g5l6e6q1{5w174g6M6P616A64170h3*6*6R3D170D6{6%010L5R665_6o6?3P6s040Z2j0Q0t6I5C6x7g3t6d6z6f016K5 6;6P786}046U6W6Y0 703C6h0)6n6#7t0m5X5Z5#5%5)5+0D5-7m6+125;7j6S667U7o170I7A5j170H7#4c7I5!0Z5$1D7M2u7O1D7X7T7Q6|7H5^7)4j6h0#7}2p6-4e811{7 857V6 7_715|7q6;7t4X4Z4#0O0D0%0|6D5c5e4@0t7c4/1^0U1o0Q1C0g0Z0l76386N7r7G6C0@6E6G5f8b7B170Y7X7{0o0X0X2t0P7@7i8N3(7{7w2F7y6!4P7n8d6:6=7n652W0B8A8D3o6$5@598J8p6H8!6w5r8R7l5A7R7Y045E6M1F4S4N4y9d0S4B1F0B4D9i2,2(26282*0o1?9f4B1L4U712W0s0d0h0o0+6X0G0c171x1z1B1D0l6L3a1S3p1k3p1,040!4;4M5w0f2W0l2i0Z141^0V2f1t0U0:0B8s0l1D0B0l9*4?2r1p4R4H3C1}1+1-1/9w3C8;0?8@887u8|5b6F5e8Y92906c7|ag7h984Q0S9c048m1o4@0L0g0G0^9/4=4;0i3F0t8A4/002 1X0O1^7t1f2Q0G1e9/0/17090u0m097!6o2TaI218v4+9/0Y0l0K0g0l5*2t5h9c9~1-1 1.2x967{8^3z8`7$6i6k6ma85Y6t2tae6y957`8Iab8LaeaW9Oao0l0o0g9K0U8n0{ar8V1m0l4}2N0m0P9!1X2W2Y1y2t0B8m2P310m8m0_0l9Bbq1@8n0U0O0g1@8B0?4=000o0Aat9/8B9^4;1,0b9/8maI0l1B0D8rbJaw9@ay4=1)2?9#4}0O0:0=0ma%1F9T199T9|4T8%6X6Z9b4H3H9=0l0gb_c78u0{6ZbH4%144*0b0:9)a}45aL2daO0taQ04aS0TaV5gb#b@0Qb_0Ja(0jbl0kbhcs4jcuaN4-cxaRaTcC6o6Zb=9.0g1X9:2TaK0ZaMcwcyaS0u0T8m0m0#0r0IcW388mc)c+cSc-0u0u0rc;0#0wc^be3oc{7ncQc,cU090O0P0L52c_d8cO2pdbc~cUaTd48mc@dj3zd996dnaPdpc=d20l0Td63Ua(9Va,at0}aJa:3(9 a?a27t656_0Zb26~a8736~a{2$dl3t7a7c0m7eb693aib88c7Z9N4PancbbJ8s4;a-9{dac*cvdoczcVd7a|0Bat0Z0b8QbQ9S0D04bib`1y0D9:e7aDc|e1dze30D0(cBe52$8m0UbV1m9!0:9-2Fb 4/a+4G0g0XbM0=0i8t0p2+aJd c}epaSdBdu2$c1eec3eeegel8B4^aAeEencReT0uer0reWapbUbieP0leB0:eD9?0PeGateJ4`0teM4;eO9!e,dce3c=0we=eYed042T1e4%9Z1^0Q0:0m0:7c1@eweye_e{e}eF2feIeKf4eNe_f9e2eUc?0#0Dfe0Sc21Fec19fMeZ059TdIdU0sbQ1^2NaDbMcYa.fFe.fKeuccb(4/1o0Oa/9}dOa=a1a^b95^7J7-7L5*7;7Pd:3C7^g38#dXaj5:7ZdY7%dWf|7,7.5(g05,7?g97S8Zg67*d/8_7t87777n835zgs7ngu7F7n7{8agp6Jgb6zd^4Tffe!040.0gb(670D1o0{f$6Ve}gkcFb_0,f=4T4!0j8kb*8oac1y8r8t2T8wd+8z8B76ao05fPfTee0qb.arcdbB4}4/2jgV4;b(0Z0g2Y8A1^4Gbu4(1o2?0Ufs0|00cd9Kg%4N1p02501v2D0uaa8K5eaWg{fRfg0R0^0{9^aF101C8ub?26hcbMc5hsf}gh7:gk0baT0l0#3lhCd_4;9.0:bh8U0t9-8mbTdg0mf;hS04hz8~8Mbg4;0P0:0A9*h*0l5whI0lbXaDfi2j0Dflbr0:bPe91Y0th:9?bIcdh=f;g=8xg^hraiao8QhEgN0K1pbp9?0^0m2P9+eJ9.9:4?1 b_4fhra;1~f_a3g7h_g-bcgm728Pd.8T8Vbud-iX8$gXc87ziX8-bfcbiwfN0Sg}ix1F9R191?0L0O0+1Bdh4N9vcK9;0/a$4`00054;0G2W0h1%210X0b0z0S0S0h0Z0Y0C0D0+150t1X0o0Y3*0Q0Sjqjs0S0*6V7.0d0=0d0xg-17e^5%i49.0G4H0{aY3FbP0U1F0oe?eJgQ9;0h2r59aIea1O3p0Si}i j19/j.0=0@0_0b04.