4-grille
9-prog.dynamique
Somme minimale pour traverser un carré en diagonale
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 telle que somme_minimale_1(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}
\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
Lancer # testsbksl-nlbksl-nlgrille = [[1, 5, 9], [10, 3, 5], [10, 2, 3]]bksl-nlassert sommepy-undminimalepy-und1(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-und1(grille) == 2427bksl-nlbksl-nl# autres testsbksl-nlbksl-nlbksl-nldef secretpy-undsommepy-undminimalepy-und1(grille):bksl-nl n = len(grille)bksl-nl sommes = []bksl-nl cumul = 0bksl-nl for x in grille[0]:bksl-nl cumul += xbksl-nl sommes.append(cumul)bksl-nl for i in range(1, n):bksl-nl ligne = grille[i]bksl-nl nouvellespy-undsommes = [sommes[0] + ligne[0]]bksl-nl for j in range(1, n):bksl-nl nouvellespy-undsommes.append(ligne[j] + min(sommes[j], nouvellespy-undsommes[-1]))bksl-nl sommes = nouvellespy-undsommesbksl-nl return sommes[-1]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 [randrange(10py-strpy-str6) py-str (i + 3) py-str (j + 3) for j in range(n)] for i in range(n)bksl-nl ]bksl-nl attendu = secretpy-undsommepy-undminimalepy-und1(grille)bksl-nl resultat = sommepy-undminimalepy-und1(grille)bksl-nl assert attendu == resultatbksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder def sommepy-undminimalepy-und1(grille):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlgrille = [[1, 5, 9], [10, 3, 5], [10, 2, 3]]bksl-nlassert sommepy-undminimalepy-und1(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-und1(grille) == 2427bksl-nlbksl-nl def sommepy-undminimalepy-und1(grille):bksl-nl n = len(grille)bksl-nl sommes = []bksl-nl cumul = 0bksl-nl for x in grille[0]:bksl-nl cumul += xbksl-nl sommes.append(cumul)bksl-nl for i in range(1, n):bksl-nl sommes[0] = sommes[0] + grille[i][0]bksl-nl for j in range(1, n):bksl-nl sommes[j] = grille[i][j] + min(sommes[j], sommes[j - 1])bksl-nl return sommes[-1]bksl-nlbksl-nl
A
Z