EXERCICE 1 (10 points)

Écrire une fonction verifie qui prend en paramètre un tableau de valeurs numériques et qui renvoie True si ce tableau est trié dans l’ordre croissant, False sinon.

Un tableau vide est considéré comme trié.

Exemples :

>>> verifie([0, 5, 8, 8, 9])
True
>>> verifie([8, 12, 4])
False
>>> verifie([-1, 4])
True
>>> verifie([])
True
>>> verifie([5])
True

EXERCICE 2 (10 points)

On considère dans cet exercice l’élection d’un vainqueur à l’issue d’un vote. Les résultats du vote sont stockés dans un tableau : chaque vote exprimé est le nom d’un ou d’une candidate.

Par exemple, les résultats pourraient correspondre au tableau :

urne = ['A', 'A', 'A', 'B', 'C', 'B', 'C', 'B', 'C', 'B']

indiquant que 3 candidats ont obtenu au moins un vote chacun : A, B et C.

On cherche à déterminer le ou les candidats ayant obtenu le plus de suffrages. Pour cela, on propose d’écrire deux fonctions :

• la fonction depouille doit permettre de compter le nombre de votes exprimés pour chacune des issues. Elle prend en paramètre un tableau et renvoie le résultat dans un dictionnaire dont les clés sont les noms des issues et les valeurs le nombre de votes en leur faveur ;
• la fonction vainqueurs doit désigner le nom du ou des gagnants. Elle prend en paramètre un dictionnaire non vide dont la structure est celle du dictionnaire renvoyé par la fonction depouille et renvoie un tableau. Ce tableau peut donc contenir plusieurs éléments s’il y a des artistes ex-aequo.

Compléter les fonctions depouille et vainqueurs ci-après pour qu’elles renvoient les résultats attendus.

def depouille(urne):
    '''prend en paramètre une liste de suffrages et renvoie un 
    dictionnaire avec le nombre de voix pour chaque candidat'''
    resultat = ... 
    for bulletin in urne:
        if ...: 
            resultat[bulletin] = resultat[bulletin] + 1
        else:
            ...
    return resultat

def vainqueurs(election):
    '''prend en paramètre un dictionnaire non vide avec le nombre de voix
    pour chaque candidat et renvoie la liste des vainqueurs'''
    nmax = 0
    for candidat in election:
        if ... > ... : 
            nmax = ... 
    liste_finale = [ nom for nom in election if ... ] 
    return ... 

Exemples d’utilisation :

>>> depouille([ 'A', 'B', 'A' ])
{'A': 2, 'B': 1}
>>> depouille([])
{}
>>> election = depouille(['A', 'A', 'A', 'B', 'C',
    'B', 'C', 'B', 'C', 'B'])
>>> election
{'A': 3, 'B': 4, 'C': 3}
>>> vainqueurs(election)
['B']
>>> vainqueurs({ 'A' : 2, 'B' : 2, 'C' : 1})
['A', 'B']

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• verifie prend en paramètre un tableau (list) de valeurs numériques (int ou float)
• 0 <= len(tab) <= 10^4
• -10^9 <= tab[i] <= 10^9
• le tableau peut être vide ou ne contenir qu’un seul élément
• verifie renvoie un booléen (True ou False)

Exercice 2

Contraintes :

• depouille prend en paramètre un tableau (list) dont chaque élément est une chaîne de caractères (str) désignant un nom de candidat
• 0 <= len(urne) <= 10^4
• 1 <= len(urne[i]) <= 20 ; les noms sont formés de caractères alphanumériques
• l’urne peut être vide : depouille([]) renvoie {}
• depouille renvoie un dictionnaire (dict) dont les clés sont des chaînes de caractères et les valeurs des entiers strictement positifs
• vainqueurs prend en paramètre un dictionnaire non vide de la forme renvoyée par depouille pour une urne non vide : 1 <= len(election) <= 10^4, et 1 <= election[nom] <= 10^4 pour chaque clé nom
• le dictionnaire vide et les dictionnaires contenant des valeurs nulles ou négatives sont hors du champ de vainqueurs et ne sont jamais soumis à la fonction
• vainqueurs renvoie un tableau (list) de chaînes de caractères, les noms y apparaissant dans l’ordre des clés du dictionnaire reçu

Corrigé - Sujet 27

Exercice 1 - vérifier qu’un tableau est trié

