On considère un ensemble de voitures sur une file à sens unique. Une file ##L## de longueur ##n## est représentée par ##n## cases. Une case peut contenir au plus une voiture. Lorsqu’une case d’indice ##i## de la file est occupée par une voiture, ##L[i]## vaut ##True##, sinon ##L[i]## vaut ##False##.
Afin de comparer plus efficacement les files représentées par des listes de booléens, on remarque que ces listes représentent un codage binaire où ##True## correspond à ##1## et ##False## à ##0##.
a) Soit L une liste représentant une file de longueur ##n## et ##i## un entier tel que ##0 \leq i \leq n##.
Définir en Python la fonction ##occupe(L, i)## qui renvoie ##True## lorsque la case d’indice ##i## de la file est occupée par une voiture et ##False## sinon.
b) Combien existe-t-il de files différentes de longueur ##n## ? Justifier votre réponse
c) Écrire la fonction ##versEntier(L)## prenant une liste de booléens en paramètre et renvoyant l’entier correspondant.
Par exemple, l’appel ##versEntier([True, False, False])## renverra ##4##.
d) On veut écrire la fonction inverse de ##versEntier##, transformant un entier en une liste de booléens.
Que doit être au minimum la valeur de ##taille## pour que le codage obtenu soit satisfaisant ? On suppose que la valeur de ##taille## est suffisante. Quelle condition booléenne faut-il écrire en quatrième ligne du code ci-dessous ?
def versFile(n, taille):
res = [False] * taille
i = taille - 1
while ....:
if n % 2 != 0: # % est le reste de la division euclidienne de n par 2
res[i] = True
n = n // 2 # // est le quotient de la division euclidienne de n par 2
i -= 1
return res
Cet exercice est inspiré du sujet de la filière MP, Mines Ponts 2017. L’énoncé du sujet est accessible en cliquant-ici, le corrigé associé en cliquant-ici.
Besoin d’aide ?
a) La case d’indice ##i## contient la valeur à retourner.
b) Définir une boucle sur la liste en pensant à la notation binaire.
c) Envisager une exécution pas à pas du programme pour mieux l’analyser, en gardant en mémoire la question précédente.
d) Envisager une exécution pas à pas du programme pour mieux l’analyser, en gardant en mémoire la question précédente.
Correction détaillée
a) Comme la file est représentée par une liste, on peut accéder directement à l’état d’une position en utilisant son indice, sans avoir besoin de parcourir toute la liste, ce qui nous donne :
def occupe(L, i):
"""
Fonction qui vérifie si la position i dans la liste L est occupée.
:param L: Liste représentant la liste de positions
:param i: Position à vérifier
:return: True si la position est occupée, False sinon
"""
return L[i]
b) Prenons l’exemple d’une file de longueur ##3##.
Pour la case d’indice ##0##, on a deux possibilités, soit elle est occupée (##True##) soit elle est vide (##False##).
Pour la case d’indice ##1##, on a également deux possibilités, occupée ou vide
Pour la case d’indice ##2##, on a également deux possibilités, occupée ou vide
Ainsi, pour chaque case, il y a 2 choix possibles.
Le nombre total de combinaisons est donc :
Pour une file de longueur ##n##, chaque position peut prendre 2 états : occupée (##True##) ou vide (##False##).
Par conséquent, le nombre total de files possibles est ##2^n## pour une longueur de ##n##.
c) On considère l’exemple suivante ##L = [True, True, False, True]##
En convertissant en binaire on obtiens : ##1101_b = 1\times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 8 + 4 + 0 + 1 = 13##
Nous allons utiliser deux variables ##result## et ##puissance##. Voici les étapes importantes :
– À chaque étape de la boucle ##for## on ajoute à ##result## la valeur de puissance si la valeur binaire est ##1##
– À chaque étape de la boucle ##for## on multiplie par ##2## la variable ##puissance##
def versEntier(L):
"""
Convertit une séquence de bits en entier.
:param L: Chaîne de caractères composée de '0' et '1' représentant un nombre binaire (ex: '1101')
:return: Entier correspondant
"""
result = 0
puissance = 1
for bit in reversed(L):
result = result + int(bit) * puissance
puissance = puissance * 2
return result
assert versEntier("1101") == 13
assert versEntier("101010") == 42
assert versEntier("11111111") == 255
assert versEntier("0") == 0
assert versEntier("1") == 1
print("Tous les tests ont réussi !")d) Pour un codage sur ##3## bits, la valeur maximale est ##111_b = 4 + 2 + 1 = 7 = 2^3 – 1##. Cela correspond à ##L = [True, True, True]##.
Pour un codage sur ##x## bits, la valeur maximale vaut ##2^x -1##. On doit donc avoir : ##n \leq 2^{taille} – 1##
On considère l’exemple suivant : ##taille = 4## et ##L = [True, True, True, True]##.
On a ##1101_b = 8 + 4 + 0 + 1 = 13##.
-
Première étape de la boucle ##while : i = 3##. Le reste vaut ##13%2 = 1##. Le quotient vaut ##13//2 = 6##.
-
Deuxième étape de la boucle ##while : i = 2##. Le reste vaut ##6%2 = 0##. Le quotient vaut ##6//2 = 3##.
-
Deuxième étape de la boucle ##while : i = 1##. Le reste vaut ##3%2 = 1##. Le quotient vaut ##3//2 = 1##.
-
Quatrième étape de la boucle ##while : i = 0##. Le reste vaut ##3%2 = 1##. Le quotient vaut ##3//2 = 0##.
La condition booléenne à écrire est : ##while\: i\geq0##. On peut aussi écrire la condition ##while\: n>0##.