Essence☘

Ces exercices doivent être utilisés pour vous entraîner à programmer. Ils sont généralement accompagnés d'aide et de leur solution pour vous permettre de progresser.

Avant de vous précipiter sur ces solutions dès la première difficulté, n'oubliez pas les conseils suivants :

Avez-vous bien fait un schéma au brouillon pour visualiser le problème posé ?
Avez-vous essayé de rédiger un algorithme en français, avec vos propres mots, avant de vous lancer dans la programmation sur machine ?
Avez-vous utilisé des affichages intermédiaires, des print(), pour visualiser au fur et à mesure le contenu des variables ?
Avez-vous testé le programme avec les propositions de tests donnés dans l'exercice ?
Avez-vous testé le programme avec de nouveaux tests, différents de ceux proposés ?

Rappels

Chaque programme Python doit être sauvegardé sous forme de fichier texte avec l'extension .py.
Enregistrez ce fichier dans le dossier [G05_Algo_Gloutons] avec le nom donné à l'exercice : ProgG05.71.py, ProgG05.72.py, etc...
Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].

Le programme principal doit contenir un appel au module doctest :

##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

Les exercices de cette page sont issus d'une situation commune.

Exercice G05.71 - Problème de l'arrêt☘

Un camion parcourt un trajet d'un point D (départ) à un point A (arrivée). Le plein est toujours fait au départ.

Le long du trajet, on trouve un certain nombre de stations essence s₁, s₂, etc... :

Entre le départ D et la première station s₁ la distance est d₁, entre la station s₁ et la station s₂, la distance est d₂, etc...

Contraintes☘

Le camion peut parcourir une distance totale $d$ avec un plein.
On suppose que les distances d₁, d₂,... sont toutes inférieures ou égales à $d$ .
Le routier doit s'arrêter le moins possible le long de son trajet. Ainsi, il doit prendre de l'essence le moins souvent possible.

Stratégie☘

Notre routier décide de suivre la stratégie suivante : toujours parcourir le plus long trajet possible avec un plein, c'est-à-dire toujours s'arrêter à la dernière station atteignable avec l'essence du réservoir.

Exemple « à la main »☘

On suppose que le camion peut parcourir jusqu'à 100 km avec un plein. De plus, le trajet à suivre est représenté par le schéma ci-dessous (les distances sont en kilomètres) :

Déterminez les arrêts réalisés par le routier en utilisant la stratégie présentée dans le paragraphe précédent.

Réponse
Il part de D, il s'arrête en s₃ (car s₄ ne peut être atteinte avec le plein de départ, la distance de D à s₄ étant de 120 km). Il fait le plein en s₃, roule jusqu'à s₆, fait à nouveau le plein et termine enfin son trajet.
Combien d'arrêts a effectué le routier ? Est-ce le minimum réalisable ?

Réponse
La distance totale à parcourir est 225 km.
Avec deux pleins (donc un seul arrêt), le camion parcourt un maximum de 200 km. Un seul arrêt ne suffit donc pas, il en faut au moins deux.

Par conséquent, deux arrêts réalisent bien le minimum.
Y a-t-il d'autres choix d'arrêts possibles pour réaliser le minimum d'arrêts au cours de ce trajet ?

Réponse
On peut aussi réaliser le minimum d'arrêts en s'arrêtant en s₂ et s₅. Par contre, dans ce cas, ce n'est pas la stratégie « gloutonne » du routier qui est appliquée.

ProgG05.72 - Programmation☘

Complétez la définition de la fonction arrets().

Le paramètre distances_stations est un tableau des différentes distances entre chaque station (ou le départ) et la station suivante (ou l'arrivée) : [Départ -> Station1, station1 -> station2, ..., dernière station -> arrivée].
Avec l'exemple proposé dans la partie précédente, cela donne le tableau [30, 30, 30, 30, 30, 30, 15].
Le paramètre distance_plein représente la distance maximale que peut parcourir le camion avec un plein.
Avec l'exemple proposé dans la partie précédente, cette distance maximale est 100.

def arrets(distances_stations, distance_plein):
    """
    distances_stations - list, tableau des distances entières entre stations
            [Départ-Station1, station1-station2, ..., dernière station-arrivée]
    distance_plein - int, distance maximale parcourue par le camion avec un plein.

    Sortie: list - tableau des stations où prendre de l'essence.
            Les stations sont numérotées de 1 à q
            (station0 serait donc le départ, station q+1 l'arrivée).

    >>> arrets([30, 30, 30, 30, 30, 30, 30, 15] , 100)
    [3, 6]
    >>> arrets([100, 100, 100] , 100)
    [1, 2]
    """

Une piste

Pour ne pas s'emmêler les pinceaux dans les indices, on peut considérer que les stations sont les virgules (départ avant le premier nombre, station 1 = première virgule, dernière station = dernière virgule, arrivée après le dernier nombre).

Un code possible

def arrets(distances_stations, distance_plein):
    """
    distances_stations - list, tableau des distances entières entre stations
            [Départ-Station1, station1-station2, ..., dernière station-arrivée]
    distance_plein - int, distance maximale parcourue par le camion avec un plein.

    Sortie: list - tableau des stations où prendre de l'essence.
            Les stations sont numérotées de 1 à q
            (station0 serait donc le départ, station q+1 l'arrivée).

    >>> arrets([30, 30, 30, 30, 30, 30, 30, 15] , 100)
    [3, 6]
    >>> arrets([100, 100, 100] , 100)
    [1, 2]
    """
    distance_parcourue = 0      # distance parcourue entre deux pleins
    tab_arrets = []
    position_actuelle = 0
    position_finale = len(distances_stations)
    while position_actuelle != position_finale:
        if distance_parcourue + distances_stations[position_actuelle] <= distance_plein:
            distance_parcourue += distances_stations[position_actuelle]
            position_actuelle += 1
        else:
            tab_arrets.append(position_actuelle)
            distance_parcourue = 0
    return tab_arrets

Exercice G05.73 - Stratégie optimale ?☘

Cet exercice a pour but de justifier que la stratégie du routier, à savoir toujours parcourir le plus long trajet possible avec un plein, est optimale dans toutes les situations.

Remarque importante

Cet exercice peut être difficile. Si c'est le cas, prenez le temps de bien étudier et comprendre les raisonnements utilisés dans les solutions proposées.

On note $G = (g_1, g_2, ..., g_p)$ les $p$ stations essence où le camion s'arrête (dans cet ordre) selon le principe glouton évoqué ci-dessus.

On note $O = (o_1, o_2, ..., o_q)$ les $q$ stations essence où le camion s'arrête (dans cet ordre) dans le cas d'une solution optimale (c'est-à-dire utilisant le minimum d'arrêt en station possible).

Remarque

On peut parler d'une solution optimale du problème même en ne sachant pas a priori en déterminer une. Puisqu'il n'y a qu'un nombre fini de possibilités, il en existe nécessairement une (ou plusieurs) meilleure que les autres.

Expliquez pourquoi on a $q \leqslant p$ .

Réponse
Comme $O$ est une solution optimale, le nombre de stations utilisées est minimale donc $q \leqslant p$ .
Justifiez que $O' = (g_1, o_2, ..., o_q)$ est aussi une solution (et qu'elle est optimale).

