Aller au contenu

Pseudo arbre de Fibonacci

Pseudo arbre de Fibonacci

Pour les besoins de cet exercice, on définit la notion de pseudo arbre de Fibonacci.

Il s'agit, ou bien :

  • D'un arbre binaire de hauteur 0, donc vide.
  • D'un arbre binaire de hauteur 1, donc à un seul nœud.
  • D'un arbre binaire de hauteur \(h\), pour \(h \geqslant 2\) dont
    • un sous-arbre est un pseudo arbre de Fibonacci de hauteur \(h - 1\),
    • l'autre sous-arbre est un pseudo arbre de Fibonacci de hauteur \(h - 2\).

L'étiquette de chaque nœud pourra être totalement quelconque.

Un exemple de hauteur 4

graph TB
    A("8")
    B("3")
    C("5")
    D("2")
    E((" "))
    F("2")
    G("3")
    H((" "))
    I((" "))
    J((" "))
    K((" "))
    L((" "))
    M("2")
    N((" "))
    O((" "))
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    D --> H
    D --> I
    F --> J
    F --> K
    G --> L
    G --> M
    M --> N
    M --> O

Un contre-exemple

Une modification est effectuée, ce n'est plus un pseudo arbre de Fibonacci.

graph TB
    A("8")
    B("3")
    C("5")
    D("2")
    E((" "))
    F("2")
    G("3")
    H((" "))
    I((" "))
    J((" "))
    K((" "))
    L((" "))
    M((" "))
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    D --> H
    D --> I
    F --> J
    F --> K
    G --> L
    G --> M

Exercice

Coder une fonction est_pseudo_Fibonacci qui prend en paramètre ab un arbre binaire représenté à l'aide de la classe Noeud et qui renvoie un booléen :

  • True si ab est un pseudo arbre de Fibonacci,
  • False sinon.
