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 :

Il faut comprendre que :

• la première station (indice 0) est à 51 km du départ et le carburant coûte 7,5 centimes/km,
• la deuxième station (indice 1) est 20 km plus loin (donc à 71 km du départ) et le carburant y coûte 7,3 centimes/km,
• la troisième station (indice 2) est 15 km plus loin,
• la dernière station (indice 103) a un prix nul car ce n'est pas une station, c'est l'arrivée.

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 :

• on commence le parcours avec DIST_AVEC_PLEIN = 300
• on a roulé 86 km pour atteindre la station 2, il reste donc 214 km dans le réservoir
• on en reprend 30, donc on a 234 km dans le réservoir
• on parcours 224 km pour atteindre la station 8, il reste donc 10 km dans le réservoir
• on en reprend 100 donc on a 110 km dans le réservoir

Avec 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)].

• On prend 30 km en station 2 à 7,4 centimes / km soit 222 centimes
• on prend 100 km en station 8 à 7,3 centimes / km soit 730 centimes

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))