Aller au contenu

Somme maximale entre deux nœuds

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

Depuis et vers un nœud quelconque

Dans cet exercice, on souhaite obtenir, pour un arbre donné la somme maximale des valeurs d'un nœud quelconque à un autre (ou éventuellement lui-même). La somme vide égale à 0 n'est pas acceptée, comme dans les exercices précédents.

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("-5")
    N30("-1")
    N0 --- N10
    N0 --- N11
    N0 --- N12
    N10 --- N20
    N10 --- N21
    N11 --- N22
    N11 --- N23
    N20 --- N30

La somme maximale d'un nœud à un autre est \(7+(-5)+4+3=9\)

Exercice

Coder une fonction somme_max_4 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 à un autre nœud, éventuellement lui-même.

⚠ Les fonctions de tri sont interdites dans cet exercice, à vous de faire sans.

🥼 Indice

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

On pensera alors à créer une fonction auxiliaire récursive somme_max_4_aux qui renvoie un tuple (somme_max_tenu, somme_max_libre)

  • tenu : la somme maximale concerne un chemin qui joint la racine
  • libre : tout type de chemin

Ici, chemin se comprend aussi comme vide, allant d'un nœud jusqu'à lui-même !

On pourra alors écrire

🐍 Script Python
def somme_max_4(arbre):
    """Pour l'arbre donné, renvoie
     la somme maximale des valeurs d'un nœud quelconque à un autre (ou pas)
    """
    tenu, libre = somme_max_4_aux(arbre)
    return libre
