Aller au contenu

Parcours de tableaux☘

Dans le dossier [NSI], créez le dossier [G05_Algo_Glouton].

Téléchargez le fichier à compléter TPG05.10.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le dossier [G05_Algo_Glouton].

Consignes communes à chaque partie

Le programme principal contient un appel au module doctest : 

##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()
Chacune des fonctions devra passer les tests proposés.
Il faudra aussi ajouter vos propres tests dans le « main » afin de vous entraîner à en réaliser.

Partie A - Un défi☘

Une fois que vous aurez cliqué sur le bouton [Nouveau Jeu], vous devrez parcourir un donjon. Dans chaque salle se trouve une table sur laquelle sont disposées des pièces en or. De plus, les portes vers la salle du bas et celle de droite sont ouvertes et vous permettent de voir les pièces contenues dans ces autres salles.
Attention, choisissez bien la salle suivante car, une fois une porte franchie, celle-ci se referme et vous empêche de revenir en arrière...

    Nombre total de pièces récupérées :

Quelle stratégie avez-vous mis en place pour récupérer le plus grand nombre possible de pièces ?
Notez cette stratégie sur votre cahier puis discutez-en avec votre binôme avant d'appeler l'enseignant.

Partie B - Programmation☘

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.

Un exemple☘

  1. 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

    Dans le main du fichier TPG05.10.py], complétez la représentation de cette grille sous la forme d'un tableau de tableaux ayant 6 éléments :

    1
    grille = ...

  2. En appliquant la stratégie mise en œuvre dans la partie A, quelle somme obtient-on en parcourant cette grille ?

  3. Écrivez sur votre cahier les coordonnées des éléments de la grille successivement parcourus pour obtenir la somme précédente.

Généralisation☘

Programmez le raisonnement précédent en 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, cette fonction renvoie la somme obtenue en se déplaçant d'une case à la suivante en bas ou à droite. Le choix de déplacement s'effectue à partir de la valeur de la case suivante.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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

A-t-on toujours deux choix possibles de déplacement ?

Une autre piste

En considérant une case quelconque de la grille, quels sont les cas possibles pour se déplacer vers la case suivante ?

Encore une piste

Il existe deux possibilités pour identifier que le chemin est terminé :

  • ou bien on est arrivé aux coordonnées de la dernière case (celle en bas à droite) ;
  • ou bien on a parcouru un certain nombre de cases (ce nombre est-il toujours le même ?).

Partie C - Approfondissements☘

Connaître le nombre de pièces d'or obtenu, c'est bien.
Identifier le chemin pour l'obtenir, c'est mieux !

  1. En vous référant au code de la fonction somme_maxi(), complétez le corps de la fonction parcours_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, cette fonction renvoie le chemin obtenu en se déplaçant vers la droite et/ou vers le bas dans le but d'obtenir la plus grande somme possible.
    Ce chemin est représenté par un tableau des coordonnées entières des cases traversées.

    40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
    def parcours_somme_maxi(grille):
    """
    grille - list, Tableau de tableaux ayant le même nombre d'entiers
    Sortie: list - Tableau des couples de coordonnées à parcourir pour
            aller 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
            dans le but d'obtenir une somme maximale
    >>> 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]]
    >>> parcours_somme_maxi(grille)
    [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 5)]
    >>> 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]]
    >>> parcours_somme_maxi(grille)
    [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (2, 5), (3, 5)]
    """
    pass


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

  2. Complétez le corps de la fonction genere_tab_2D() en respectant ses spécifications.
    Cette fonction renvoie une grille de n lignes et m colonnes.
    Chaque case de cette grille contient un entier généré aléatoirement entre borne_inf et borne_sup.

    77
78
79
80
81
82
83
84
85
86
87
88
89
    def genere_tab_2D(n, m, borne_inf, borne_sup):
    """
    n, m - int, entiers strictement positifs
    borne_inf, borne_sup - int, entiers tels que borne_inf < borne_sup
    Sortie: list - Tableau de n tableaux ayant m éléments
            Chaque élément est un entier aléatoire compris entre borne_inf et borne_sup
    """
    pass


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

  3. Dans le programme principal, testez les fonctions somme_maxi() et parcours_somme_maxi() à l'aide de grilles générées aléatoirement par des appels à la fonction genere_tab_2D().

Un exemple

>>> grille = genere_tab_2D(6, 10, 0, 9)

>>> for ligne in grille:
...     print(ligne)
[4, 0, 0, 9, 5, 8, 7, 5, 4, 4]
[3, 6, 7, 8, 2, 8, 5, 4, 6, 6]
[2, 4, 0, 1, 1, 4, 8, 5, 2, 0]
[5, 5, 0, 4, 5, 4, 8, 5, 5, 0]
[3, 0, 5, 4, 0, 9, 4, 9, 7, 9]
[5, 3, 6, 0, 7, 8, 7, 7, 0, 4]

>>> somme_maxi(grille)
93

>>> parcours_somme_maxi(grille)
[(0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 6), (3, 6), (3, 7), (4, 7), (4, 8), (4, 9), (5, 9)]