Nombre de 1

Nombre de 1

On considère un tableau vide ou 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. Combien 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 avec un 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

Python Console Session

>>> 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

Exercice 1

Compléter le script ci-dessous :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)

Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)

Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Exécuter le code
(Ctrl+S)Valider
(Ctrl+Enter)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

Évaluations restantes : 5/5

ENCRYPTION_TOKEN

Solution & Remarques

def compte_uns(tableau):
    if tableau == []:
        return 0

    if tableau[0] == 1:
        return len(tableau)

    debut = 0
    fin = len(tableau) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        if tableau[milieu] == 0:
            debut = milieu + 1
        elif tableau[milieu - 1] == 1:
            fin = milieu - 1
        else:
            return len(tableau) - milieu

    return 0

Remarques :

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.

ENCRYPTION_TOKEN

Crédits

Un exercice de Nicolas Revéret