TP - Version 1

Dans une grille de dimensions n × m, dont chaque case contient un nombre, on part de la case (0, 0) et on se rend dans la case (n-1, m-1). Les seuls déplacements autorisés sont les déplacements vers la droite et vers le bas.

On souhaite emprunter le chemin pour lequel la somme des nombres rencontrés est la plus grande.

Exemple

On considère la grille ci-dessous :

	3	3	6	2	3	3
	8	9	3	4	8	7
	7	7	9	5	9	7
	3	4	2	4	1	6

Un manière optimale de résoudre ce problème en plusieurs étapes est de choisir, à chaque étape (donc à chaque case), la solution qui semble la meilleure, c'est-à-dire la case suivante qui contient la plus grande valeur.

Ainsi, avec la grille précédente :

• À partir de la case (0, 0), on a le choix entre les nombres 3 à droite et 8 en bas. Il est préférable de descendre :
  

  	3	3	6	2	3	3
  	8	9	3	4	8	7
  	7	7	9	5	9	7
  	3	4	2	4	1	6

• À partir de la case (1, 0), on a le choix entre les nombres 9 à droite et 7 en bas. Il est préférable d'aller à droite :
  

  	3	3	6	2	3	3
  	8	9	3	4	8	7
  	7	7	9	5	9	7
  	3	4	2	4	1	6

• À partir de la case (1, 1), on a le choix entre les nombres 3 à droite et 7 en bas. Il est préférable de descendre :
  

  	3	3	6	2	3	3
  	8	9	3	4	8	7
  	7	7	9	5	9	7
  	3	4	2	4	1	6

• etc... jusqu'à arriver à la case en bas à droite de cette grille :
  

  	3	3	6	2	3	3
  	8	9	3	4	8	7
  	7	7	9	5	9	7
  	3	4	2	4	1	6

Le chemin optimal a donc pour somme 63.

Partie A - Application manuelle

Sur un cahier, recopiez la grille ci-dessous puis indiquez le chemin permettant d'obtenir la somme maximale ainsi que la valeur de cette somme.

	1	8	7	8	4	1
	7	3	6	5	3	9
	5	8	5	1	5	7
	3	9	4	1	3	8

Appelez l'enseignant pour lui faire part de votre raisonnement.

Partie B - Programmation

Programmez le raisonnement précédent en copiant, collant et complétant le code de la fonction somme_maxi() dont le paramètre grille est un tableau de tableaux contenant chacun le même nombre d'entiers.
Pour une grille passée en paramètre, ce tableau renvoie la somme obtenue en se déplaçant d'une case à la suivante en bas ou à droite. Le choix s'effectue selon la case ayant la plus grande valeur.

def somme_maxi(grille):
    """
    grille - list, Tableau de tableaux ayant le même nombre d'entiers
    Sortie: int - Somme maximale obtenue en allant de la première à la dernière
            case de la grille en allant uniquement à droite ou vers le bas
            (lorsque c'est possible). Le choix de déplacement s'effectue à partir
            de la valeur de la case suivante
    >>> grille = [[3, 3, 6, 2, 3, 3], [8, 9, 3, 4, 8, 7], [7, 7, 9, 5, 9, 7], [3, 4, 2, 4, 1, 6]]
    >>> somme_maxi(grille)
    63
    >>> grille = [[1, 8, 7, 8, 4, 1], [7, 3, 6, 5, 3, 9], [5, 8, 5, 1, 5, 7], [3, 9, 4, 1, 3, 8]]
    >>> somme_maxi(grille)
    56
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

Une piste

Nommer ligne la ligne de la case « en cours » et colonne sa colonne.
Alors la case de coordonnées (ligne, colonne) est grille[ligne][colonne)].

Une autre piste

Traiter séparément le cas de la dernière ligne ou de la dernière colonne car un seul déplacement est alors possible au lieu de deux.

Encore une piste

Lorsqu'on est sur une case quelconque de coordonnées (ligne, colonne), alors on se déplace sur la case contenant la plus grande valeur entre celle de coordonnées (ligne+1, colonne) et celle de coordonnées (ligne, colonne+1).

Une dernière piste

On pose ligne = 0 et colonne = 0.
On se place sur la case (ligne, colonne).
Tant que ligne et colonne n'ont pas toutes les deux la dernière valeur possible, Alors :

• si la ligne a la dernière valeur possible, on ne va qu'à droite en augmentant colonne de 1 ;

• si la colonne a la dernière valeur possible, on ne va qu'en bas en augmentant ligne de 1 ;

• si la case à droite a une valeur plus grande que celle d'en bas, on va à droite en augmentant colonne de 1 ;

• si la case en bas a une valeur plus grande que celle de droite, on va en bas en augmentant ligne de 1.

Partie C - Plus grande somme ?

En fait, cette méthode ne donne pas toujours le chemin de somme maximale.

Dessinez sur votre cahier un tableau pour lequel le raisonnement développé dans ce TP ne donne pas un chemin de somme maximal.