Réseau routier☘
Exercice☘
Note
Dans cet exercice 1, on met en place les conventions utilisées pour les exercices suivants.
Le schéma ci-dessous représente un réseau de routes entre des villes.
Les flèches signifient que les routes sont à sens unique.
On représente les liaisons entre villes par la liste de listes (matrice) ci-dessous:
routes = [ [0, 0, 0, 0],
[1, 0, 0, 0],
[1, 1, 0, 1],
[1, 1, 0, 0]
]
Cette liste de listes est à interpréter comme suit:
| a | b | c | d | |
|---|---|---|---|---|
| a | 0 | 0 | 0 | 0 |
| b | 1 | 0 | 0 | 0 |
| c | 1 | 1 | 0 | 1 |
| d | 1 | 1 | 0 | 0 |
La "ligne" c, "colonne" a est marquée d'un 1: cela traduit le fait qu'il y a une route allant de c vers a.
La ligne a, colonne c est marquée d'un 0: il n'y a pas de route de a vers c.
A vous☘
Donner le code de la liste de listes correspondant au réseau routier ci-dessous (on prend les villes dans l'ordre alphabétique comme ci-dessus).
Attention
Dans ce réseau, certaines routes n'ont pas de flèches: cela signifie qu'elles sont à double-sens.
On placera donc un 1 par exemple de A vers B mais aussi de B vers A.
Réponse
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 |
1 | 1 | 0 | 1 |
| B | 1 | 0 | 0 | 0 | 0 |
| C | 1 | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 1 | 0 | 1 |
| E | 0 | 1 | 0 | 0 | 0 |
La liste de listes python:
routes = [ [0, 1, 1, 0, 1],
[1, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[0, 0, 1, 0, 1],
[0, 1, 0, 0, 0]
]
Exercice☘
Écrire une fonction python prenant en entrée une liste de listes comme ci-dessus représentant un réseau routier, ainsi que la liste des noms des villes de ce réseau routier et renvoyant la liste des routes.
Une route allant de A vers B sera représentée par le tuple ('A','B').
def les_routes(reseau, villes):
"""
reseau -- matrice traduisant la présence de routes
villes -- liste des noms des villes (même ordre que pour la matrice)
renvoie la liste des routes
sous la forme de tuples (ville d'origine, ville d'arrivée)
"""
Exemple
Pour le deuxième réseau routier de l'exercice précédent:
- l'entrée sera:
la matrice traduisant les routes:
[ [0, 1, 1, 0, 1],
[1, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[0, 0, 1, 0, 1],
[0, 1, 0, 0, 0]
]
['A', 'B', 'C', 'D', 'E']
- la liste obtenue en sortie contiendra tous les couples ('A','B'), ('B', 'A'), ('A','E'), ('A','C'), ('C','A') ... qui traduisent l'existence d'une route entre les deux villes du couple.
Exercice☘
Écrire une fonction python prenant en entrée une matrice représentant un réseau routier, ainsi que la liste des noms des villes de ce réseau routier et renvoyant la liste des routes à sens unique.
La fonction demandée est donc assez proche de celle de l'exercice précédent mais la liste obtenue en sortie ne doit pas contenir les routes à double-sens.