Aller au contenu

Arbres k-aires de hauteur h

Arbres k-aires ; généralisation des arbres binaires

On définit un arbre k-aire (et sa hauteur) comme :

  • soit un arbre k-aire vide (de hauteur 0),
  • soit un arbre qui a exactement k sous arbres k-aires
    • dont la hauteur vaut un de plus que le maximum des hauteurs des sous-arbres.

L'ordre des sous-arbres compte, ainsi on dénombre

  • 1 arbre 3-aire de hauteur 0. L'arbre vide.
  • 1 arbre 3-aire de hauteur 1. L'arbre ayant un seul nœud.
  • 7 arbres 3-aires de hauteur 2. Ils sont dessinés ci-dessous.
Définition alternative, enracinée

On peut aussi définir un arbre k-aire comme un arbre enraciné :

  • soit une feuille (de hauteur zéro),
  • soit un arbre qui a exactement k sous-arbres k-aires

Les seules différences étant

  • qu'une feuille peut porter une valeur, et pas nil.
  • pour le dessin, on indique les feuilles, et pas les nil.

Pour le compte qui nous intéresse ; aucune différence !

Exercice

Coder une fonction nb_arbres_aires_hauteur

  • qui prend en paramètres
    • k un entier strictement positif
    • h un entier positif
  • et qui renvoie le nombre d'arbres k-aires de hauteur inférieure ou égale à h.
