Indice d'une panne

Une sonde interroge à intervalles réguliers l'état de fonctionnement d'un système électronique. Celui-ci peut être en marche ou en panne.

La sonde est programmée pour enregistrer les résultats de ses requêtes dans un log. Il s'agit d'un tableau de booléens (une list Python) dans lequel les valeurs True précèdent les False. La valeur True indique que le système est en marche, False qu'il est en panne.

Une panne nécessite une intervention humaine et ne peut donc pas disparaître seule : elle persiste jusqu'à la fin de l'enregistrement.

🐍 Script Python

#         0     1      2      3      4
log = [True, True, False, False, False]

Lors d'une vérification on constate que le système est en panne : le log contient au moins une valeur False en dernière position. On se demande à quel moment a débuté cette panne.

Dans l'exemple précédent, le premier False est à l'indice 2 : la panne a débuté à l'instant 2.

Écrire la fonction indice_panne qui prend en paramètre le tableau de booléens log et renvoie l'instant du démarrage de la panne.

On garantit que le log n'est pas vide et que, au moment de la vérification, le système est en panne (la dernière valeur du tableau est False).

Attention

La panne du système a aussi corrompu le fichier de log. Vous ne pouvez pas lire plus de 500 valeurs dans celui-ci. Passé ce nombre de lectures, tout nouvel accès lèvera une erreur.

Il est donc important de bien concevoir votre algorithme car les logs utilisés dans les tests secrets peuvent être très longs : un milliard de valeurs !

Exemples

🐍 Console Python

>>> indice_panne([True, False])
1
>>> indice_panne([False, False, False])
0
>>> indice_panne([True] * 10 + [False] * 100)
10
>>> indice_panne([True, True, False, False, False])
2

###

Lancer# Testsbksl-nlassert indicepy-undpanne([True, False]) == 1bksl-nlassert indicepy-undpanne([False, False, False]) == 0bksl-nlassert indicepy-undpanne([True] py-str 10 + [False] py-str 100) == 10bksl-nlassert indicepy-undpanne([True, True, False, False, False]) == 2bksl-nlbksl-nl# Tests supplémentairesbksl-nlfrom random import randrangebksl-nlbksl-nlbksl-nlclass Log(list):bksl-nl def py-undpy-undinitpy-undpy-und(self, longueur, premierpy-undfaux):bksl-nl assert longueur > 1py-und000, "La longueur doit être supérieure à 1000"bksl-nl self.py-undlongueur = longueurbksl-nl self.py-undpremierpy-undfaux = premierpy-undfauxbksl-nl self.py-undcompteurpy-undlectures = 0bksl-nl self.py-undlecturespy-undmax = 500bksl-nlbksl-nl def py-undpy-undlenpy-undpy-und(self):bksl-nl return self.py-undlongueurbksl-nlbksl-nl def py-undpy-undgetitempy-undpy-und(self, i):bksl-nl if type(i) is slice:bksl-nl indices = range(py-stri.indices(self.py-undlongueur))bksl-nl return [self.py-undpy-undgetitempy-undpy-und(k) for k in indices]bksl-nl self.py-undcompteurpy-undlectures += 1bksl-nl if self.py-undcompteurpy-undlectures > self.py-undlecturespy-undmax:bksl-nl raise LookupError(f"Il faut réaliser strictement moins de {self.py-undlecturespy-undmax} lectures dans le tableau")bksl-nl return True if i < self.py-undpremierpy-undfaux else Falsebksl-nlbksl-nl def py-undpy-undsetitempy-undpy-und(self, i, x):bksl-nl raise NotImplementedError("Il est interdit de modifier les valeurs")bksl-nlbksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl return f"[{self.py-undpy-undgetitempy-undpy-und(0)}, {self.py-undpy-undgetitempy-undpy-und(1)}, ..., {self.py-undpy-undgetitempy-undpy-und(self.py-undlongueur - 1)}]"bksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl return self.py-undpy-undstrpy-undpy-und()bksl-nlbksl-nl def py-undpy-unditerpy-undpy-und(self):bksl-nl for i in range(self.py-undlongueur):bksl-nl yield self.py-undpy-undgetitempy-undpy-und(i)bksl-nlbksl-nlbksl-nlfor test in range(20):bksl-nl attendu = randrange(0, 100)bksl-nl faux = randrange(1, 100)bksl-nl log = [True] py-str attendu + [False] py-str fauxbksl-nl assert indicepy-undpanne(log) == attendu, f"Erreur avec {log}"bksl-nlbksl-nl exposant = randrange(6, 10)bksl-nl N = 10py-strpy-strexposantbksl-nl attendu = randrange(1, N)bksl-nl grandpy-undlog = Log(N, attendu)bksl-nl assert (bksl-nl indicepy-undpanne(grandpy-undlog) == attendubksl-nl ), f"Erreur lors de la recherche dans un tableau de 10py-strpy-str{exposant} valeurs"bksl-nlbksl-nl Valider 5/5 TéléchargerTéléverser RechargerSauvegarder

def indicepy-undpanne(log):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert indicepy-undpanne([True, False]) == 1bksl-nlassert indicepy-undpanne([False, False, False]) == 0bksl-nlassert indicepy-undpanne([True] py-str 10 + [False] py-str 100) == 10bksl-nlassert indicepy-undpanne([True, True, False, False, False]) == 2bksl-nlbksl-nldef indicepy-undpanne(log):bksl-nl if not log[0]:bksl-nl return 0bksl-nl bksl-nl debut = 0bksl-nl fin = len(log) - 1bksl-nlbksl-nl while debut <= fin:bksl-nl milieu = (debut + fin) // 2bksl-nl if log[milieu - 1] and not log[milieu]:bksl-nl return milieubksl-nl elif not log[milieu]:bksl-nl fin = milieu - 1bksl-nl else:bksl-nl debut = milieu + 1bksl-nl bksl-nl

A

On utilise une recherche dichotomique itérative.

Il est aussi possible de procéder de manière récursive en introduisant des paramètres :

• debut désigne l'indice inclus du début de la zone de recherche dans le log,

• fin désigne l'indice exclu de la fin de la zone de recherche dans le log.

Afin de ne pas surcharger le premier appel indice_panne(log), on donne des valeurs par défaut à ces paramètres.

🐍 Script Python

def indice_panne(log, debut=None, fin=None):
    if debut is None:
        debut = 0
        fin = len(log)

    if not log[debut]:
        return debut

    milieu = (debut + fin) // 2
    if log[milieu - 1] and not log[milieu]:
        return milieu
    elif not log[milieu]:
        return indice_panne(log, debut, milieu)
    else:
        return indice_panne(log, milieu + 1, fin)

On notera que dans cette version l'indice de fin de la zone de recherche est exclu de celle-ci. La recherche dans la zone (debut, fin) s'apparente alors au fonctionnement classique de la fonction range(debut, fin) : la valeur debut est incluse alors que fin est exclue.

Z

Astuce (1)

Il s'agit d'une recherche dans un tableau trié : les valeurs True sont au début, les False à la fin.

Astuce (2)

Si le log ne contient que des valeurs False, il faut renvoyer 0.

Dans le cas contraire, l'indice cherché est l'unique indice i qui vérifie log[i - 1] and not log[i].