4-grille
9-prog.dynamique
Somme minimale pour traverser un carré
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 côté gauche au côté droit,
les seuls déplacements autorisés sont →, ↓, ↑
\[\begin{pmatrix}
131 & 673 & \mathbf{234} & \mathbf{103} & \mathbf{18} \\
\mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\
630 & 803 & 746 & 422 & 111 \\
537 & 699 & 497 & 121 & 956 \\
805 & 732 & 524 & 37 & 331\\
\end{pmatrix}\]
Le chemin marqué en gras donne une somme de \(994\) qui est ici le minimum possible pour cet exercice.
Écrire une fonction telle que somme_minimale_2(grille)
renvoie la somme minimale spécifiée plus haut. On garantit que la grille
est carrée et remplie d'entiers positifs.
Exemples
\[\begin{pmatrix}
5 & 2 & 3 \\
\mathbf 2 & \mathbf 0 & 2 \\
3 & \mathbf 2 & \mathbf 1 \\
\end{pmatrix}\]
🐍 Console Python >>> grille = [[ 5 , 2 , 3 ], [ 2 , 0 , 5 ], [ 3 , 2 , 1 ],]
>>> somme_minimale_2 ( grille )
5
\[\begin{pmatrix}
9 & 9 & 0 & 9 & 9 \\
\mathbf{3} & \mathbf{1} & 9 & 9 & 9 \\
5 & \mathbf{1} & 9 & \mathbf{1} & \mathbf{3} \\
7 & \mathbf{1} & 9 & \mathbf{1} & 9\\
9 & \mathbf{1} & \mathbf{1} & \mathbf{1} & 9\\
\end{pmatrix}\]
🐍 Console Python >>> grille = [
... [ 9 , 9 , 0 , 9 , 9 ],
... [ 3 , 1 , 9 , 9 , 9 ],
... [ 5 , 1 , 9 , 1 , 3 ],
... [ 7 , 1 , 9 , 1 , 9 ],
... [ 9 , 1 , 1 , 1 , 9 ],
... ]
>>> somme_minimale_2 ( grille )
14
\[\begin{pmatrix}
131 & 673 & \mathbf{234} & \mathbf{103} & \mathbf{18} \\
\mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\
630 & 803 & 746 & 422 & 111 \\
537 & 699 & 497 & 121 & 956 \\
805 & 732 & 524 & 37 & 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_2 ( grille )
994
Lancer # testsbksl-nlbksl-nlgrille = [[5, 2, 3], [2, 0, 5], [3, 2, 1]]bksl-nlassert sommepy-undminimalepy-und2(grille) == 5bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [9, 9, 0, 9, 9],bksl-nl [3, 1, 9, 9, 9],bksl-nl [5, 1, 9, 1, 3],bksl-nl [7, 1, 9, 1, 9],bksl-nl [9, 1, 1, 1, 9],bksl-nl]bksl-nlassert sommepy-undminimalepy-und2(grille) == 14bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [131, 673, 234, 103, 18],bksl-nl [201, 96, 342, 965, 150],bksl-nl [630, 803, 746, 422, 111],bksl-nl [537, 699, 497, 121, 956],bksl-nl [805, 732, 524, 37, 331],bksl-nl]bksl-nlassert sommepy-undminimalepy-und2(grille) == 994bksl-nlbksl-nlbksl-nldef secretpy-undsommepy-undminimalepy-und2(grille):bksl-nl n = len(grille)bksl-nl colonne = [grille[i][0] for i in range(n)]bksl-nl for j in range(1, n):bksl-nl colonne[0] += grille[0][j]bksl-nl for i in range(1, n):bksl-nl colonne[i] = grille[i][j] + min(colonne[i - 1], colonne[i])bksl-nl for i in range(n - 2, -1, -1):bksl-nl colonne[i] = min(colonne[i], colonne[i + 1] + grille[i][j])bksl-nl return min(colonne)bksl-nlbksl-nlbksl-nlfrom random import randrangebksl-nlbksl-nlfor n in [1, 2, 3, 4, 5, 6, 7, 8, 16, 32, 64]:bksl-nl grille = [bksl-nl [bksl-nl randrange(10py-strpy-str6) py-str (i + 3) py-str (j + 3) py-str (n + 3 - i) py-str (n + 3 - j)bksl-nl for j in range(n)bksl-nl ]bksl-nl for i in range(n)bksl-nl ]bksl-nl attendu = secretpy-undsommepy-undminimalepy-und2(grille)bksl-nl resultat = sommepy-undminimalepy-und2(grille)bksl-nl assert attendu == resultatbksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder
def sommepy-undminimalepy-und2(grille):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlgrille = [[5, 2, 3], [2, 0, 5], [3, 2, 1]]bksl-nlassert sommepy-undminimalepy-und2(grille) == 5bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [9, 9, 0, 9, 9],bksl-nl [3, 1, 9, 9, 9],bksl-nl [5, 1, 9, 1, 3],bksl-nl [7, 1, 9, 1, 9],bksl-nl [9, 1, 1, 1, 9],bksl-nl]bksl-nlassert sommepy-undminimalepy-und2(grille) == 14bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [131, 673, 234, 103, 18],bksl-nl [201, 96, 342, 965, 150],bksl-nl [630, 803, 746, 422, 111],bksl-nl [537, 699, 497, 121, 956],bksl-nl [805, 732, 524, 37, 331],bksl-nl]bksl-nlassert sommepy-undminimalepy-und2(grille) == 994bksl-nlbksl-nl def sommepy-undminimalepy-und2(grille):bksl-nl n = len(grille)bksl-nl colonne = [grille[i][0] for i in range(n)]bksl-nl for j in range(1, n):bksl-nl colonne[0] += grille[0][j]bksl-nl for i in range(1, n):bksl-nl colonne[i] = grille[i][j] + min(colonne[i - 1], colonne[i])bksl-nl for i in range(n - 2, -1, -1):bksl-nl colonne[i] = min(colonne[i], colonne[i + 1] + grille[i][j])bksl-nl return min(colonne)bksl-nlbksl-nl
A
Z