Somme minimale (1)
Une grille carrée étant donnée, remplie d'entiers positifs, on souhaite traverser le carré avec une somme minimale des entiers rencontrés.
Pour cet exercice,
- on souhaite aller du coin supérieur gauche au coin inférieur droit,
- les seuls déplacements autorisés sont →, ↓
\[
\begin{pmatrix}
\mathbf{131} & 673 & 234 & 103 & 18 \\
\mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\
630 & 803 & \mathbf{746} & \mathbf{422} & 111 \\
537 & 699 & 497 & \mathbf{121} & 956 \\
805 & 732 & 524 & \mathbf{37} & \mathbf{331}\\
\end{pmatrix}
\]
Le chemin marqué en gras donne une somme de \(2427\) qui est ici le minimum possible pour cet exercice.
Écrire une fonction somme_minimale_1 qui prend en paramètre une liste de liste grille représentant une grille carrée remplie d'entiers positifs et renvoit la somme minimale spécifiée plus haut.
Exemples
\[
\begin{pmatrix}
\mathbf{1} & \mathbf{5} & 9 \\
10 & \mathbf{3} & 5 \\
10 & \mathbf{2} & \mathbf{3}
\end{pmatrix}
\]
🐍 Console Python
>>> grille = [[1, 5, 9], [10, 3, 5], [10, 2, 3]]
>>> somme_minimale_1(grille)
14
\[
\begin{pmatrix}
\mathbf{131} & 673 & 234 & 103 & 18 \\
\mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\
630 & 803 & \mathbf{746} & \mathbf{422} & 111 \\
537 & 699 & 497 & \mathbf{121} & 956 \\
805 & 732 & 524 & \mathbf{37} & \mathbf{331}\\
\end{pmatrix}
\]
🐍 Console Python
>>> grille = [
... [131, 673, 234, 103, 18],
... [201, 96, 342, 965, 150],
... [630, 803, 746, 422, 111],
... [537, 699, 497, 121, 956],
... [805, 732, 524, 37, 331],
... ]
>>> somme_minimale_1(grille)
2427
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 :pbv(40i2+edxm3s7= 1jo5w_lSnatf-)9h]6,crg.[yPku8/ 050m0l0E0D0i0A0q0t0N0A0D0q0q0s010E0i0c010406050q0V0o0o0D0O0S040B0w0A0V0=0w0C050X0|0~10120`0c041b1i051l0X1l1n1i0`0m0i0e0*0,0.0:0J0i0P0J0A1B0J0E0^050#0d0A0l1w0-0/011A1C1E1C0E1K1M1I0E0d0w0m121J0O1j0E0J0*150q0c0D0C0:0j011O1y010F0%0l0C0D0o0l1I1:1=1`1Q1}1M20220^0a0t0T0O0w0c0w0q0i180C0t0Z1.0O0O0l0N2n1b250C1j0X1,2A0E1*1)1+0m270:1E0C1 2k1I1t1v0+1P2K0i2M0C1$1u1I0c2t1j2y2A2(0{1;2o2S1{2X0O0 0A0^0t0u2x2,0_2+262.1Q2:2=2@0j2`1=2|2y2J01310D2?040t0p352z0`382 0:3b3d0t0g3h372,393n2@0x3r3j3t3l3a0w2;3c2@0L3y2}2-1x303D323e0r3I3k3L3m3N3F3e0W3R3A3T3C3E3o0I3Z2~3#3v040u0h3*3K2T3$3O0u2_1c2{3z3+3?3-0u343{361k2$1b2Q2D0m2H390N1$231j481m462*432z054d0Z2%3!3?0U0^0Z0F3r3J390y2@4x3S3 0F0^0q0w0~0l0z0o2V0i2=4K3`2*4D1{0@040f4C4r2/0^0P0O0%1M4Y3~4U0^0H0b3y0t4;0t4y3B0C0^1a4l3e4@3#0w0^0s3r4?4T300d0^2a4*3=4,4W5a3u4#4%0A4)4|4~3?4V0H4:4=5l4!044H4J0q535r1Q5004524|544Z1Q4V0R0K5p4;5y3m0^0N0}0V0A5x550:5A5C2(5E4+1Q4M0^3:4|064=5Z5b1Q4t040F3D5T5F5N040n5?5!5V4A042V5{5-5^4$4(0l5e3B5H673#5$045(4S5@014V0K4/5)5+5+5M3a5O5Q5S5D6o5A0k5X2{5,5f5_5K6m6o4_5t4I225w5k5U015A0Q6a3 0^0D0c0c1 0m6P5c4X6K6g6F5P0o5R6X5G4-6C6o5/5;0O616A0i6=3B0w5~606t6L0C57040O1=0P666!5|6h0^6Z6f776c4R2{6o4V0M6^3,4`6*0:5n6k2(5*6m5L6~4G6H0l6J7b6278040R7m016c6e7f6L6i7j3?5W7L5s5u6I7E69767A7G7S0^5J6}6g6v7O305g657X7C7E6F6@7U396i7D7:3B7W7@3#7K6l7s6z3B6/5=7!776F0v7%5}0^6|5Y6E70720C747+7a7I6g7d7+7i837A6F4{7z7;4-7p3|7~6D7u6G5v7+7?8s4^0^867`5m7Y876M518L6F645i758E7{0^8D8j84897+0K8W448z8H8T8J047Z8b6L7$8o3u704M8r8X7A4V8i8%6#7v8B8I5c8$4m8(8!8n8.8~8A7R916+7,9c5^8)6y6u0^0G8L8l9f7B0K5o7}7t6g5/2t0E0V0O8^367 7k9a7x8C7E5A9l9o9n8*5c8-3|1b4o0l2A2#9S471u492D2F2B1#1%2D0D1L9V0X480`9,0!0$0(04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)