Extraction minière

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

Cout d'extraction minière

On imagine qu'un arbre représente une mine avec ses galeries sous forme hiérarchique. Chaque nœud indique la quantité de minerai disponible.

On suppose que le cout d'extraction de l'étiquette n à la racine coute 0 * n.
On suppose que le cout d'extraction de l'étiquette n d'un nœud situé à une distance d coute d * n.

Une petite mine

Avec l'arbre suivant représentant une mine

graph TB
    N0(5)
    N0 --> N1(9)
    N0 --> N2(5)
    N0 --> N3(11)
    N1 --> N4(4)
    N2 --> N5(1)
    N3 --> N7(8)
    N3 --> N10(2)
    N7 --> M(5)

Le cout d'extraction est :

$5×0 = 0$, plus
$(9+5+11) × 1 = 25$, plus
$(4+1+8+2) × 2 = 30$, plus
$5 × 3 = 15$

Donc un cout total de $0+25+30+15 = 70$

D'un autre côté, le stock récupéré est $5 + (9+5+11) + (4+1+8+2) + 5 = 5 + 25 + 15 + 5 = 50$

En conclusion, les cout et stock de cette extraction sont (70, 50).

Exercice

Coder une fonction extraction qui prend une mine (représentée par un arbre étiqueté) en paramètre et qui renvoie le tuple (cout, stock) de l'extraction.

Indice

On pourra considérer que pour extraire une mine, on peut agir de manière récursive :

il est facile de trouver le stock total connaissant le stock de chacun des sous-arbres et celui de la racine.
il est possible aussi de déterminer le cout total...

Évaluations restantes : ∞/∞

