Aller au contenu

Somme maximale de la racine à un nœud

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

Jusqu'à un nœud quelconque

Dans cet exercice, on souhaite obtenir, pour un arbre donné la somme maximale des valeurs de la racine à un nœud quelconque.

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 de la racine à un nœud est \(6\). Il y a parmi d'autres telles sommes : - La racine seule : \(4\) - \(4+(-2) = 2\) - \(4+(-3) = 1\) - \(4+(-3)+(-4) = -3\) - \(4+(-5)+7 = 6\)

Exercice

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

###(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.128013x,59/fq78r;nb _o=ylaepcwgu)vdV4613kRméhtsP(S0à+2-i:050E0w0P0v0Z0u0Q0p0y0u0v0Q0Q0s010P0Z0x010406050Q0B0M0M0v0l0t040T0r0u0B0^0r0n0p020v0M0x0m0p0L0w120l0i0B0w0Q050g0 1113150}0x04051A1t1D0g1A0}0E0Z0D0-0/0;0?0O0Z0A0O0u1R0O0P0{050(0o0u0w1M0:0=011Q1S1U1S0P1!1$1Y0P0l1B0P0O1(1O010h0*0w0n1g0w010-180Q0x0v0n0?0X1Y282a1|1*1 1$220M24040b0p0R0l0r0x0r0Q0Z1b1d0$260l0l0w0y2y1t2f0n1B0g1`2K1@1_1^1Z0E2h0?1U0n212v1Y1J1L0.1)2U0Z2W0n0r2!1Y0x2D1B2I2K2=0~291d2$1}2+0l120u0{0p0I2H2_0|2^2g2{1*2}2 310X342a362I2T013b0v30040p0J3f2J0}3i390?3l3n0p0G3r3h2_3j3x310e3B3t3D3v3k0r2~3m310H3I372`1N3a3N3c3o0j3S3u3V3w3X3P3o0k3#3K3%3M3O3y0f3-383/3F040I0U3@3U2%3:3Y0I331u353J3^403`0I3e453g1E2:1t2!2N0E1_2S3L0y2,2n0#1K1B2/0w2;353B054o0$4w481}0K0{0$0h4y3$400z314J3.490h0{0Q0r110w0q120c0q4c2@4K1}0`040S4O4D3a0{130o2D4,3 4(0{0C0!3~3j4M3o0p504?3j0Q0E0{01570R0r0B0l0p0B1d4:2D0p0E1c0n0N0d0p2D0n0D0r0Z1%5e0p0P0B0x1$0p4{4d3s3T53554 505J0p0Y0p0/0p4T4V0p4Y0Z2 1%2A5O0l0v0y2)1%0V5d2W0p0h0w0B0*1$4|3L54315K5J5M5O5Q2m5S0v0c5U3m5W1%5Y5!5$0p5(5v0n0a0B0E5;3/5?5I0p57013I5K5F3L0n0{5Z5#2W523L4)0d3B0p6o3_0{210h2a0P1s5D3o6B400r0{0s6z6L2|4/0l4;0w6m5J6R4.045|4W4Y6Q4%1*6N046P6J6A6*3w6r666u6J066n6;014F040h3N6)4P6S6#5a0Q0q5g6W6/6Z0?0r4~2)724-6=046E6G6I4$731*4)5C2=6`5^516|6q754V7h4@6+6O7B3E6?6t7a2=6:7p7d0{0W7F6p4S4U2m4X5 4!6v3/4)4+6J7c3k7S0B77797Y404)0C6X7v7%6~0Z4I7b7x7S4V7V0c7Q3/6,020u0P0m80497|2m7-4^047s467v7=7{7z7U6(7`7M016,6.7K7%7y6$7;7L7i6}6r0%5b0n87746$7~3S0g4A4v4f8K0g4i1t0P4k8P2Q2L0v1#8M4i1z4C7C0?2D0M0q6F0K4W0O0J0{1l1n1p1r5B4y1G360$0(0*0,3L0E2a0A0w0l0{3t101n150F130Z6G1%700n2F0Z5k0w0u5:1u971x8`1K3j1,1T1V1X8!3j2j21230{2p0T0y0l0_0P2q0t1`1c4y4u8!2?4x8J9x3L6~4H8b1*4~6A7$7x4R8j6%7W4#4x6|7!9X7j7,9#8n7/8e3g478#019Z6Y9=8x6h6k595b5)0p795i5k5m5o215r5ta55x5z1%9^5E6|6h8g5L5N0v5P7T1%5T5V5i64aq6s67695*5,5.9l7J467%am8g5`aq6$5~60av5Xay6@5%a56b6d6f40aJ506k8v8s7H5$9/016x8D6!7l0n6Ha.7N6-a?7(049;7t6{8n6~2D5x0l8C8m8x7yaz6^8r6|6,7Pb59{0n0o0{8l7o8x9.9 9{0M0Z0{3}bn3ja-be3Ebh04bj9,9?0{7#a}8g7%bmbkbf899)4Z9+4e9-bDa+8t76786U4=bt6w4_a_6~700la_bT7*bV6Va_7e0{7gbw7R7k0n6Fa;7nbBbl4_6y6_ana(044H0v0B84a+8pa+bpbra%bQ040C7:6_1t9S8L2K8Y4h0%0)0+368Ncp8}04.