Combien de 1 ?

On considère un tableau ne contenant que des 0 et des 1. Ce tableau est trié dans l'ordre croissant et il est possible qu'il ne contienne que des 0 ou que des 1.

On souhaite déterminer combien ce tableau compte-t-il de 1 ?

Écrire la fonction compte_uns qui prend en paramètre un tel tableau et renvoie le nombre de 1 qu'il contient.

Attention

Certains des tableaux utilisés dans les tests sont très grands. Une méthode de coût linéaire sera inefficace face à ceux-ci.

On limite donc le nombre de lectures dans chaque tableau à 500. Passé cette valeur maximale, tout nouvel accès provoquera une erreur.

On rappelle à ce titre que le tableau est trié...

Exemples

🐍 Console Python

>>> compte_uns([0, 1, 1, 1])
3
>>> compte_uns([0, 0, 0, 1, 1])
2
>>> compte_uns([0] * 200)
0
>>> compte_uns([1] * 300)
300
>>> compte_uns([0] * 200 + [1] * 500)
500
>>> compte_uns([])
0

###

Lancer # Testsbksl-nlassert comptepy-unduns([0, 1, 1, 1]) == 3bksl-nlassert comptepy-unduns([0, 0, 0, 1, 1]) == 2bksl-nlassert comptepy-unduns([0] py-str 200) == 0bksl-nlassert comptepy-unduns([1] py-str 300) == 300bksl-nlassert comptepy-unduns([0] py-str 200 + [1] py-str 500) == 500bksl-nlassert comptepy-unduns([]) == 0bksl-nlbksl-nl# Tests supplémentairesbksl-nlfrom random import randrangebksl-nlbksl-nlbksl-nlassert comptepy-unduns([]) == 0, "Erreur avec le tableau vide"bksl-nlbksl-nlbksl-nlclass Tableau(list):bksl-nl def py-undpy-undinitpy-undpy-und(self, taille, premierpy-undun):bksl-nl assert taille > 1py-und000, "La longueur doit être supérieure à 1000"bksl-nl assert taille > premierpy-undun, "Le premier 1 doit être dans le tableau"bksl-nl self.py-undtaille = taillebksl-nl self.py-undpremierpy-undun = premierpy-undunbksl-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-undtaillebksl-nlbksl-nl def py-undpy-undeqpy-undpy-und(self, autre):bksl-nl if self.py-undtaille != len(autre):bksl-nl return Falsebksl-nlbksl-nl for i in range(self.py-undtaille):bksl-nl if self.py-undpy-undgetitempy-undpy-und(i) != autre[i]:bksl-nl return Falsebksl-nlbksl-nl return Truebksl-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-undtaille))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(bksl-nl f"Il faut réaliser strictement moins de {self.py-undlecturespy-undmax} lectures dans le tableau"bksl-nl )bksl-nl if i < 0:bksl-nl i = self.py-undtaille + ibksl-nl if not (0 <= i < self.py-undtaille):bksl-nl raise IndexError("L'indice demandé est invalide")bksl-nl return 0 if i < self.py-undpremierpy-undun else 1bksl-nlbksl-nl def py-undpy-undgetitempy-undbispy-undpy-und(self, i):bksl-nl if i < 0:bksl-nl i = self.py-undtaille + ibksl-nl return 0 if i < self.py-undpremierpy-undun else 1bksl-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-undbispy-undpy-und(0)}, {self.py-undpy-undgetitempy-undbispy-undpy-und(1)}, ..., {self.py-undpy-undgetitempy-undbispy-undpy-und(self.py-undtaille)}]"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-undtaille):bksl-nl yield self.py-undpy-undgetitempy-undpy-und(i)bksl-nlbksl-nlbksl-nlfor py-und in range(20):bksl-nl taille = randrange(10py-strpy-str5, 10py-strpy-str6)bksl-nl premierpy-undun = randrange(0, taille)bksl-nl tableau = Tableau(taille, premierpy-undun)bksl-nl attendu = taille - premierpy-undunbksl-nl assert comptepy-unduns(tableau) == attendu, f"Erreur avec {tableau}"bksl-nlbksl-nl Valider 10/10 Télécharger Téléverser Recharger Sauvegarder

def comptepy-unduns(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert comptepy-unduns([0, 1, 1, 1]) == 3bksl-nlassert comptepy-unduns([0, 0, 0, 1, 1]) == 2bksl-nlassert comptepy-unduns([0] py-str 200) == 0bksl-nlassert comptepy-unduns([1] py-str 300) == 300bksl-nlassert comptepy-unduns([0] py-str 200 + [1] py-str 500) == 500bksl-nlassert comptepy-unduns([]) == 0bksl-nlbksl-nldef comptepy-unduns(tableau):bksl-nl if tableau == []:bksl-nl return 0bksl-nlbksl-nl if tableau[0] == 1:bksl-nl return len(tableau)bksl-nlbksl-nl debut = 0bksl-nl fin = len(tableau) - 1bksl-nl while debut <= fin:bksl-nl milieu = (debut + fin) // 2bksl-nl if tableau[milieu] == 0:bksl-nl debut = milieu + 1bksl-nl elif tableau[milieu - 1] == 1:bksl-nl fin = milieu - 1bksl-nl else:bksl-nl return len(tableau) - milieubksl-nlbksl-nl return 0bksl-nlbksl-nl

A

Le premier test permet de traiter le cas des tableaux vides. Le second celui des tableaux ne contenant que des1. On renvoie alors directement la longueur du tableau. Ce cas pourrait être traité par la boucle principale mais ce test initial permet d'optimiser le code.

Le tableau peut être partagé en deux zones (éventuellement vides) : une zone ne contenant que des 0, une autre ne contenant que des 1.

On utilise une recherche dichotomique afin de trouver la position du premier 1, limite entre ces deux zones. Il s'agit de l'unique 1 précédé par un 0. Une fois trouvé on renvoie le nombre de 1.

Si l'on quitte la boucle sans avoir renvoyé de résultat c'est que le tableau ne contenait aucun 1. On peut renvoyer 0.

Z