Aller au contenu

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
###
bksl-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-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-nlfrom random import randrangebksl-nlfor n in [1, 2, 3, 4, 5, 6, 7, 8, 16, 32, 64]:bksl-nl grille = [[randrange(10py-strpy-str6)py-str(i+3)py-str(j+3)py-str(n+3-i)py-str(n+3-j) for j in range(n)] for i in range(n)]bksl-nl attendu = secretpy-undsommepy-undminimalepy-und2(grille)bksl-nl resultat = sommepy-undminimalepy-und2(grille)bksl-nl assert attendu == resultatbksl-nlbksl-nl ∞/∞

def sommepy-undminimalepy-und2(grille):bksl-nl ...bksl-nlbksl-nlbksl-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-nlNone

A

Z

Retour en haut de la page