.128013x,59/f.q78r;nb _o=ylaepcwgu)vd*V46F13kRméhtsP(S0+2C-i:E050E0w0R0v0#0u0S0p0y0u0v0S0S0s010R0#0x010406050S0B0O0O0v0l0t040V0r0u0B0{0r0n0p020v0O0x0m0p0N0w150l0i0B0w0S050f12141618100x04051D1w1G0f1D100E0#0D0:0=0@0_0Q0#0A0Q0u1U0Q0R0~050+0o0u0w1P0?0^011T1V1X1V0R1%1)1#0R0l1E0R0Q1+1R010g0-0w0n1j0w010:1b0S0x0v0n0_0Y1#2b2d1 1-221)250O27040a0p0T0l0r0x0r0S0#1e1g0)290l0l0w0y2B1w2i0n1E0f1}2N1`1|1{1$0E2k0_1X0n242y1#1M1O0;1,2X0#2Z0n0r2%1#0x2G1E2L2N2^112c1g2)202.0l150u0~0p0K2K2|0 2{2j2~1-3032340Y372d392L2W013e0v33040p0L3i2M103l3c0_3o3q0p0H3u3k2|3m3A340d3E3w3G3y3n0r313p340I3L3a2}1Q3d3Q3f3r0j3V3x3Y3z3!3S3r0k3(3N3*3P3R3B0e3:3b3=3I040K0W3E1H2?1w2%2Q0E1|2V3O0y2/2q0(1N1E2=0w2@38414b0)4j3{2*010M0~0)0g413)4q0z344w3;4q0n0g0~0w0b1`0v2I0#1f4B4p200}040U4O3X4D0~0O2,0w4U3m4R0C0$3L0p4+0p3W3m0S2g04011o0n0D0r0#1*0U4b1d0c0p0S0R0r0y0M0C0p240p0l0v0x2x0l0R0p0v0D2H0p0u004H4J4L1f0p2D0=0p4Y2Z014*4,4.3O0n0~5b0y4Z4#3O4R0c3E4-4x2 4G4E2d0R1v1x385N4C200r0~0s5M5B3|4X5H5V3j064,5X4P3d0~4~0R0q530+0u5%5O1-5!045$5,2M5:4V204Y0~40630 5/5(4W0452540M5_0r5{5}5Y5 5#6n5;3z5E4K5+2^5.5A5~0_4s040g3Q6r665=6g0r0B0S0q160o2G6G3m0r4z042,6R5C5Q0g5S5U2`6A014R4)6b6y5/4+6e5P045@5I3=5K6X5)6g53556`4q60622^653H4G4I5F2J6b6:1-4R4T7a6(5D6J6L6N0l6P4!7f6o0_4%5z6.746Y6=6K5^5`3p6 5Z0~0X725W7b6t7w1d7B6p040X7L7I6h6~6,7t6/7g0~7R6j7z5|6b7u3=607E7P3n7X6}0M7s7%4q6C2G0R0B0l0n7+7d6@6f5@6k6m7o6s6)0~5L7$7H7,6|6i817A836H7q0~0C3V0f4m4i428n0f451w0R478s2T2O0v1(8p451C4o8g012G0O0q6!0M0w0q0Q0L0~1o1q1s1u0p6+2`1J392%3m0v0E0O1f2A4M1g2,6E0~1C8!8$8(2B0!0{0R1^040G160#5S1*5i5k2c0l4~0l0/590=0l0A0w7_1H8Y1N3m1/1W1Y1!8D3m2m24260~2s0V0y0l0|5g0T0t1}4N7a4h8D2_4k8m9m3O0M7h0#1k3Q0R7~206U4-8f3H7h4b0u1)5q0n6$38063M846C3c9Q1-9S9-3z0y0~0J239:85048V9%6d6(4:0~010Z3Y1*9@1)5h5j0y0p0B2Z5s0w8S580g220y4K1*2D9y9A0n0!020A0R0m9X9Z2B0S5y7T6z7p4r4t0w4v9U3O9/aI3=0g0O0~0q0q2,2AaQ9_7}aL4q0o4R0S0w0uaH6%aD4%9|5-7U7;20aZ7Xa$a(4k6(600h9_7h0E0v0+7+717+9W1bax8*9$3j89a`a|aF8SaV0~0U8j6,6-a/1-6C4u9_aKa)844E4G520q0D0#0)bf4S9_a;6ga?bA4(7:9~aD7?0*7_7{886(bDa#a%9_bbaX6;a~b0bPaD717F3jbl7Iaw2HaybU0~a{bW6I0)beb;8h4Sbi6xbk89bnaGbp4Ab^3n4F04249obA7ebr8EbRbFc36_b!bs0~0bbGa,3va.89cdbTc3bVcb7504bY0vb.04b:cu7v5c0x240Ec9bc04ckcf8i3Lb}6(b a@b96(bqa^aDbtcw0Pc8cMbBc3cqcS2M89a+bIaC9*0~0#c*3rcpa!cecC7(b/cJ1u5^bxbzc$bhcm6ca.c/8E7?0,a#b32q8|1c0w0%2F6Fd39_a04=a61*d127bGc.7VbK5EbM7`7+c)czcBcWcicwa cycsc}c37h2x0x1)0g9Pd3b{9%9)d9aFc?89cVcTcXc55o788*cIdL0~6O6Qc$bHaBdvdF6?c$8773897h7Yb16qch8EaWc{4q68046ae44Q867+e6e8dEe2cNd=b)8a0D6Ld 61b39?9^dS7:d|0~0xenb%6489ed5Mej0y0K0~035l0v0p2=0r6E0n0)7_aeeI5a6v2Zet7W04elb8c+a_dKe96Ic7ere(b_0Ucaefcvd.7ne,9`d`7GeXewd:dTa-d83m6C0z1T1)b16U2.dRd{eXeZdCc~bvdrc9d;6xcoeX2.9ccHd_ep04e|fab#e0ftdFfcdJcAcJ0Ec!e+e:5Jbge~cn7Ueu045F6wfF6^ebe1cvc76#exfqfm0BfofjfKeXd^fw8E7)eyc@eXfNeVfS3O600Ffqfs9}f$cX7-6ien7*f;6{f/e?f`7tb~0~6E0lfq0S6K6Me=f6c;bOf)fT5R0n5TbAd5bkfkf|eYemfzdDd#dFe*f5d3e/gx8Ed}gd7k7mbAe_b(fLf_gLe$7Nec0#0~36e}eWdwfMdygie`a*bgcJf(fP4qcggj7vd~d:8k9H8o2N8B444f108q0*0,0.04.