Cheminement dans un arbre 2
On considère dans cet exercice des arbres enracinés dans lesquels chaque nœud a soit deux enfants (c'est un nœud interne), soit aucun (c'est un nœud externe).
L'illustration ci-dessous présente un tel arbre. Les nœuds internes sont représentés par des cercles, les nœuds externes par des carrés.
Afin de représenter les arbres en machine on numérote les nœuds dans un ordre quelconque. Cette étape étant réalisée, on peut représenter les arbres en machine par des listes d'adjacences (des dictionnaires avec Python) dont les clés sont les numéros des nœuds internes et les valeurs associées une liste contenant les numéros de leurs deux enfants.
L'arbre dessiné ci-dessus est représenté par le dictionnaire {0: [1, 2], 1: [4, 5], 2: [6, 3], 3: [7, 8]}. Les nœuds externes de numéros 4, 5, 6, 7 et 8 ne sont pas des clés du dictionnaire.
Pour calculer les longueurs présentées dans la suite, on utilise des parcours en profondeur.
1. Longueur de cheminement interne
On s'intéresse à la longueur de cheminement interne qui est la somme des longueurs de tous les chemins allant de la racine à un nœud interne. Pour l'arbre dessiné plus haut, cette longueur vaut \(1+1+2=4\).
Écrire une fonction itérative longueur_ci qui prend en paramètre un dictionnaire représentant un arbre et renvoie la longueur de cheminement interne de l'arbre considéré.
Exemples
>>> arbre = {0: [1, 2], 1: [4, 5], 2: [6, 3], 3: [7, 8]}
>>> longueur_ci(arbre, 0, 0)
4
>>> arbre = {2: [0, 1]}
>>> longueur_ci(arbre)
0
>>> arbre = {3: [0, 1], 4: [2, 3]}
>>> longueur_ci(arbre)
1
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 :Lpbv(40i2+edmx3;sN7= 1E}o5w_lSnatf)9h]{R6qcrg.,[éyPku8/ 050n0m0I0H0j0E0s0w0S0E0H0s0s0v010I0j0d010406050s0$0o0o0H0T0Z040F0A0E0$0|0A0G0w020H0o0d0r0w0P0m160T0R0$0m0s050(13151719110d041x1E051H0(1H1J1E110n0j0f0;0?0^0`0M0j0U0M0E1X0M0I0 050,0e0E0m1S0@0_011W1Y1!1Y0I1*1,1(0I0e0A0n191)0T1F0I0M0;1c0s0d0H0G0`0k011.1U010J0.0m0G1k0m1(292b2g1:2j1,2m0o2o040a0w0!0T0A0d0A0s0j1f1h0*270T0T0m0S2J1x2q0G1F0(252V0I2322240n2s0`1!0G2l2G1(1P1R0=1/2)0j2+0G1 1Q1(0d2O1F2T2V30122a1h2;2h2_0T160E0 0w0x2S3410332r361:383a3c0k3f2b3h2T2(013m0H3b040w0q3q2U113t3k0`3w3y0w0h3C3s343u3I3c0B3M3E3O3G3v0A393x3c0Q3T3i351T3l3Y3n3z0u3%3F3*3H3,3!3z0%3:3V3=3X3Z3J0L3{3j3}3Q040x0i3M1G2~1x2/2Y0n2$3u0S1 2y0)1Q1F2}0m2 3g494i0*4q432=010#0 0*0J493;4x0C3c4D3|4x0G0J0 0E1g0U1u0$0T0D0S0j4I4w2h0~040g4X3)4K0 170e2O4%3u4!0K0b3T0w4@0w3(3P0 2l0J2b0I0s0D2@0I0m0T2+1w1y3g4_4E2h0A0 0v3M5b4J4Z0 0O4.3W0G0 0G5n3}4!4=593r5i4Y3l0 0T5h4`3W4z040J3Y5D5c5A045C5w2U5y4(5d4G042@5K5j5M4+4-5P3z5E3}5G5I5O305R4{045r5$5.3W0A5U5W5=5(4)045!0m5s4x4!0X61375B651:4!0N5X5z0`5G0j4C5{5L3H5q6c5S1:5^0 5`5-5|665~0T4,605$6t690 0z4?4^6A6k044O0G4Q0m4S6m3u5e045g6i5Y0`0o0j0 485$064^5?5)0 5+6O5o6l6T6d016p5V5;6s6j3v4|4L4 51535557680`5u6E6$4@6G6_042}0A5I0G0*6N6.6n0`6Q6S6@6U016W0 3e6!756F6^5G0C1W1,6+446`4~0G50527D6 1v7101637J5p5:7J6a7z4x6;6r5a777N4}6|7F54567I6z6^737r7s757W0 7a7c7e5,7V6^7j7R6u7:1g7=7`6o0 0l7 6V6X46747,766^7N6?7@7m7_7g5/7Y7D6}7G7$58327)0 647(7m8b7P0 6b7+7s7.6I4P4R7?5x778f7l6/7N6J6L7f8I7h6:8183787|7d6M8E3D6$775G2O0I4S8c8F8a4N8C8W3%0(4t4p4a8=0(4d1x0I4f8`2!2W1~202Y0H1+8@4d1D4v8P2O0o0D4~0#0m0D0M0q0 1p1r1t1v0w5v321K3h1E0c0H0w7c2Q0j1g0w0n1g0G0Y1-0n2b0:1,2M0T1X0Y0w1v0I0w2H1l9K160j0:0d6M9P0J2j0S0H0S0m0V1G9s040!0A4S0w0Y0S9M2O0w0$2+0w0f552H9A0m9$0j9(9*0W0w9A4i152l9*0w2a0T9B0Y7#6W2+ah0?0w0T9)2@1-0d0$9Xa91ha30J2P8%1-9|af174i4S0:2L0E005 9,9r970y0p1q0d9K0H9 0S9{1hagaH0T0:2laf2D7;8W5v1N4l2:3}1=1Z1#1%983u2u2l2n0 2A0F9^0}9R0!0Z251g494o98314r8;a`5F4Aa37J5U4_8s8J4M8B6K8D4U4Wbm8P4!4$bu5/5 8v044;878Aaq4V2+8S8H8d6/0#0S0 0t1g6y306#7t8t7B7Z6~8mbJ5f8S4!5mby6,7Ob*5t0 9pbL8P7N8X5%7u6)5J8gb+b@6%7S5_8)5Q8AbAb|6(5Hb{8O5/c2b^8ec18S7Nc58o7m7Lb-5}b@777Qc64x6f6hcab+ccb 5T6qcxc46w5#cj6/4!6D8ycy1:5*c9b;cbbJcfcr6uci4r8p04b:3rbU8zb_5VcucOcwcQ5q0A0Ic+6=cgbX8j7!7H8ncVckb/8788bFarbIcS806Rc;b,bT8Zc$6gd5bGasc/9X8SbNbPbRbBcY8Y7,8!5B0+8(8S7o046Zd7bV8J8,bq8.d27ib$dC7n85dv3gc!cK6H0d2kb#d4dF63bxcFb=5Bd0bSc`cG0 0WdsdHbB0K8xdw897m7v7xdY8*bW79dOcm5kcXc}dxdV5:0A6M0nbBd$dF7N8U7~dFbKd=dyd@7yd_d3aOdU5/2F0dbB0g0Kd|d-bM6qc(ebd~2_e1decB8+6v6xdkep7-eA8L8DdP7kc)7Abp8Mb~8G8Re57/a+7}dB5-4^dKc~c$6*eS048ic.e9cRcveMcU3rcp8q7Mc,exef728wdl1088e!d?dNeeei5@0 ehdZd~0H0d9Z7demdTf78h6{7De3d5e7eWfff40482e_dG7pd)eocJdo5Ndq56d5eHfmcZ1xbe8?2V964c0+0-0/04.
2. Longueur de cheminement externe
On s'intéresse à la longueur de cheminement externe qui est la somme des longueurs de tous les chemins allant de la racine à un nœud externe. Pour l'arbre dessiné plus haut, cette longueur vaut \(2+2+2+3+3=12\).
Écrire une fonction itérative longueur_ce qui prend en paramètre un dictionnaire représentant un arbre et renvoie la longueur de cheminement externe de l'arbre considéré.
Exemples
>>> arbre = {0: [1, 2], 1: [4, 5], 2: [6, 3], 3: [7, 8]}
>>> longueur_ce(arbre, 0, 0)
12
>>> arbre = {2: [0, 1]}
>>> longueur_ce(arbre)
2
>>> arbre = {3: [0, 1], 4: [2, 3]}
>>> longueur_ce(arbre)
5
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 :Lpbv(40i2+edmx3;sN7= 1E}o5w_lSnatf)9h]{R6qcrg.,[éyPku8/ 050n0m0I0H0j0E0s0w0S0E0H0s0s0v010I0j0d010406050s0$0o0o0H0T0Z040F0A0E0$0|0A0G0w020H0o0d0r0w0P0m160T0R0$0m0s050(13151719110d041x1E051H0(1H1J1E110n0j0f0;0?0^0`0M0j0U0M0E1X0M0I0 050,0e0E0m1S0@0_011W1Y1!1Y0I1*1,1(0I0e0A0n191)0T1F0I0M0;1c0s0d0H0G0`0k011.1U010J0.0m0G1k0m1(292b2g1:2j1,2m0o2o040a0w0!0T0A0d0A0s0j1f1h0*270T0T0m0S2J1x2q0G1F0(252V0I2322240n2s0`1!0G2l2G1(1P1R0=1/2)0j2+0G1 1Q1(0d2O1F2T2V30122a1h2;2h2_0T160E0 0w0x2S3410332r361:383a3c0k3f2b3h2T2(013m0H3b040w0q3q2U113t3k0`3w3y0w0h3C3s343u3I3c0B3M3E3O3G3v0A393x3c0Q3T3i351T3l3Y3n3z0u3%3F3*3H3,3!3z0%3:3V3=3X3Z3J0L3{3j3}3Q040x0i423)2=3~3-0x3e1y3g3U434b450x3p4g3r4i4a373@3y0x3B4o3D3(3P4t0 0x3L4x2V2}0m2V2/2Y0n2$3u0S1 2y0)1Q1F4H2 3g3M054P0*4W4j2h0#0 0*0J4Y3;4b0C3c4-3|4k0J0 0E1g0U1u0$0T0D0S0m4=4%1:0~040g534r3l0 170e2O593u560K0b3T0w5m0w4z3W0G0 0m0p0I0m0T2+1w4F5o4.2h0A0 0v3M5B4?2h560O5g5q0 0G5N3}565k5A5p440 0T5H5W4b4)040J3Y5!5C5b045Z5V5,0`0A4:042@5+5J5-5d5f5:5{0`5%5)5/305I543H5P5`67015?0 5_5 6b5r045}524F5#5K0 0X5R4k5Y6r6o040N6a5a616e4,6g6z3v696D3u6d042_0I6y6I5@6f656n5|0T5e6l325;01560z5l5n6S685^0G5v5x1v6N3W5E045G6H3W5L6u5-5Q6m6Y5T6/5X5.705$0 6373376t6@3}6J6Q3g666E6i6k771:625*7a6s6K7j5=6P6|6R6Y7h6U5~6X606Z6p6`6)644X6~0 6x7n4(6B7q6F7p7K1:7c7t7e6(7O7i6}7A6!6$5m7V6i4`0G4|0m4~7N6;6?7u7A0o0j0 484F065n7f3u7l7F3r7}5O7P7;6b7S7N6i5t6,5y7D7B045U307{7|6%7v6G856E7/885s5u5w8c7Y6b566q8v7g8m7G7Z7I7#8j7%0 2}0A5)0G0*7-7Q5=5F7N7?4C8F7|7V5%0j6C8n3P8B817V878P7O2@8b6.8z5h0 8g4h8j8^823}5%0C1W1,8q6*8.5z7z8w7C8:837T3r7V567J8#6:7s908-8t8/946E6 7`8_9p8`7o992U9r5D8R8+6i9i6-938C95048y9l8$849D9m8E9o9q8^8H048J8L8N809u8)9x9e719S1g9U7.0 0l8S7@468V8_9Q9#8M7,9V3z9X6=909;9%8+6;9*8+8T9-9N9P8l047)7+8O9Z4b8p9y4_4{4}9@9v7R9)9{2D9T9?8F8X5Y0+4~9t9^a6a8ah3%0(4!4I1G2~1x4K1x0I4MaI2!2W1~202Y0H1+aD0(4K1D4$6E2O0o0D0J0H0#0m0D0M0q0 1p1r1t1v0w8?9a1K3h1E0c0H0w8L2Q0j1g0w0n1g0G0Y1-0n2b0:1,2M0T1X0Y0w1v0I0w2H1lbb160j0:0d7,bg0J2j0S0H510V1Ga_040!0A4~0w0Y0Sbd2O0w0$2+0w0f5w2Hb10mbt0jbv510W0wb14P152l510w2a0Tb20Y6,7?2+b*0?0w0Tbw2@1-0d0$bobY1hbS0J2P0I1ubK1hb)4P4~0:2L0E006kbya^aW0y0p1q0dbb0HbO0Sc4b(17c70T0:2lb(an9$9?5U1N4S2:3}1=1Z1#1%aX3u2u2l2n0 2A0FbH0}bi0!0Z251g4Y4V3(314XaCcJ3W5%4+8d5@5o97444^a7ag9?506W9K8;578d7w6V8d5ia?3D8Wa6b?0Sb^9(9`8+0#0S0 0t1gc_4pd47A890Ga$6+0s0D9A8uab9wdadt550 5Mc/9sd08=90aiar5(7mdw7E7.9gae6j7xdh9W6Y7 90avaj7r6edV9Q7X9H6^96d$719@9b9MdJ018Y8!7Ua6dZ6Y8*d.c~7yc`d%046#a4dWd/75dId=dk8%dR7Ad_e66h5cdPdC8f9.7$dS7MdNd@ea5@6LdLdY902ldn0Idpdr9kd}5SdDe19p9Qd6d89~9Yec8A9Jdi8k7Ad:dEb@2+er5^9C8(dSdd04dfeTdA6vd210eEek5.at5x9+7^aqaxc?aaeK6IeJeX7=9,7_8hdjed9R2kd97:e_d~0X58e%5-eGe$d)4b560We:04e eAfg0 0K9d8@eO6b8|8~dQawe7f38 fb0`9nf09/d?0A7,0negfidN9|apeIdvf79!f4fB6c0 ceff789R2Eeg0g0Keie2eQemfH0$fJ9~dMd`eec fUfD7e5m8i9OdG76dNeu2b6Mf:esdNd#fm6v9Gg86{f-f/fYdx6we)f|9OfseL0dfTgf8Q04fXgb6)0H0dbq8Mf$fagp7Og16+fKam8Kcye^9ad^alfUa24fgB5if(eDgl7~5s0/fwd,ehgTa5fyayfOd.adf=c=7*azfPa0g,fNgJd3gUc)asc2e/dNg(g@3haB4Q4GaFaU4T11aU0+0-0/04.
3. Longueur de cheminement externe pondérée
On affecte désormais un poids à chaque nœud externe. Les différents poids sont donnés par un dictionnaire {numéro_du_noeud_externe: poids}.
On s'intéresse à la longueur de cheminement externe pondérée qui est la somme des longueurs de tous les chemins allant de la racine à un nœud externe, chaque chemin étant pondéré (multiplié) par le poids affecté au nœud externe correspondant.
Considérons par exemple les deux arbres ci-dessous :
Pour l'arbre à gauche, on obtient \(2\times4 +2\times1+2\times9+2\times2= 32\). Pour celui à droite \(1\times9+2\times4+3\times1 +3\times2=26\) .
Écrire une fonction itérative longueur_ce_ponderee qui prend en paramètres un dictionnaire représentant un arbre et un dictionnaire donnant les poids des nœuds externes et qui renvoie la longueur de cheminement externe pondérée de l'arbre considéré.
Exemples
>>> arbre = {0: [1, 2], 1: [3, 4], 2: [5, 6]}
>>> poids = {3: 4, 4: 1, 5: 9, 6: 2}
>>> longueur_ce_ponderee(arbre, poids, 0, 0)
32
>>> arbre = {2: [0, 1]}
>>> poids = {0: 4, 1: 7}
>>> longueur_ce_ponderee(arbre, poids)
11
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 :Lp(40ed3;N 1E}o5_n)h]6,qc[yuvHi2+xms7=wlSatf9{Rrg.*éPkb8/ 050i0h0S0R0G0P0L0m0A0P0R0L0L0N010S0G0d010406050L0D0K0K0R0X0C040Q0q0P0D0~0q0t0m020R0K0d0k0m0W0h180X0z0D0h0L050*1517191b130d041z1G051J0*1J1L1G130i0G0E0?0^0`0|0v0G0Y0v0P1Z0v0S11050.0(0P0h1U0_0{011Y1!1$1!0S1,1.1*0S0(0q0i1b1+0X1H0S0v0?1e0L0d0R0t0|0H011:1W010T0:0h0t1m0h1*2b2d2i1=2l1.2o0K2q040a0m0$0X0q0d0q0L0G1h1j0,290X0X0h0A2L1z2s0t1H0*272X0S2524260i2u0|1$0t2n2I1*1R1T0@1;2+0G2-0t211S1*0d2Q1H2V2X32142c1j2?2j2{0X180P110m0n2U3612352t381=3a3c3e0H3h2d3j2V2*013o0R3d040m0j3s2W133v3m0|3y3A0m0f3E3u363w3K3e0r3O3G3Q3I3x0q3b3z3e0x3V3k371V3n3!3p3B0M3)3H3,3J3.3$3B0)3=3X3@3Z3#3L0U3}3l3 3S040n0g443+2@403/0n3g1A3i3W454d470n3r4i3t4k4c393_3A0n3D4q3F3*3R4v110n3N4z3P4l4u414E3U4H1I301z2;2!0i2(3w0A212A0+1S1H2 0h313i3O054X0,4)4J1=0%110,0T4+3?4d0O3e4_3~4m0T110P1i0Y1w0D0X0s0A0h0s2H0t0,2Q0h4~4:0|10040e5i4t3n11190(2Q5o3w5l0y3O0m4B3Y0t112H0G0i1y4O4`2j5l0u0b3V0m5Q5A5K5q040h0J0S0h0X2-5I325S4 2j0q110N5z5B3 5l0V5v5C110t5?5:115O4H5(5j3x110X5.5T0|4=040T3!645)5U635~5/4d0q4|042_6b605D045s5u6f650167696e5%6g395^6m5p0|6i116l6s6c3J5r0X5t5h5J6J015l0B5`4m626U5L110w6C3w670G4^6I6n6B6*6D016F042{0S6#3Y6:6H6y6t6o6q6O346t5l0p5P5R6z5U2_5Y5!1x6@3 5+045-6-5w115=6P6+6;6X1=5l5}6{6Q6o6x3i5 6.6v6a7h5@047v3t7x3w6_5_7B466L6N7c4d7z7E2W7G7C7J7s607I7O6A6p6M6r706Q6S7o6K7D7+6R6Z7Z4;6G6)7W6.6o7V7w766E6j6`7|6|7M7%4*7111734H065R7T7L04530t550h577;6E5,8k010K0G114a898b7}6u116w8n7`8n7Y7K6V5V5X5Z5#7.7q748b5Q8v7`0q8i0i0s5W792-8B8m8D7!7{4r8M75827n8Z1=7e7g7^3R118U8H7b7l6.7*8^8:8*7(605l6!8t8%8c8E2 0q695e8i7R3B8v8-8n8p4E8L8M8v6%7@817t6,8/6^7 8#7S8O6G0t8V8@8~8_5|9i93942j670O1Y1.8z9w9y5$857)116T8{7U8J7:8+7~9w9L6k9x8?9O3t8v8K929E8%9v8}9n7X8Y9q8d789%9V049S9A8|9t4/9B0491328a9-9.8)96980,8j9X6/9?9;7_5E2Fab9a8X040I9f8q489D939/aa1iac9b9F8,ag7Favakaxamae7eapae9gas9,9j8)8f8had9@6haC9uaQ5456az9d11aKaU7!aw99aTah7H110!9!5F5H9{9}9P7m2{8R8T8G7a9{a44j8u6t672Q0S57a0aA7,aRa!3)0*4-4(4Pbi0*4S1z0S4Ubn2$2Y20222!0R1-bk4S1Fa13w2Q0K0s0T0R0%5b0v0j111r1t1v1x0m7r4*1M3j1G0c0R0m982S0G1i0m0i1i0t0#1/0i2d0=1.2O0X1Z0#0m1x0S0m2J1nb;180G0=0d8ib_0T2l0A0R5a0Z1IbV040$0q570m0#0Ab?2Q0m0D2-0m0E5Z2Jb%0hc60Gc85a0y0mb%4X172n5a0m2c0Xb(0#798p2-cJ0^0m0Xc92_1/0d0Dc1cB1jcv0T2Rb81/cocH194X570=2N0P006~cbbUbA0o0J1s0db;0Rcr0Acn1jcIc-0X0=2ncHaFa,0X5}1P4!2=3 1@1#1%1)bB3Y2w2n2p112C0Qck0 b{0$0C271i4+4%a1334*bhdm3 674@7.6j5A9T46518eaZ9a595b5d5f0h6 a`a25ndO8E6~9{5yae6oa?9(2W9*115N9i9/cS0AcUan8.a.3Y0%0A110l1idZ8$8(9o5V0tbG9x0L0s9_7ad/9c6t9eae5;7.8Ad%6Y04bSaD8)a#b58x7Aa)6d8B9s9!d)ae7Q9!ba9deCd,83e5d:869|en6Wep7p9Wez667?eHeB9ZeL7#7NeT5k87d@ew68eyd~8deIejeKeW61e%849)ePes3F9E9keYe$e=6Q6:6=e!9#9!2neb0Sedef8Ie)7/erata8e8d_d{aIaWeie8a0a68Ne-6(9!fn8WaI7 ehbb6ue104e3fA9~3Y9+a5f0e-b7b9aq8re,e8bdaHe^eke^aM8sfNe77m0d2md|8n6Sd$fK8dfzeNdH4d5xfS04f$d!7i040ub2e6fv6Q9H9Jf?fEd-f+fhfMb3au8)a|0D0id*a=daayf,e$f*9Kfh7ec@f:952G9{0e0ufkfE9leH8Qghf880ete8eEgueqe~3B5Qfu9-f1e.eve8fb2d6?fBe#e^6}7$f?d;eQfh8P8Rb1gNgQa7g3f)gagLaB04gtf}7C0R0dc35egxf/g|8dgW9xgjgoglfXh4aVao7.aM4hg^e*f gzaOb4g48;0;g(e}gAhn7mfWa-gI9=7f9!hwgUhza(e:95hahxaXf5a:a=0q5Gehg)a_e|fsgEgigbeVgdg=7y620-fRe$hCbfdGbj2Xbz1K040cc=0P0Y3!2K0v2zb(1/0F0Dc6180td35Z2zb{2N2#cgcrcJc*6~0m1v0G0mbYcQhCh}0?0v1s2_d7a cpdW0#0Xb,0mcN0G3c0hc@debl0-0/0;04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)