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 s3o_8bcdufvg/0ly n7apS.r1-me,(P2=4:+jtwki9][5hx)6 050i0C0M0u0P0p0b0r0h0p0u0b0b0H010M0P0v010406050b0j0B0B0u0y0q040w0d0p0j0=0d0s050n0|0~10120`0v041b1i051l0n1l1n1i0`0i0P0l0*0,0.0:0U0P0m0U0p1B0U0M0^050#0g0p0C1w0-0/011A1C1E1C0M1K1M1I0M0g0d0i121J0y1j0M0U0*150b0v0u0s0:0G011O1y010k0%0C0s0u0B0C1I1:1=1`1Q1}1M20220^0a0r0F0y0d0v0d0b0P180s0r0Z1.0y0y0C0h2n1b250s1j0n1,2A0M1*1)1+0i270:1E0s1 2k1I1t1v0+1P2K0P2M0s1$1u1I0v2t1j2y2A2(0{1;2o2S1{2X0y0 0p0^0r0z2x2,0_2+262.1Q2:2=2@0G2`1=2|2y2J01310u2?040r0c352z0`382 0:3b3d0r0I3h372,393n2@0T3r3j3t3l3a0d2;3c2@0X3y2}2-1x303D323e0t3I3k3L3m3N3F3e0f3R3A3T3C3E3o0Q3Z2~3#3v040z0o3*3K2T3$3O0z2_1c2{3z3+3?3-0z343{361k2$1b2Q2D0i2H390h1$231j481m462*432z054d0Z2%3!3?0O0^0Z0k3r3J390N2@4x3S3 0k0^0b0d0~0C0e0B2V0P2=4K3`2*4D1{0@040E4C4r2/0^0m0y0%1M4Y3~4U0^0W0J3y0r4;0r4y3B0s0^1a4l3e4@3#0d0^0H3r4?4T300g0^2a4*3=4,4W5a3u4#4%0p4)4|4~3?4V0W4:4=5l4!044H4J0b535r1Q5004524|544Z1Q4V0S0R5p4;5y3m0^0h0}0j0p5x550:5A5C2(5E4+1Q4M0^3:4|064=5Z5b1Q4t040k3D5T5F5N040V5?5!5V4A042V5{5-5^4$4(0C5e3B5H673#5$045(4S5@014V0R4/5)5+5+5M3a5O5Q5S5D6o5A0K5X2{5,5f5_5K6m6o4_5t4I225w5k5U015A0x6a3 0^0u0v0v1 0i6P5c4X6K6g6F5P0B5R6X5G4-6C6o5/5;0y616A0P6=3B0d5~606t6L0s57040y1=0m666!5|6h0^6Z6f776c4R2{6o4V0D6^3,4`6*0:5n6k2(5*6m5L6~4G6H0C6J7b6278040S7m016c6e7f6L6i7j3?5W7L5s5u6I7E69767A7G7S0^5J6}6g6v7O305g657X7C7E6F6@7U396i7D7:3B7W7@3#7K6l7s6z3B6/5=7!776F0L7%5}0^6|5Y6E70720s747+7a7I6g7d7+7i837A6F4{7z7;4-7p3|7~6D7u6G5v7+7?8s4^0^867`5m7Y876M518L6F645i758E7{0^8D8j84897+0R8W448z8H8T8J047Z8b6L7$8o3u704M8r8X7A4V8i8%6#7v8B8I5c8$4m8(8!8n8.8~8A7R916+7,9c5^8)6y6u0^0A8L8l9f7B0R5o7}7t6g5/2t0M0j0y8^367 7k9a7x8C7E5A9l9o9n8*5c8-3|1b4o0C2A2#9S471u492D2F2B1#1%2D0u1L9V0n480`9,0!0$0(04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)