Table des matières

Meilleur parcours dans une grille (variante dynamique)

Il est question ici de l'exercice 2 du sujet 0 de l'épreuve terminale de NSI. Dans le sujet, on aborde le problème à la façon de la programmation dynamique. Mais, à la dernière question, on implémente en utilisant une récurrence ce qui n'est pas la meilleure façon de faire. On tente ici l'approche dynamique.

Je reprends les premières questions à l'identique

Présentation

  • On considère un tableau de nombres de n lignes et p colonnes.
  • Les lignes sont numérotées de 0 à n – 1 et les colonnes sont numérotées de 0 à p – 1.
  • La case en haut à gauche est repérée par (0, 0) et la case en bas à droite par (n – 1, p – 1).
  • On appelle chemin une succession de cases allant de la case (0, 0) à la case (n – 1, p – 1), en n'autorisant que des déplacements case par case : soit vers la droite, soit vers le bas.
  • On appelle somme d'un chemin la somme des entiers situés sur ce chemin.

Par exemple, pour le tableau T suivant :

4 1 1  3
2 0 2 1
3 1 5 1
  • Un chemin est (0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3) (en gras sur le tableau) ;
  • La somme du chemin précédent est 14.
  • (0, 0), (0, 2), (2, 2), (2, 3) n’est pas un chemin.

L'objectif de cet exercice est de déterminer la somme maximale pour tous les chemins possibles allant de la case (0, 0) à la case (n – 1, p – 1).

Question 1

On considère tous les chemins allant de la case (0, 0) à la case (2, 3) du tableau T donné en exemple.

  1. Un tel chemin comprend nécessairement 3 déplacements vers la droite. Combien de déplacements vers le bas comprend-il ?
  2. La longueur d’un chemin est égal au nombre de cases de ce chemin. Justifier que tous les chemins allant de (0, 0) à (2, 3) ont une longueur égale à 6.

Question 2

En listant tous les chemins possibles allant de (0, 0) à (2, 3) du tableau T, déterminer un chemin qui permet d'obtenir la somme maximale et la valeur de cette somme.

Question 3

On veut créer le tableau T' où chaque élément T'[i][j] est la somme maximale pour tous les chemins possibles allant de (0, 0) à (i, j).

  1. Compléter et recopier sur votre copie le tableau T' donné ci-dessous associé au tableau T précédent,
  2. Justifier que si j est différent de 0, alors :
    T'[0][j] = T[0][j] + T'[0][j-1]

Tableau T' à compléter :

4 5 6 ?
6 ? 8 10
9 10 ? 16

Question 4

Justifier que si i et j sont différents de 0, alors :
T'[i][j] = T[i][j] + max(T'[i-1][j], T'[i][j-1]).

Question 5

Changement ici : on va utiliser la programmation dynamique au lieu de la récursivité. Le sujet évoque un tableau T' qui sert à l'explication mais n'est pas utilisé dans la version récursive. Nous devons maintenant créer ce tableau. Mais nous ne pouvons pas l'appeler T'… Nous l'appellerons T2.

Écrire une fonction somme_max(T) qui :

  1. initialise T2 aux mêmes dimensions que T, rempli de 0,
  2. initialise T2[0][0],
  3. initialise la première ligne de T2,
  4. initialise la première colonne de T2,
  5. parcours les T2[i][j] pour 1 <= i < n et 1 <= j < p et les complète,
  6. renvoie le contenu de T2[n-1][p-1].