$O'$ est solution
Le camion peut rouler sans panne d'essence du point de départ à $g_1$ puisque $G$ est une solution.

Il s'agit de prouver que le camion peut rouler sans panne d'essence de $g_1$ à $o_2$ .

D'après la stratégie de notre algorithme, $g_1$ est la station la plus éloignée de D atteignable avec un plein. Comme $o_1$ est une station atteignable à partir de D, elle est nécessairement située entre D et $g_1$ .
La distance entre $o_1$ et $o_2$ est donc nécessairement supérieure ou égale à la distance entre $g_1$ et $o_2$ .
Comme le camion peut parcourir la distance entre $o_1$ et $o_2$ (car $O$ est une solution), il peut parcourir la distance entre $g_1$ et $o_2$ . Ainsi $O'$ est bien une solution de ce problème.

$O'$ est optimale
Si $O'$ est une solution, alors cette solution est optimale puisque le nombre de stations utilisées est le même que pour $O$ .

Remarque : $g_1$ est située avant $o_2$
En effet, supposons que $o_2$ est située avant $g_1 \; et \; o^2$ .
Comme le camion peut parcourir la distance entre $o_2$ et $o_3$ , alors il pourrait parcourir la distance entre $g_1$ et $o_3$ . On pourrait donc supprimer l'étape $o_2$ .
Ainsi, $(g_1, o_3, ..., o_q)$ serait une solution du problème.
Cependant, cette solution fait intervenir moins d'arrêt que $O = (o_1, o_2, ..., o_q)$ . Cela contredit le caractère optimal de la solution $O$ donc la supposition du début est fausse : $o_2$ est forcément située après $g_1$ .
Justifier que $O'' = (g_1, g_2, o_3,... , o_q)$ est aussi une solution (et qu'elle est optimale).

$O''$ est solution
Le camion peut rouler sans panne d'essence de $g_1$ à $g_2$ puisque $G$ est une solution.

Il s'agit de prouver que le camion peut rouler sans panne d'essence de $g_2$ à $o_3$ .

D'après la stratégie de notre algorithme, $g_2$ est la station la plus éloignée de $g_1$ atteignable avec un plein. Comme $o_2$ est une station atteignable à partir de $g_1$ (cf. question précédente), elle est nécessairement située entre $g_1$ et $g_2$ .
La distance entre $o_2$ et $o_3$ est donc nécessairement supérieure ou égale à la distance entre $g_2$ et $o_3$ .
Comme le camion peut parcourir la distance entre $o_2$ et $o_3$ (car $O$ est une solution), il peut parcourir la distance entre $g_2$ et $o_3$ . Ainsi $O''$ est bien une solution de ce problème.

$O''$ est optimale
Si $O''$ est une solution, alors cette solution est optimale puisque le nombre de stations utilisées est le même que pour $O$ .
Expliquer maintenant pourquoi l'algorithme du routier donne une solution optimale.

Réponse
On continue le raisonnement réalisé à la question précédente.

De proche en proche, on arrive au fait que $S = (g_1, g_2, ..., g_q)$ est une solution optimale.

Si on avait $p > q$ , on aurait une station $g_{q+1}$ entre $g_q$ et l'arrivée $A$ à laquelle le camion s'arrête. Or cela n'est pas possible puisque l'algorithme du routier consiste à rouler jusqu'à la dernière station atteignable et A est atteignable depuis $g_q$ puisque $S$ est solution. On en déduit que $p = q$ .

En conclusion, la solution calculée par l'algorithme de notre routier est optimale.