L’idée. Un tableau est trié dans l’ordre croissant si chaque valeur est inférieure ou égale à celle qui la suit. Il suffit donc de comparer les éléments deux par deux, en partant du début. Dès qu’on tombe sur un couple dans le mauvais ordre, la réponse est False et on peut s’arrêter. Si on arrive au bout sans rien trouver, c’est que le tableau est trié.

Un petit exemple. Pour [8, 12, 4] : on compare 8 et 12, c’est dans le bon ordre ; puis 12 et 4, et là 12 est plus grand que 4, donc on renvoie False.

def verifie(tab):
    # Le tableau est trié tant que chaque valeur est <= à la suivante
    for i in range(len(tab) - 1):
        if tab[i] > tab[i + 1]:
            return False
    return True

Explications. i est l’indice de la valeur qu’on compare à sa voisine de droite. La boucle s’arrête à len(tab) - 1 parce qu’on regarde à la fois tab[i] et tab[i + 1] : si i allait jusqu’au dernier indice, tab[i + 1] n’existerait pas. Le test est > et non >=, car deux valeurs égales ne cassent pas l’ordre croissant : c’est pour cela que [0, 5, 8, 8, 9] renvoie bien True. Enfin, si le tableau est vide ou n’a qu’un seul élément, range est vide, la boucle ne tourne pas du tout et la fonction renvoie True, comme demandé.

Exercice 2 - dépouiller une élection

La fonction depouille

L’idée. On lit les bulletins un par un en tenant à jour un dictionnaire de comptage. Pour chaque nom rencontré, deux cas seulement : soit ce nom est déjà une clé du dictionnaire et on ajoute 1 à son compteur, soit c’est la première fois qu’on le voit et on crée la clé avec la valeur 1.

Un petit exemple. Pour ['A', 'B', 'A'] : A est nouveau, on obtient {'A': 1} ; B est nouveau, on obtient {'A': 1, 'B': 1} ; A est déjà là, son compteur passe à 2, d’où le résultat {'A': 2, 'B': 1}.

def depouille(urne):
    '''prend en paramètre une liste de suffrages et renvoie un 
    dictionnaire avec le nombre de voix pour chaque candidat'''
    resultat = {}
    for bulletin in urne:
        if bulletin in resultat:
            resultat[bulletin] = resultat[bulletin] + 1
        else:
            # Premier vote pour ce nom : on crée son compteur
            resultat[bulletin] = 1
    return resultat

Explications. resultat part du dictionnaire vide {} : il se remplit au fur et à mesure de la lecture de l’urne. Le test bulletin in resultat demande si le nom est déjà une clé du dictionnaire, c’est lui qui sépare les deux cas. Si l’urne est vide, la boucle ne tourne pas et on renvoie {}, ce qui est bien le résultat attendu.

La fonction vainqueurs

L’idée. On procède en deux temps. On cherche d’abord le plus grand nombre de voix obtenu, qu’on appelle nmax, en parcourant tous les candidats. On repasse ensuite sur les noms et on garde tous ceux dont le nombre de voix vaut exactement nmax : c’est ce deuxième passage qui permet de renvoyer plusieurs noms en cas d’ex-aequo.

Un petit exemple. Pour {'A': 2, 'B': 2, 'C': 1}, le premier passage trouve nmax = 2 ; le second garde A et B, qui ont tous les deux 2 voix, et renvoie ['A', 'B'].

def vainqueurs(election):
    '''prend en paramètre un dictionnaire non vide avec le nombre de voix
    pour chaque candidat et renvoie la liste des vainqueurs'''
    nmax = 0
    for candidat in election:
        if election[candidat] > nmax :
            nmax = election[candidat]
    # On ne peut garder les ex-aequo qu'une fois nmax connu, d'où le second passage
    liste_finale = [ nom for nom in election if election[nom] == nmax ]
    return liste_finale

Explications. Attention, quand on écrit for candidat in election, la variable candidat prend les clés du dictionnaire, c’est-à-dire les noms ; pour obtenir le nombre de voix il faut écrire election[candidat]. On peut partir de nmax = 0 sans risque, parce que l’énoncé garantit un dictionnaire non vide dont tous les comptages valent au moins 1 : nmax finit donc toujours par valoir un vrai score. La liste en compréhension parcourt les noms dans l’ordre des clés du dictionnaire et garde ceux dont le score est égal à nmax ; c’est pour cela que les vainqueurs sortent dans l’ordre où ils apparaissent dans election.