###(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 : /
.9888.128013.128165x/.Tr;nbOylaeêu)*dVM63Am(Pô+02è-@U,59fq!78 N_o=pcwgvF41kRIéhtsàSLCji:E050u0p0/0o0_0n0:0T0Z0n0o0:0:0X010/0_0Y010406050:0r0A0A0o0h0m040=0W0n0r1c0W0j0T020o0A0Y0i0T0+0p1m0h0P0r0p0:050e1j1l1n1p1h0Y04051U1N1X0e1U1h0u0_0$1416181a0.0_0#0.0n1/0.0/1f050 0k0n0p1*1719011.1:1=1:0/1{1}1_0/0h1V0/0.1 1,010O110p0j1A0p01141s0:0Y0o0j1a0G1_2s2u2g212j1}2m0A2o040b0T0C0h0W0Y0W0:0_1v1x0}2q0h0h0p0Z2S1N2z0j1V0e2e2(2b2d2c1`0u2B1a1=0j2l2P1_1%1)15202=0_2@0j0W2{1_0Y2X1V2$2(391i2t1x2}2h320h1m0n1f0T0)2#3d1g3c2A3f213h3j3l0G3o2u3q2$2;013v0o3k040T0y3z2%1h3C3t1a3F3H0T0(3L3B3d3D3R3l0M3V3N3X3P3E0W3i3G3l0x3$3r3e1+3u3+3w3I0R3:3O3?3Q3^3-3I0S3|3(3~3*3,3S0N443s463Z040)0F4b3=2~473_0)3n1O3p3%4c4k4e0)3y4p3A4r4j3g403H0)3K4x3M3;3Y4C1f0)3U4G3W4s4B484L3#4O4z4J4S4f3/4V4I3)4u3{4#3}4t4K4f434*454,4Y0)4a4:4Q3@4Y0G4h4_4A4{3_0G4o394W4%4-0G4w554$4d584F3b1!371N2{2+0u2d2:3)0Z332H0|1(1V360p383p3V055q0}5y4`1a0*1f0}0O5A4+2h0!3l5L4;3g0O1f1L0/0V0Y0:0p0r0u0W0V0%0_0k1w0o0Z0Z0_5Q5F011e040B5;503Q1f0o0k5`3D5@0s0`3$0T660T5c4k0:2x04011F0j0$0W0_1~0r1x5+1s0-2l0L0T0g0h1K0T2Q0T5~0T5V0T6l0T5Y5!5$0T5)5+2m5.0_6r0%3G5Z6w301w013$0667685M210Z0)1f030T0@0~0/1~0O1w2Z0_1w6A0:0/0T0u0-2j0j6j0T0;0T0n00300/0-0h6j0r0h6`1~730o1u2X6567692h5H045J603)5O3I7p4d5T045V5X5Z5#5%6J5,6M0V7f0d7t4k5@5_4O7k3u5}5 7M6!1a62644V6Y6Y7N1a6b1f6e2l6h6 6D0/0r0Y1}0T0B6n0n6p0j7F272l0u0r6r0.7f6-7a0s6V7W7X667Z017m0_5K4O6Z5R7O045~3V8e5=0W7r0_1M8d880*0Z1f0U1w0p7I2h5@7V558686886$6(6y0k6@6_2U7 1u5!7b4~8C8D7Y7S891f2X7,0h0j8j887K8y218s1f6t1K8)7T1f0L8$8V0A0_1f8R5z8V627i8E8V7m0p1=8c398k5{5?1f7L3b8V0j7P8/010W1f0f9g9e040#7f0Z0.8x8q8V8m1f8o8?8f5G8t048v2@9g8~9t9z9h7r2u0u9y5=8(7R9I9m8i9Q8l9j9l5I2M2R9s96889v049x9H5=8+9C8w9F1f638 8T973D8G046)6z6B8M808P3m9?8T8r8X0~7a8#9+989P9c9I9-8-9#8|9I5@8=aa3D8^4L9:040sa37j915U12ah3A8%1f8B4q9@au9I9`9|8J9~1~8N817b0G0T0W0r0T0Eat909R1f0Y0%0V0#aqal9$9d1f0.a#9N989i040Xa.3Y5U6^7y6G7B5*7D5/7F0r7H9Uab9a9X8h7Qad9V049kb3a@9n9p9raqas85aE889maZ0V9Mbd3)aka?4%a+bpbu46a:a=ambv7wa_6F7A5(a}6La 7Gaq9bai5=9Sb8bPa/9Wbr4d9Y6i6-biaV7XbmaY0%by4kbAb+3gb)a-bCbz9K0jbqa)aX04bob_3p9^3)9(9Lb.21acbT3Y0k7P8pb9b45^b6a,a$b=b,1f0Ic45|04a,b~az8}9;cm9h1f0XbBb`5=ao4fb#bk9@b(cocub-ci2hcB54b 9%1faUcK3uc9041mb2cc61b5bW4tbwchcYbs8;cu9mcpcD8Sblav048Ya8cuc6crb{aZa%c,a+c/4q6XaF5=aH1E0~aR7b71160T6/0j6;6?36305/2t1}9?cGc}c#8zc+cScn0.cIcwc bE5WbG5$bI6K5-bLb1bNb69Tc)469Gc:c0467mc@8!dydp5b0e5C5x1Y5i0e5k1N0/5md(2.2)5~1}2(5k1T5E982X0A0V0O0o0*0p0V0.0y1f1F1H1J1L0TaCaz1!3q2{3D0o0u0A1w2R6=2T2u0#0p0h1f1Tedefeh2S0I1c0/29040ven2Qdh1t130p0O2j0Z5-9s1#5t2|46231;1?1^d?3D2D2l2n1f2J0=0Z780Y6_0C0m2e1w5A5wd?3a5zdYeU3)7m7odq217r68e{3Q7v7xdBa|dE6MdIe 3E9ff87Udn8V7#6d6f7)6k6m0W6o6q6s6u1~6x9}6^6C1xf36IbJdF6N6I6Qfq6T9e6W8UaG6%9{6*6,6.6:2S8K6`6|306 db740j7678a12U7e7gay3MfH9,5IeG9ge}9lf1bF7zdC7CbK0_b0cXc7c*cef8bRbie84H8Ve}8D9g0:0u7$017%6g6if(4P98g93laE0T0t720o0TaMf!1~6z6x0Z006B6Dfwf^fz4i3Dgj3Iglgn9DfD320j6r6?6Rege56y0n3+13f#gp6K2@gqa07a6W88gF8T6+7`0T0$eBejfQ7.0reFeH0_eJ0Z0pbc5bfegagGaE0)0f0T0{0n7/0-0$9!6waRg.fX721~2t0h5q7aeFfX6j7bf#001n0k2Xg}4qg(h0gl0T0Gh4h67/gZ2Xge6 1J006D2l1cen7:aR0TgJ0s6A6_gLfu0T7,7.g|gD3)g)8Dgc84dOf*988a95cOa*b7cI8ncbh;ae9BgJaqg31ghz8FfJaIfQ9 8O7a0T8{4yi1c=dSa9cz98cBiaf)g7c=938bc_c!dLc$h?f8a:hvc{bQ1f9o0r9qggdPb,h^cu9-h}fbctdt9J5}b^ipf irb/itiS21ivb60u9Zb!iM9(9*ig3DiI9/iKarh d3c;fI8Hfs8LaLg#7bcNibgla5c?a7dTiMcMb$i 935Zh~b$h-9_i38Ii5i_i7aOaQaScRh,ilb{cgdwa;dyf2f?f4a~f`bMi-bOix98g1iubViVcniAiCd1i}i;f+9)h:3AiEiTjpi$iGiMi+9Ei-i/hzjbe^a68Zifh`9,h|i,55i:cFh=c.i$dxiM9mjta{dDjwf{f7jGf9iUf}bzjFk4isiZbZggaAarjad4h.9wjP2%jR8gj?i)c1jVkndQj-jYk18AkeaWjNieiHksgg06j:a48Vd60,5/gqa#hUkK2:0:1w6_hMho130B5$dfhg13kPg?0Ihs2XkZkQ6Eju0IgB6MbjjmkxkgjOc,cU5~h_jBcZiRk7jSb;kqcj04clj_bwcq2%kck:j+bUa;cylcan8_cCjZkwb%idj1j*jQ88j4j@04jllg4%cUcWk0k kll1lB8:04a(lwbXcobxi-lbjLj;aeawj8lkcEiclQj0j)kA8uj.d2j$46d61F0/d970goddfOg:didf1d3GkCl%isdvltlflqh=j{bHk.dGf|k|f~jAl9h=dKlE99kdcEi kzl6cHjU9wk{kj9%7r320/lZ9.kthwdX5r2(e/5j5u1hd$mB0|0~10123D0uelenep1i1k1H1p050_0A0#gS0/1a0c2p3)0/0!1G0W0^8_6whj1-275Y0`0edX0u0j0f0^g9in0$0h0f2@0/0e1:0e0^0}0Zd}0u2)m%egm*0J0)0M0fh30F0e200~0:1O0$0#0e0)0O0(0ong0:np2pew1}1a0`6n0A0`010e3IeA0heC1x0og.0Z68e?gLgTeJ0n1Ne?68mTmV3GmX01mZ3Dm$m(m*2p0:m-22m/0:m;m?m^m`0}1=m}m 0~n20.n4n6n8nan,0_nengnink18nmnonqnsnunwnyhY2RnB01nDflnFnH3amP1R3q1Xn!mW1a0am!46n+ncm+n/0Zm.0/m:m=0Zm@m_m{n|m~n0o0o22Yo4oDm)o7nfnh0fnjnl0/nnnxnq0G0x0o0F0fo+nzol0pnC0!1n6~0j0#nGnI0T0?hK1c1=0:0ofP2U5BmxnT0WnVnXmxfQ2b0H136/0h6-2Ghf6{5q0j5Z117?1~2lhR0=0,0T1Dp60r0Ol-p67)7bhid{9!po6_730p0d7.0_e5m~6*gxft6l1~6-9q6~gR360W0O1LnM2@h71~2X5q1Qb^6p6`2u13g{pm10ps1417bceM1U0lfv1n8LhKgZeg1%eIp7g:7?0#0H2X7cl.dedg1xgr7aq2eb1(3DeQ251@2y9IeW2F2He!e$1de)e+0.e-7Mmz5g3be?i e`k1f/g0f;dAjuj}f_lAm6lJmbq!7J9;j!kfgE6cgdfihX7=7@6rag6Sjegyfvjufxf55/6OfC6SgLh+aDq+bD0h0-1j0n0 mrl}msagfGr6l(jdg+6-l/dffP9~fS6~1~fV757779hp7dhrf%fdlWqQmcqSk10j7vqp0hj jzdJbSq%dri.h$46g68Ef8gFh*fhgfl.rKqk7e0hhtkChxgk860w338b6 dc0$1n0_d.1~pcnVe70Tr8rarcrT6ahygl6xr)r+0T0jpX6_2t13f3qXgC4 gEs686h*j5c=r}3Gdys10rrbp7splWiomiq$mn9ukplI4kjXkbcs04q*jMk?mhl2cLliiji0jnjNj7sJajaBllcGjTsQiWj^s(dui`rMkuiqmcjDk1iXg0izbgsY9OiLk;lmjolLs+cvjrmirKs.mcc`m9b{sCe@k5bbiYi!s{cdlNiksNi*khh@1fmqqZtaiylKc(sG2hbAl~sD9Iiitp8hiPt5t1txs)lecutDlMtEc3j_k_0kmmtdq(k~rQlCtwl 9Ia:l5t2c-tItYlFtk7s9u1f0QtAt/tClii|ttcdsMj#cGsuswrdt2cJt29-6Paxs#lnlYj3t_jqlvt#bQly0om5t{k}m8tVl0t!ulf~lHugjCl7jK3Mj:i28Hl*l,dbgpqmfPl=dkl^rCtul|u3s*tJs,jht7t,mduncGtclauLsOlostr9svs38dkk1ad6g{0Tq;pxgp0Y5!0/0I0q2b1~0-760Tqbr=0-3:mw5Dd!dZmD0$ov04q56Eu^l.hGiZpwg^g`pw1xhG6h0m2u6_pa5DiJnY0upj0ThJgO106_gRgw6B301u2kqr1$qt3)qveSqy5=qAeY2I0Te#e%qGe,lpl9qL5z7MqOc=rEuUrGs;qUa`m2fyf6rNs^k3uUfcmffeq-r!7*fkfmgMfo6vfraJpYq{a{q}jwr0axr26Uu!beu0u*uOt4u59Brg4VuzkGrkfMrnqni5rrfU72fWfYrxr(rAu|whj%7nf-f8v-uUrIa+s-jys/tXurq#rPwUtW9=sk7qr.b%rXh0rZ7(r#dcr%hqk%1~0BhQgJ6rvx13vA1xp62R0fw t.5646h(r/r;2j7dgpr^78r{sb1wnU3Gs0u(u1s42hx49@s8hrr*qjsc6Bsfk+j|m35:w!x3sm7XsolUrisHtqxepdssmiwjsxxE87c=sAt)fau3sFuui*kBj9xOs kyu$uc8`sysWu8lTs~l`7ltoxLxiwkt8s!x!kFt0uqt@bat?u,k2t6wRx^wTuo8guYt:tfv^jIbhtOx`xFx:7wx,wSt}lVx$ubwnl!mu4ykEsVk?xRuQk2xMu2y5ymi~j=t+tBx dyy3dHv@rHxTmcs@yN7nthuxsUtmwIsXxZx.yvtnlXc^jWxYwqynywkix~uvc?x?xNylllx/8*x;xUxHyBv`s:wNc%jqcxtMsStPtGxSlKl8y/3Dtzz5x)yfy|tFzby10jtStUkcuWyFx}y1t%yJyGy7t-jqt=zfljy@ygyWlJyAz3msu7lSy!zFxGy%j2yqmtl_yElWyYx-r5j#y1dRx%zRiJj/y,y$sPyylswlufyHjCuiukzxuVcflDy lGzvzbuZy+yh6#jduCi8uEwvuH78l?dlzTxPjozIt5wQyLwSzqtbwWz^dNzYz!j(y(z9zHu+uAfKu/u;nNve1uu`u|0Tu~0-v0x60_v34#v5v8mzv9ebmG11p{46mKo}mM3Bot1oezg/dhk(gR0C0+0lnZmUoyn(oB4koXn-m,oHn;oJn?oLoNn`m|oRn n3n5oV0pn9A^oZo9o$ob5Zo)oenrntnvo;ojnAo^onnEo 7soxn$mYA?2hBan.n:1@A}n@oMn_oP1(B3n1B5o3B8o5oEo8o#o%ocBgo+BiohBl0#o?exBooo0WoqnI2#A#1S1W04p2vIp5qe6?p9e?vvpg6BgT7a0}6rnO2YkYhY5Vhmemb^s16r11dd7fiZvChXeg0mpx2U6^2Nu@7bdc0Y2kqkr80Zhlejw h40?gpkP1tfPhahMqkvt1~vN1?qweTi nlpm5AAO3IgR736?eJe(7agtnPnR5rquCJvPz^7m2b0myZyy920dg{e(CPvwp`qll:A)djl@1}vKB-0?1~CG04srnWCQ7cCDhfl+0 1}pN0TvHp41~0Q1YqseO4kvO26vQ98vS2GeZvVqEe(2KqHqJ3bv$e9qNmxqPwKqR5PqTa^qVxwv=5/tsz^s=y5wZdOg(v~w+w0u:flpvw3q@w6fQgzq|xxwd6R2Qr3rhAed5wtg,uGg:rq6}wz73rvfZi8w/rBv|rDDHrFDJrHrJAiz@zprOg2xke|w$7Yw(gbr44yr-h17Xv x8g!jhwEw:Eh7!xB6Y2L0W6hCSgx2Wa1016zhWf3k-DOoF0_u:1L6iv!ghslEj67xDs~i yxxWbDtcztxVz;xXyrtik}yDk=z+z$z-z6x!j6ykyCu9x|Agz9yKEdsKAltuy9t$k6z1bfiByewSx1z*bDkmyyu4yyc-EcDQuXAncPybyRk99!yUyuE=wICNy~E,m7z`zsFrz4x(04sTE*iOzks$zwztcwy0lrE_FetE3+iQF5z=caFozrjqt(FluwzhFjFRzBt`Aos}Aqx{yoAtE^apltz:zclx1flzyMs;z2i-utFClJFiz|x1wri=fKA5daC_rol;AauJdmE5jNC+C-lOy_duF0F*coFnG2FaF7s|meDVimC:0pC=zXGrA2u-jdpZ6AEHi80:sd6E2M7|9!w^6:x*u#ypC.9BzKkCGcD@8H0ziBGNen2Xg$GnG!F_E%kr8,fpv4qO5hv8d;B-mSA:Bu01oAn*nboYBzA{BBoKn^oOn{BHn~BJo1B6n7BMBaBPoao(o*np0eo-o/BXBZom0`o`8!30o~or0T0KgZg.nLg:r893DdCEp)p+18ejp.7/7VeMsv3q1=04B:8oenCe6DCGC$24C(mg10zLv%nYA77.eKCFdYH-eRDpC)5}ocCO7MD72Oi8p)EE1K7bG/GPhpq9hY0mu@14qI8oEQ0~Cfp,0oem6y18pdALalH#1hH#qhqj8^5!0dl.hihNC!2UCIH.H j6GFGH5gnYpx0$rw2jvrhgIgIi0uEGG;7bCV8Zp^In7/2G18IqgtIt5/0-bcIx1NHZd=8vg?IFs1hMen1w130k6jfX0D0/CwpW6BI 0hIT6yb16ApReno)0T0QJmDkmC0}0 AU3qd$AT12JtJqmH0:04.