Contraintes
  • 1 <= k < 20
  • 0 <= h < 7
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
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
Évaluations restantes : ∞/∞
.128013x,59/f.78r;nb _o=ylaepcwgu)*vd461`3kRméhtsP(S0à+2-i:@050E0v0P0u0Z0t0Q0o0x0t0u0Q0Q0r010P0Z0w010406050Q0A0M0M0u0k0s040T0q0t0A0_0q0m050f101214160~0w04051m1f1p0f1m0~0E0Z0D0.0:0=0@0O0Z0z0O0t1D0O0P0|050)0n0t0v1y0;0?011C1E1G1E0P1M1O1K0P0k1n0P0O1Q1A010g0+0v0m0u0M0v010.190Q0w0u0m0@0X1K1{1}1+1S1.1O1;1?0|0a0o0R0k0q0w0q0Q0Z1c0m0o0%1_0k0k0v0x2k1f220m1n0f1)2x1$1(1%1L0E240@1G0m1:2h1K1v1x0/1R2H0Z2J0m0q2N1K0w2q1n2v2x2#0 1|2l2P1,2U0k130t0|0o0H2u2)0}2(232+1S2-2/2;0X2@1}2_2v2G012~0u2:040o0J322w0~352|0@383a0o0F3e342)363k2;0d3o3g3q3i370q2.392;0G3v2`2*1z2}3A2 3b0i3F3h3I3j3K3C3b0j3O3x3Q3z3B3l0e3W2{3Y3s040H0U3%3H2Q3Z3L0H2?1g2^3w3(3:3*0H313^333`3/2,3S3a0H3d403f3G3r450|0H3n493p3{443!4e3u4h424c4l3+3E4o4b3y3}3N4u3P3|4d3+3V4z3X4B4r0H3$4F4j3J4r0X3-4L434N3L0X3@2#4p4w4C0X3 4X4v3)4!484%4A4k4U4g4,4G4.3T0X4n4;4M3R4O4t4`4S4|4U4y4 4q4U4E544Z4O4K584)4r0J4Q5c4H3L0J4W3_4(5i3T0J4$5m4-4T5p4+5s4=5u3a0J4:5x4{3;5p4_5D505F5A4~5I555p535N595j575R5d5j5b5V5o3a0F5g5Z4?5#5l415n5)0|0F5r5,5t513T0F5w331q2Z1f2N2A0E1(2F3y0x2V1@1n5 1o5}2%4h05650%2!5y0@0K0m0|0Z0M2g0k0P3o5-1S0y2;6s5?376l040g0A0m2s0q1`3v4Y3Y0K0|0%0g6x6i016v3b6P5E0m0g0|0m0n0p140n2q0Q6#0Z6(0p0O0u1b0v0A0k6U5J0{040S6@3r0|0K6|3y6_0c3o0o6t3j0|0O703Y6_0B0!3.366S0o7i756d6y0Q0E0|017q7f3y7n2;7j0L1:0D0q0Z1P1O0o2U0M6%1P0E006$6(0o0I0K0I0Y0*6(7s3Y7u3b7j7Y2n6.6:6=0o2S0g0N0k7B6=1P0q0A0o0N0z391P0V7N0O0I7U3:7W7Y7q016I7Y76377o040#6C6E0P6G0,7a3:0q0|0h8g2,0|0x0u0x0O0v3v856y6L046N8l6u6w7l6Q6W0|0Q8z0@6_6{8C6V6~8H017274866A798L6^0|7d8t7Y7j860Q2004370n0o7L0v0-7!6/0P6;0k0o0r0r0o0O834o8!8#8v6m6O4h756y8T8R6y8i048_986Q0M0Z0|5%5{6y6_7e8~8 8!868w2q0P6=1e94869f4e8Z8 8S8F0p9d5E9a0r9F5J6A8G8V368J8O6A6 9N710|739w96789J369a0Y9!3y9y3+8O7c9A9p9Y040P9E9X6Q9H9(3)0|6r9T7b0|8K2%9:9Sa26Q8Q9@8M048U2#959^0|9%a85J9*5+2w869-9n9B91049s9u9`3:9P9~3|9Dau1,9a0WaA2}9|9?a55Eanac869a0C0CaE7704a42^7iaMafaQ37aGaYaNaPah6}aS84908D888a6D6F6HaxaB8j9Q8n8p8r9.9q6M0v93aI5J7h9Q6X9;9,a0a_a*a?1Sa7aL9:ab2^am8X9m4X9oad5E8%7p6Z8,0k7H8/1P7#8=7%020t0P0l8{8}bm9oa~040Zb1aU9Caaa#0|9ca(9)9g049ial9k0|bl3_bn8u6Q9r0(atbT3Y9*bX0}bnbJas0k9vbf8D9|b86`baaT9ja69VaY97b-8haXc61,ajb}0BbQ04aDc9aF049Mb29Ob9bcaRc0bYc2049Wb`a9bh33bo5J9$aYcbco8P8Xa+aVaqb@b_bN9:9}cl9Ub~cE9Rb}cucMb{bPcEaKcW9G0|cgcv9K8Fb}a1bia3cUc49ZcZcG4o6J3|a.8ba;8fcE9a8kcSa`8q8s4R368w8ycEb4cSb66Z0p0)0+1Oc,bacOc.cs8Yaoczd792c;b7ch0@9H9Idv01b/b}b#41b=cJb+b^cCbVakb;a,a9ckc#cAbRdJ9ha}aq0g3Adt0ua#6S2Sc40n0|0k1}0zd5cP9 cRd/aydud=1,7cdD3fdFb)0|dX6?dz6A0nd#6mcLcy8Sd)ard,d.dmaJcnd^cidle899c8c)a)d!c?04dobHb%dq3y8we0dt0xe5bKe72wev3)ead+0md-djd2d@dQ9#emeO4w0|epen3ycBe20|e4eqesb$eu9/cX0EcedyeV9{eNekae04age.d?eUeR3YeXe^8m04e!e~1Se}e{d?eAdzf4e;5EcDete(cId~041R0v6qdte+f80|020zbDe-f5cabVb:06feb(5E8wfifkeYfhcec(ftcif1fIdwc%ezfGfle,fsfac*e:eEaWe?dT9+dpfebOdPfTePcffSfW9:dedg0tdieqc-c1a9e`f^8Wercea%f2aRf/0*f;edf{cmd;eefUfKg6cQcdfn04f fLaZ04g2dhg5crefg8gce/f7eh8Ic@g001aNdtglg4eLgugjfmgEc!dEdN5Jb*9tdIfEf(3fc_1,exdYfEejf-9^d$eD6T96eHecgDg9369*5QgravbkdV8Dea2Y2SgX6hgpf@gofUgBf=gHegg+eSfVg{f|0Bge5he 0v0b2jg*g/fudUe#3F0f6f0v2x2Yho5~1w602A2D2y0u1Nhr0f5 0~hB0(g30Q04.