Exercices
Exercice 1
Exercice 3 du sujet 0 version A - 2024
Code pour tester la Q8.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | G2 = {'A': ['B', 'C', 'H'],
'B': ['A', 'I'],
'C': ['A', 'D', 'E'],
'D': ['C', 'E'],
'E': ['C', 'D', 'G'],
'F': ['G', 'I'],
'G': ['E', 'F', 'H'],
'H': ['A', 'G', 'I'],
'I': ['B', 'F', 'H']
}
tab_itineraires = []
def cherche_itineraires(G, start, end, chaine=[]):
chaine = chaine + [start]
if start == end:
return chaine
for u in G[start]:
if u not in chaine:
nchemin = cherche_itineraires(G, u, end, chaine)
if len(nchemin) != 0:
tab_itineraires.append(nchemin)
return []
def itineraires_court(G, dep, arr):
cherche_itineraires(G, dep, arr)
tab_court = ...
mini = float('inf')
for v in tab_itineraires:
if len(v) <= ...:
mini = ...
for v in tab_itineraires:
if len(v) == mini:
tab_court.append(...)
return tab_court
|
Exercice 2
extrait de la BNS 2024
On considère dans cet exercice un graphe orienté représenté sous forme de listes d’adjacence.
On suppose que les sommets sont numérotés de 0 à n-1.
Par exemple, le graphe suivant :
est représenté par la liste d’adjacence suivante :
adj = [[1, 2], [2], [0], [0]]
Écrire une fonction voisins_entrants(adj, x) qui prend en paramètre le graphe
donné sous forme de liste d’adjacence et qui renvoie une liste contenant les voisins entrants
du sommet x, c’est-à-dire les sommets y tels qu’il existe une arête de y vers x.
Exemples :
>>> voisins_entrants([[1, 2], [2], [0], [0]], 0)
[2, 3]
>>> voisins_entrants([[1, 2], [2], [0], [0]], 1)
[0]
Exercice 3
Dans cet exercice, on considère un graphe non orienté représenté sous forme de listes
d’adjacence. On suppose que les sommets sont numérotés de 0 à n-1.
Ainsi, le graphe suivant:
sera représenté par la liste d’adjacence suivante:
adj = [[1, 2], [0, 3], [0], [1], [5], [4]]
On souhaite déterminer les sommets accessibles depuis un sommet donné dans le graphe.
Pour cela, on va procéder à un parcours en profondeur du graphe.
Compléter la fonction suivante.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | def parcours(adj, x, acc):
'''Réalise un parcours en profondeur récursif
du graphe donné par les listes d'adjacence adj
depuis le sommet x en accumulant les sommets
rencontrés dans acc'''
if x ...:
acc.append(x)
for y in ...:
parcours(adj, ...)
def accessibles(adj, x):
'''Renvoie la liste des sommets accessibles dans le
graphe donné par les listes d'adjacence adj depuis
le sommet x.'''
acc = []
parcours(adj, ...)
return acc
|
Exemples :
>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 0)
[0, 1, 2, 3]
>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 4)
[4, 5]
Exercice 4
Exercice 2 du sujet Concours GEIPI 2024.
Codes du sujet :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 | sentiers = [('Briana', 'La Concorde', 'Grand Palais', 100),
('Teddy', 'Grand Palais', 'Trocadéro', 550),
('Elaine', 'La Concorde', 'Trocadéro', 200),
('Lucie', 'Grand Palais', 'Champ de Mars', 512),
('Sydney', 'Trocadéro', 'Champ de Mars', 100)]
def creer_dico_arcs_sortants(sentiers):
arcs_sortants = ...
for (n, p1, p2, d) in sentiers:
if ... not in arcs_sortants:
arcs_sortants[ ... ] = []
arcs_sortants[ ... ].append((p1, n, d))
if ... not in ... :
arcs_sortants[ ... ] = []
arcs_sortants[ ... ].append( ... )
return arcs_sortants
from math import inf # la constante inf représente (+ infini)
def plus_proche(a_visiter):
min = ...
proche = ''
for (p, (poids, pred, sent)) in a_visiter.items():
if ... <= ... :
( ... , ... ) = ( ... , ... )
return ...
def meilleur_chemin(base, depart, arrivee):
arcs = creer_dico_arcs_sortants(base)
a_visiter = {p: (inf, '', '') for p in arcs.keys()}
a_visiter[depart] = ...
visites = ...
while a_visiter != ... :
# recherche du sommet suivant à visiter
p = ...
(dist,precedent,sentier) = a_visiter[p]
# m-à-j des voisins de p restant à visiter
for (suivant, n, d) in ... :
if ... in a_visiter:
(min,prec,sent) = ...
poids = ... + dist
if ... < ... :
a_visiter[suivant] = (..., ..., ...)
# p passe des sommets à visiter aux sommets visités
visites[p] = a_visiter[p]
del a_visiter[p]
affichage(visites, depart, arrivee)
def affichage(visites, depart, arrivee):
pass
(dist, depuis, nom) = visites[arrivee]
pass
if dist == inf:
pass
return
pass
if depart != arrivee:
pass
pass
pass
|
Pour vous aider à comprendre l'algorithme de Dijkstra, n'oubliez pas cette vidéo d'un youtuber célèbre.
Exercice 5
Exercice 2 du sujet Amérique du Nord J1 2024
Erreur d'énoncé sur la question 10.
Le code à compléter est celui-ci :
| visites = []
def parcours_en_profondeur(d, s):
...
for v in d[s]:
...
parcours_en_profondeur(d, v)
...
|