Ce problème est un exemple d'application de l'algorithme glouton mais rien n'empêche de le traiter avec une autre méthode.
Une personne fait un voyage avec sa voiture. Le voyage est long, il sera obligé de passer prendre du carburant. Il a noté toutes les stations essences présentes sur le chemin et le prix du carburant.
Pour simplifier, on fait comme si les stations étaient juste sur le chemin et n'occasionnent jamais de détour supplémentaire.
On donne le carburant en centimes / km.
En faisant l'hypothèse d'un carburant à 1€50 au litre et une consommation de 5 litres / 100 km, on obtient 7,5 centimes / km. Les prix seront donc de cet ordre en faisant l'hypothèse simplificatrice que la consommation est constante.
La contenance du réservoir est exprimée en km pouvant être effectué. Quand le réservoir contient 85, il faut comprendre qu'en l'état, sans reprendre de carburant, la voiture pourra faire 85 km.
On fixe la distance pouvant être effectuée avec un réservoir plein : DIST_AVEC_PLEIN = 300.
On vous donne ce tableau :
| station | prix | distance |
|---|---|---|
| 0 | 7,5 | 51 |
| 1 | 7,3 | 20 |
| 2 | 7,4 | 15 |
| … | … | … |
| 103 | 0 | 23 |
Il faut comprendre que :
La distance est toujours donnée par rapport à la station précédente. La distance de la première station est donc la distance par rapport au point de départ.
Dans notre implémentation, le tableau aura cette forme (résumé) :
stations = [(7.5,51), (7.3,20), (7.4,15), ...]
Le conducteur devra s'arrêter dans certaines stations et recharger son réservoir. Il n'est pas obligé de remplir entièrement son réservoir.
La réponse devra indiquer l'indice de chaque station où le conducteur s'est arrêté et a pris du carburant, ainsi que la quantité (exprimée en km) de carburant qu'il a pris.
Exemple : parcours = [(2,50), (5,80)] signifie que le conducteur s'est arrêté à la station d'indice 2 et y a pris pour 50 km de carburant, puis il s'est arrêté dans la station d'indice 5 et y a pris pour 80 km de carburant.
Vous allez devoir compléter le programme donner ci-dessous. Je détaille certaines fonctions.
Supposons que le parcours actuel soit [(2,30), (8,100)] cela signifie :
DIST_AVEC_PLEIN = 300Avec ces 110 km d'autonomie on peut atteindre les stations 9, 10 et 11 mais pas la 12 qui est à 111 km de la station 8.
Donc on attend :
>>> stations_atteignables([(2,30), (8,100)], stations) [9, 10, 11]
Supposons que le parcours actuel soit [(2,30), (8,100)].
Le coût total de ce parcours est donc 952 centimes. C'est ce qui doit être renvoyé.
>>> cout_parcours([(2,30), (8,100)], stations) 952
On a dit que le parcours [(2,30), (8,100)] permettait d'atteindre les stations 9, 10 et 11. Il ne permet donc pas d'atteindre la station finale qui est la ligne d'arrivée. Dans ce cas, la fonction renvoie False. Si un parcours permet d'atteindre l'arrivée, la fonction renvoie True.
>>> parcours_termine([(2,30), (8,100)], stations) False
Complétez le programme suivant. Les détails ont déjà été donnés.
Remarque : vous pourrez utiliser DIST_AVEC_PLEIN comme variable globale
À titre de comparaison, un parcours naïf consistant à faire le plein à chaque station rencontrée a un coût total de 21 009 centimes.
DIST_AVEC_PLEIN = 300
def cout_parcours(parcours, stations):
'''
parcours: tableau de (indice station, quantité carburant pris)
stations: tableau des stations
renvoie le cout total pour le parcours considéré
'''
# à compléter
return 0
def stations_atteignables(parcours, stations):
'''
parcours: tableau de (indice station, quantité carburant pris)
stations: tableau des stations
renvoie le tableau des indices des stations pouvant être atteintes à l'issu de ce parcours
'''
# à compléter
return []
def parcours_termine(parcours, stations):
'''
parcours: tableau de (indice station, quantité carburant pris)
stations: tableau des stations
renvoie True si ce parcours permet d'atteindre la station finale, False sinon
'''
# à compléter
return False
def calcul_parcours(stations):
'''
stations: tableau des stations
renvoie un parcours respectant les contraintes et le moins cher possible.
'''
# à compléter
return []
# partie des tests
stations = [
(7.5,51), (7.3,20), (7.4,15), (7.0,58), (6.7,20), (7.1,40), (7.2,23),
(6.5,34), (7.3,49), (6.6,31), (7.6,44), (6.0,15), (7.1,21), (7.8,45),
(6.0,7), (7.6,32), (7.1,19), (6.2,34), (7.2,50), (7.2,10), (7.8,6),
(7.5,43), (7.5,37), (6.0,58), (6.4,8), (7.6,26), (6.7,16), (6.6,17),
(7.7,12), (6.8,25), (7.5,30), (6.3,49), (7.0,26), (6.8,18), (6.8,47),
(7.7,20), (7.9,12), (7.1,16), (7.5,56), (7.7,43), (7.3,59), (6.7,34),
(6.1,26), (6.1,20), (6.4,49), (7.1,11), (7.2,36), (6.0,25), (6.1,18),
(7.9,31), (7.0,12), (7.1,48), (7.8,44), (6.8,3), (7.7,47), (6.6,12),
(7.9,48), (7.9,12), (7.4,48), (7.4,7), (6.7,46), (6.9,46), (7.8,8),
(6.7,18), (6.9,36), (6.3,38), (6.7,26), (7.6,45), (7.2,42), (7.4,3),
(7.4,17), (6.7,6), (6.1,3), (7.2,34), (7.0,18), (6.5,38), (7.7,16),
(6.7,20), (6.8,4), (6.0,22), (7.2,43), (7.7,43), (6.5,15), (6.1,56),
(7.0,24), (7.8,38), (6.3,5), (7.4,39), (6.4,21), (7.9,57), (6.0,6),
(6.0,32), (7.1,56), (6.7,36), (6.4,34), (7.3,7), (7.9,23), (7.5,10),
(7.2,54), (6.6,7), (6.6,21), (7.0,47), (7.0,44), (0,23)
]
# Vérification que l'on obtient bien les résultats attendus
# [(2,30), (8,100)] permet d'atteindre (9,10,11)
assert tuple(stations_atteignables([(2,30), (8,100)], stations)) = (9, 10, 11)
# [(2,30), (8,100)] a un coût de 952
assert cout_parcours([(2,30), (8,100)], stations) = 952
# [(2,30), (8,100)] ne permet pas d'atteindre la fin
assert parcours_termine([(2,30), (8,100)], stations) == False
# calcul du meilleur parcours selon la méthode que vous aurez choisie
parcours = calcul_parcours(stations)
# si ce parcours est bon, il doit terminer :
assert parcours_termine(parcours, stations) == True
# affichage du coût de ce parcours
c = cout_parcours(parcours, stations)
print("Le coût du parcours trouvé est de {} centimes.".format(c))