Aller au contenu

Somme maximale d'un nœud à une feuille

🏷️ On considère ici des arbres étiquetés.

Depuis un nœud quelconque

Dans cet exercice, on souhaite obtenir, pour un arbre donné la somme maximale des valeurs d'un nœud quelconque à une feuille.

Un nœud quelconque peut-être aussi la racine elle-même, ou bien une feuille.

Exemple

graph TB
    N0("4")
    N10("-5")
    N11("-3")
    N12("-2")
    N20("7")
    N21("-3")
    N22("-4")
    N23("0")
    N30("-1")
    N0 --- N10
    N0 --- N11
    N0 --- N12
    N10 --- N20
    N10 --- N21
    N11 --- N22
    N11 --- N23
    N20 --- N30

La somme maximale parmi les sommes d'un nœud à une feuille est \(6\). Il y a parmi d'autres telles sommes :

📋 Texte
- La feuille seule : $0$
- $7+(-1) = 6$
- $4+(-3)+0 = 1$
- $-5+(-3) = -8$
- $4+(-5)+7+(-1) = 5$

Exercice

Coder une fonction somme_max_3 qui prend un arbre étiqueté (avec des entiers relatifs) en paramètre et qui renvoie la somme maximale des valeurs d'un nœud quelconque de l'arbre à une feuille.

🥼 Indice

On peut résoudre efficacement ce problème par programmation dynamique.

On pensera alors à créer une fonction auxiliaire récursive somme_max_racine_noeud_feuille qui renvoie un tuple (somme_max_racine_feuille, somme_max_noeud_feuille)

On pourra alors écrire

🐍 Script Python
def somme_max_3(arbre):
    """Pour l'arbre donné, renvoie
     la somme maximale des valeurs d'un nœud quelconque à une feuille
    """
    sm_rf, sm_nf = somme_max_racine_noeud_feuille(arbre)
    return sm_nf
###(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 : ∞/∞
.339.128013]x,59/fq78rnb _o=ylaepcwgu)vd46F13kRméhtsP(S0à+2C[-i:050E0w0P0v0#0u0Q0p0y0u0v0Q0Q0s010P0#0x010406050Q0B0M0M0v0m0t040T0r0u0B0`0r0n050h111315170 0x04051n1g1q0h1n0 0E0#0D0/0;0?0^0O0#0A0O0u1E0O0P0}050*0o0u0w1z0=0@011D1F1H1F0P1N1P1L0P0m1o0P0O1R1B010i0,0w0n0v0M0w010/1a0Q0x0v0n0^0X1L1|1~1,1T1/1P1=1@0}0b0p0R0m0r0x0r0Q0#1d0n0p0(1`0m0m0w0y2l1g230n1o0h1*2y1%1)1(1M0E250^1H0n1;2i1L1w1y0:1S2I0#2K0n0r2O1L0x2r1o2w2y2$101}2m2Q1-2V0m140u0}0p0I2v2*0~2)242,1T2.2:2=0X2^1~2`2w2H012 0v2;040p0J332x0 362}0^393b0p0F3f352*373l2=0f3p3h3r3j380r2/3a2=0G3w2{2+1A2~3B303c0k3G3i3J3k3L3D3c0l3P3y3R3A3C3m0g3X2|3Z3t040I0U3(3I2R3!3M0I2@1h2_3x3)3;3+0I323_343{3:2-3T3b0I3e413g3H3s460}0I3o4a3q3|453#4f3v4i434d4m3,3F4p4c3z3~3O4v3Q3}4e3,3W4A3Y4C4s0I3%4G4k3K4s0X3.4M444O3M0X3^2$4q4x4D0X404Y4w3*4#494(4B4l4V4h4-4H4/3U0X4o4=4N3S4P4u4{4T4}4V4z504r4V4F554!4P4L2(1t2!1g2O2B0E1)2G3z0y2W1^1o5h1p5f5d2(5n0(2#4?1T0K0}0(0i3p4)3;0z2=5F4.2~0i0}0Q0r130w0q140d0q4,2_5G1-0|040S5K5z3k0}150o2r5(4|015#0C0$3/375I3c0p5|5/51010Q0E0}01640R0r0B0m0p0u005,2r2n1e0n0N0e0p2r0n0D0r0#0w5^3z612=5|5|0;0p5P5R0p5U0#2:1Q0(0.0D3a0w680.0E000B2m0n0a0B2G0j0B0w0u5n0n6V1Q0V0p6P1Q0i6K0,1P6r3Z6t5{5|64013w066v0p5Z1T0y0I0}030p0Y0)0P6*1e2t0#1e0p0w0Q0P2n0N1/0n6p0p6%6b2T0P0N0m6p682n1Q6b0v1c5.4p6{6}0^5B045D5~5_5J4i7C385N046z1@5T0v5V0m0v0y2T5S2V6K0E0q6+0B6-6q7K5L0^5#5%7+5)385+0m5-7*2(7,5;0}5?6/5H6u6{5}7:5:6;6@0H782l6k0N0y6L1x1Q7o0w2/0N1w0+7z596:626=820L1;6n7k6P0p0P0B0x6.4S376;826v0!6a0v6y5Q1@6B7S6D6J7u6H6J6L7u8J6k7V7X7l6(2K0p7%7)7 1-8F8G0p8I6x7P1Q6C6E8S0p6I1P8V6N8x6R6T0p6#6Y1e6#8#6)8(6,0u8C8o3;8-8G6@3w8.6|7{0n0}7U7W2K7H3z5#0e3p9k7;9m041;0i1~0P0Q9v7L0r0}0s9F9l7?7^9i8.7L7E0#5E4i9w5:9y9A9C9E9U9G9I9J9#7{5#0Z0c5@7A9j6v9Q9n0)681f9)7;7.9r3*9n8Z9q845 9t9K9x9 9p7_5Y9*7}9O8G9=9z0-a9347L5#9.4Y9:9;9L7O7R7T9T2$9V5 9H049(av7L0n0o0}0i0u0r0v0P9}3;9|a28E7004000!2T0i00aL5!ac9/aoaC5Oas0q0nau2_aw37ayaAa,aCaE04aGaIaKaO9s0}7/7`7;0QaQaSaUaWa{3Z5=ad9:af0i3Ba59W5O670Q0q6dai2xa-3z0r5`2Tbe5 9Xa*9ZaX1Talb9ao5}aqbi0ma+ajab049u9`bfara*bsa.9IbP4xbg5Ra(9o7Xa)0r7!7$9a9caa9{a}bx5*7Obhbj7@8nb)5:b8a!bBbCa6ar5U0qbFbS3Za/c13}a?5Ub,7|5$c89ybib~c0b6aM0}bKaBbDb bG2xakaZanb`apb|cd7Sa)cn3c9$azc42-c67Sc8aNa bMcv5VbOcgaYbJcC2~a%cMcIa3cq3`b`a$b}cwcfck7;ay0Wa:34bn9~04bXa1cra#clb~cTa;7{c3bLbtcE0dcGb+cNcRc!cLcycpcPc}3sa%ced7bI0CbA9P7{7E2r8z0m9_c%b@d2cUdbd5cmd1d9dpbtdccwc_bHb*04dg4p6`ct5:6 710p8t0P67697m8Kbc0n797b2Z2T7W1}b(427BbD0Mdvd37-cicQb-0Qd*dCbmcAc+d@bD8M5Scea07Yb!6Tb$7(9bbl5ydqcad,7=04bkdwdGc=c-3;dk9@dnd/ebd;cx3G0h5w0w2y2Zet5g1x5i2B2E2z0v1Oew0h5h0 eG0)0+0-04.