Aller au contenu

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
###
bksl-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# autres testsbksl-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-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) for j in range(n)] for i in range(n)]bksl-nl attendu = secretpy-undsommepy-undminimalepy-und1(grille)bksl-nl resultat = sommepy-undminimalepy-und1(grille)bksl-nl assert attendu == resultatbksl-nlbksl-nl ∞/∞

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-nlNone

A

Z

Retour en haut de la page