###(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/fq78r;nb _o=ylaepcwgu)vd46F1`3kRméhtsP(S0à+2C[i:050F0x0R0w0$0v0S0q0z0v0w0S0S0t010R0$0y010406050S0C0O0O0w0m0u040V0s0v0C0{0s0o050h12141618100y04051o1h1r0h1o100F0$0E0:0=0@0_0Q0$0B0Q0v1F0Q0R0~050+0p0v0x1A0?0^011E1G1I1G0R1O1Q1M0R0m1p0R0Q1S1C010i0-0x0o0w0O0x010:1b0S0y0w0o0_0Z1M1}1 1-1U1:1Q1?1^0~0b0q0T0m0s0y0s0S0$1e0o0q0)1{0m0m0x0z2m1h240o1p0h1+2z1(1*1)1N0F260_1I0o1=2j1M1x1z0;1T2J0$2L0o0s2P1M0y2s1p2x2z2%111~2n2R1.2W0m150v0~0q0J2w2+0 2*252-1U2/2;2?0Z2_1 2{2x2I01300w2=040q0L342y10372~0_3a3c0q0G3g362+383m2?0f3q3i3s3k390s2:3b2?0H3x2|2,1B2 3C313d0k3H3j3K3l3M3E3d0l3Q3z3S3B3D3n0g3Y2}3!3u040J0W3)3J2S3#3N0J2^1i2`3y3*3=3,0J333`353|3;2.3U3c0J3f423h3I3t470~0J3p4b3r3}463$4g3w4j444e4n3-3G4q4d3A3 3P4w3R3~4f3-3X4B3Z4D4t0J3(4H4l3L4t0Z3/4N454P3N0Z3_2%4r4y4E0Z414Z4x3+4$4a4)4C4m4W4i4.4I4:3V0Z4p4?4O3T4Q4v4|4U4~4W4A514s4W4G564#4Q4M5a4+4t0L4S5e4J3N0L4Y3{4*5k3V0L4(5o4/4V5r4-5u4@5w3c0L4=5z4}3?5r4{5F525H5C505K575r555P5b5l595T5f5l5d5X5q3c0G5i5#4^5%5n351s2#1h2P2C0F1*2H3A0z2X1_1p5=1q5:2)4j055{0)2$5A0_0M0~0)0i3q5p1.0A2?6e5v3l0i0~0S0s140x0r150d0r5E5.6k010}040U6j68390~160p2s6D5G6A0D0%3:386h3d0q6T6K5L0S0F0~016!0T0s0C0m0q0v006H2s2o1f0o0P0e0q2s0o0E0s0$0x6P3A6X2?6T726T0=0q6o6q0q6t0$2;1R0)0/0E3b0x6(0/0F000C2n0o0a0C2H0j0C0x0v5{0o7t1R0X0q7n0q0w1d6.0U6%0q1~0S0D6~3!706S6T6!013x06736f1U0z0J0~030q0!0*0R1R0i1f2u0$1f0q0x0S0R2o0P1:0o6|0q7B6+2U0R0P0m6|6(2o1R6+7F1(6}4q7X6y6a046c6V6Q6i636y0o6m04771^6s0w6u0G0r7F0d8j3A6A6C8m6E0o6G0m6I8c2)6y6M6O4T8k7R730q8A7P6Y047T0I7.2m6@0P0z7j1y1R810x2:0P1x0,6J8P6 8W8S726^6`7}7D0R0C0y1Q0q0K0U8r6r6t0r7+0o0C6?968t6u1I8J0D0K7O3=7Q8_7S6!3x9o8T8n0~0m0w0z2U8K2`7Y0_6A0e3q9t8F0~1=0i1 0R0S9G9C010s0~0t9P9u046-9A439s9Q8G040o0p0r9K9M9O4j9H5G9S049U9/9$0p0~298U3=8C9}2.9J8o9-a01U6M9r9o9Q8g0$6d9^9W9)9+a30o9N9V6E9=0t9@2%9:5L0O0$0~5)6x6E6A8O4Z9s8e9I8q9f991=0Cal9;9TaK5L9%9w9y2La8aCar3t6naG9h8=aq9QanaNaW04aQ9zaT8Saa9J1Iada#af9*9,aj9.a?am9Tap2`aV3Aat4ga59D0~aA3{aU6U9W9aaJ8E6L0~9FaeaEaZ9Z2yb13!a%bj5G9%9e988w8yb56z0~8D8LaEa_akbf5L6A0#byb304aw2y9Q6A0c7N8dba9$aX98bda(3Abqa|bs9`046tby9 bGa)a+aSb-8BbhbZ3+9v9xa,br5L9=0Yb@3~0~bYb;3!a7bTaUbVaF98blc01.b#b09_0~b*c49~bAby9%ccck1.9Ecd2 bW8uaH9bb+0~bSaBa98fa:0Sbm67bg04b835bb6E7!7$0qagbE0/020B0R0n0t0q5t9!bUbcaI0rbNcIbHb?b|a)blc*ct0_cfcMc9bucwbw0C8zcqa6cmd03la29La`cz04bJd301bLc+bP0~bRa-9#c(9b0r5-bO8Mc.b$aO9{0$8Jdmc?9RaMc/4y6n6p8sbv8xc~d8bB9B9WcTd8dabC5GbLdnc,38bQcBb9c%aE0SaYdua!cg6yc^bnchb)8udIcndtdvdedp04bidrc:d$6rdSdf04dWc$c8cE04acdx9%bdc=dAbp0~cVcXe7c2c)d~d@cL3hbaa.dk0CeadPc-d^eg04e9dSbo3=d*3dc9exd8d_d(aEe9c+7WdY5G8g7-0mev0$dx0s6R2Ue7b(9w0o0BcHd dJaxdQau04c#doaydqeHbs0~cSaibFesdUcAel0 enaDe=ewaIeFevcpd`b!dzf7b^8qdD97c|dGc e`b=6Bd:04dMdbbIfleSfodge1eme cNf1d!cbd|eTf9e;aOb(cjfic5d2fIc1cacwf6dKe/euebfMfPe)etfue~fweza1f2dlc+f#1UeBf*3lfGd.fsfkdbe8c)d?fReGc_epd8fYeLfwa/e5a=fEa)eJfC04ee0neveEf;e}g0f!fxdsf%eqf_cJf{d+epdwfTcefDf|eIeif4gscugker3{ggdjdZaGc3faeAgugp8Ff/fhfQcJe(e.f1b/e$d@goeC9WgVg8b gzd4gBejfRf gEcDgGfA8Jg8a gvb%cif:fLcrfKgQgjfzfOfBf;gYf-6FfN6ugIg e{e0dig/fyd#g=g(dy9?eXg`gPfWhcgSdTdBh80rfVgTeth5c9g#hjb~gcgxhC0~g%gJf$g7f;f gFeN9v0*6(1ghjb,g|gAh1h9f3h4evhYhvh3hWb6hd4qgg9QcP047%0N0*6%6)7 0w0q7-0o7/7;2!2U9y1~1Qa-eDh!h*bzfShJgAhwgZa}hlhjbtfdaGc}hohxhqfl9Yf~i6e42s8 0mhTicg)ie100h650x2z2!iF5;1y5?2C2F2A0w1PiI0h5=iC0)0+0-0S04.