Samedi 15 janvier PCSI
Devoir surveillé no 2 − Correction
Problème 1 : Étude de trafic routier
Partie I. Préliminaires
1. On peut représenter une file de voitures par une liste de booléens, True représentant la présence d’une voiture et
False représentant une absence de voiture. Par exemple [True, False, True] pourrait représenter une file de 3
places avec une voiture au début et à la fin, et un espace vide entre les deux.
2. On peut écrire, par exemple :
1 A = [ True , False , True , True ] + 6 * [ False ] + [ True ]
ou
1 A = [ True , False , True , True , False , False , False , False , False , False , True ]
pour représenter la situation de la Figure 1.
3. Par exemple :
1 def occupe (L , i ):
2 return L [ i ]
Cette fonction renvoie True s’il y a True en position i dans la liste L et donc s’il y a une voiture en position i dans
la file. Et inversement avec l’absence de voiture.
4. Pour une file de longueur n, on a 2 situations possibles seulement pour chaque place (une voiture ou pas de voiture).
On a donc 2n listes possibles.
5. Par exemple :
1 def egal ( L1 , L2 ):
2 return L1 == L2
Cette fonction renvoie le booléen associé au test d’égalité entre les deux listes. Si elles diffèrent d’une seule position
au moins, elle renverra False.
6. Le test d’égalité L1 == L2 demande de comparer chaque élément de L1 à l’élément correspondant de L2. La
complexité, dans le pire des cas, est donc linéaire en la taille des listes.
7. La fonction egal renvoie un booléen.
8. On propose :
1 def nombre_occ ( L ):
2 compteur = 0
3 for x in L :
4 if x :
5 compteur += 1
6 return compteur
Lycée Fénelon Sainte-Marie, 2021-2022 1/5 Q. Fortier & A. Sourie, 13 janvier 2022
Devoir surveillé no 2 − Correction MPSI/PCSI
9. On propose :
1 def max_succ ( L ):
2 max = 0
3 i = 0
4 while i < len ( L ):
5 # i est l ’ indice de parcours de la liste
6 max_local = 0
7 j = i
8 while j < len ( L ) and occupe (L , j ):
9 # à partir de i on d é termine la longueur
10 # de la suite de places occup é es
11 max_local += 1
12 j += 1
13 if max_local > max :
14 max = max_local
15 # Pour avancer dans la liste ( indice i ) :
16 if max_local > 1 :
17 i += max_local
18 else :
19 i += 1
20 return max
21
22 # autre possibilit é :
23 def max_succ ( L ):
24 a = 0
25 b = 0
26 for i in range ( len ( L )):
27 if L [ i ]:
28 b +=1
29 else :
30 b =0
31 if b > a :
32 a = b
33 return a
Parie II. Déplacement de voitures dans la file
10. On a :
1 A = [ True , False , True , True , False , False , False , False , False , False , True ]
L’appel avancer(A,False) renvoie la liste :
1 [ False , True , False , True , True , False , False , False , False , False , False ]
Et donc l’appel avancer(avancer(A, False), True) renvoie la liste :
1 [ True , False , True , False , True , True , False , False , False , False , False ].
11. Par exemple :
1 def avancer_fin (L , m ):
2 n = len ( L )
3 Lretour = []
4 for i in range ( m ):
5 Lretour . append ( L [ i ])
6 L2 = avancer ( L [ m : n ] , False )
7 for j in range (n - m ):
8 Lretour . append ( L2 [ j ])
9 return Lretour
Lycée Fénelon Sainte-Marie, 2021-2022 2/5 Q. Fortier & A. Sourie, 13 janvier 2022
Devoir surveillé no 2 − Correction MPSI/PCSI
ou
1 def avancer_fin (L , m ):
2 n = len ( L )
3 L1 = L [:] # Copie de L
4 for i in range ( m +1 , n ):
5 L1 [ i ] = L [i -1]
6 L1 [ m ] = False
7 return L1
ou encore, en version courte :
1 def avancer_fin (L , m ) :
2 return ( L [: m ] + avancer ( L [ m :] , False ))
12. Par exemple :
1 def avancer_debut (L , b , m ) :
2 n = len ( L )
3 Lretour = avancer ( L [0: m +1] , b )
4 for i in range ( m +1 , n ):
5 Lretour . append ( L [ i ])
6 return Lretour
ou
1 def avancer_debut (L , b , m ):
2 n = len ( L )
3 L1 = L [:] # Copie de L
4 for i in range (1 , m +1):
5 L1 [ i ] = L [i -1]
6 L1 [0] = b
7 return L1
ou, en version courte :
1 def avancer_debut (L , b , m ):
2 return ( avancer ( L [: m +1] , b ) + L [ m +1:])
13. Par exemple :
1 def av a n c e r _ d e b u t _ b l o q u e (L , b , m ):
2 for i in range (1 ,m ):
3 if not occupe (L , m - i ):
4 return avancer_debut (L , b , m - i )
5 return L [:]
Partie III. Une étape de simulation à deux files
14. Par exemple :
1 def avancer_files ( L1 , b1 , L2 , b2 ):
2 m = len ( L1 )//2
3 R1 = avancer_fin ( L1 , m )
4 R2 = avancer_fin ( L2 , m )
5 if occupe ( R1 , m -1):
6 R2 = a v a n c e r _ d e b u t _ b l o q u e ( R2 , b2 , m )
7 else :
8 R2 = avancer_debut ( R2 , b2 , m )
9 R1 = avancer_debut ( R1 , b1 , m )
10 return [ R1 , R2 ]
Lycée Fénelon Sainte-Marie, 2021-2022 3/5 Q. Fortier & A. Sourie, 13 janvier 2022
Devoir surveillé no 2 − Correction MPSI/PCSI
ou, plus malin :
1 def avancer_files ( L1 , b1 , L2 , b2 ):
2 m = len ( L1 )//2
3 R2 = avancer_fin ( L2 , m )
4 R1 = avancer ( L1 , b1 ) # Les voitures de L1 ne peuvent pas ê tre bloqu é es
5 if occupe ( R1 , m ):
6 R2 = a v a n c e r _ d e b u t _ b l o q u e ( R2 , b2 , m )
7 else :
8 R2 = avancer_debut ( R2 , b2 , m )
9 return [ R1 , R2 ]
15. L’appel avancer_files(D, False, E, False) renvoie :
1 [[ False , False , True , False , True ] ,[ False , True , False , True , False ]]
Partie IV. Transitions
16. Considérons la situation suivante :
• la file L1 est pleine,
• à chaque étape de la simulation, on ajoute une nouvelle voiture à la file L1,
• une voiture est sur la case m-1 de la file L2.
Dans ce cas, la voiture sur la case m-1 de la file L2 est indéfiniment bloquée.
17. Examinons le temps nécessaire pour que les voitures de la file L2 soient dans la position voulue :
• Les voitures de la file L2 doivent laisser la priorité aux voitures de la file L1, elles restent donc immobiles
jusqu’à l’étape 4 incluse.
• Les voitures de la file L2 commencent à se déplacer à l’étape 5 et arrive dans la position voulue à l’étape 9.
Il n’est donc pas possible d’atteindre la configuration demandée en moins de 9 étapes. Il suffit d’ajouter des voitures
à L1 aux étapes 6, 7, 8 et 9 (et de n’ajouter aucune voiture à L2) pour obtenir la configuration souhaitée en 9
étapes. Conclusion : il faut 9 étapes.
18. Pour obtenir la configuration de droite en une étape à partir d’une configuration C, il faut que les voitures en
position 6 de la configuration de droite soient, dans la configuration C toutes les deux en position 5 dans leur liste,
donc toutes les deux sur le croisement, ce qui est impossible. Il est donc impossible de passer de la configuration
de gauche à la configuration de droite.
Partie V. Atteignabilité
19. Par exemple :
1 def elim_double ( L ) :
2 if L == []:
3 return L []
4 R = [ L [0]]
5 n = len ( L )
6 for i in range (1 , n ):
7 if L [ i ] > L [i -1]: # ou L [ i ] != R [ -1] ou ...
8 R . append ( L [ i ])
9 return R
20. L’appel doublons([1, 1, 2, 2, 3, 3, 3, 5]) renvoie [1, 2, 3, 5]. doublons est une version récursive de
elim_double.
21. Non, car elle ne compare que les valeurs consécutives d’une liste, elle ne peut pas supprimer un doublon de valeurs
si les deux valeurs ne sont pas consécutives.
Lycée Fénelon Sainte-Marie, 2021-2022 4/5 Q. Fortier & A. Sourie, 13 janvier 2022
Devoir surveillé no 2 − Correction MPSI/PCSI
22. On a :
• recherche renvoie un booléen.
• successeurs renvoie une liste de listes de 2 listes de même longueur impaire correspondant à des files.
• espace pointe sur une liste de listes de 2 listes de même longueur impaire correspondant à des files.
• but pointe sur une liste de 2 listes de même longueur impaire correspondant à des files.
23. La recherche par in1 a une complexité linéaire tandis que celle par in2 est dichotomique, donc de complexité
logarithmique. La deuxième est donc préférable.
24. Considérons k le nombre de configurations qui ne sont pas dans espace. On remarque que k est un variant de
boucle (la suite des valeurs de k est une suite d’entiers naturels strictement décroissante), ainsi la boucle ne peut
pas être infinie et termine. La suite des valeurs de k est strictement décroissante car la ligne 6 fait décroître k et
la ligne 9 arrête la boucle si k n’a pas strictement décru (s’il n’a pas strictement décru, comme les doublons sont
supprimés et les listes triées, il y aura égalité à la ligne 9).
25. Par exemple :
1 def recherche ( but , init ):
2 espace = [ init ]
3 if egal ( init , but ):
4 return 0
5 stop = False
6 nb_etapes = 0 # initialisation du nombre d ’é tapes
7 while not stop :
8 ancien = espace
9 espace = espace + successeurs ( espace )
10 espace . sort () # permet de trier espace par ordre croissant
11 espace = elim_double ( espace )
12 stop = egal ( ancien , espace )
13 nb_etapes += 1 # on incr é mente le nombre d ’é tapes
14 if but in espace :
15 return nb_etapes
16 return -1
On peut montrer la correction de cette fonction modifiée en utilisant l’invariant de boucle suivante : « espace
contient toutes les configurations atteignables en nb_etapes étapes ou moins ». La fonction s’arrête à la première
apparition de but dans espace et renvoie bien le nombre minimal d’étapes pour y arriver (on ne sort de la boucle
qu’à la première apparition de but dans espace s’il y est) et -1 s’il n’y apparaît pas.
26. On propose :
1 def avancer (L , b ):
2 # L = une liste ( on suppose que L contient au moins un é l é ment ...)
3 # b = un bool é en
4 Lretour = L [:] # copie de L
5 n = len ( L )
6 for i in range (1 , n ) :
7 Lretour [ i ] = L [i -1]
8 Lretour [0] = b
9 return Lretour
Lycée Fénelon Sainte-Marie, 2021-2022 5/5 Q. Fortier & A. Sourie, 13 janvier 2022
