EXERCICE 1 (10 points)

Programmer la fonction moyenne prenant en paramètre un tableau d’entiers tab (de type list) qui renvoie la moyenne de ses éléments si le tableau est non vide. Proposer une façon de traiter le cas où le tableau passé en paramètre est vide.

Dans cet exercice, on s’interdira d’utiliser la fonction Python sum.

Exemples :

>>> moyenne([5,3,8])
5.333333333333333
>>> moyenne([1,2,3,4,5,6,7,8,9,10])
5.5
>>> moyenne([])
# Comportement différent suivant le traitement proposé.

EXERCICE 2 (10 points)

On considère un tableau d’entiers tab (de type list) dont les éléments sont des 0 ou des 1). On se propose de trier ce tableau selon l’algorithme suivant : à chaque étape du tri, le tableau est constitué de trois zones consécutives, la première ne contenant que des 0, la seconde n’étant pas triée et la dernière ne contenant que des 1. Au départ, les zones ne contenant que des 0 et des 1 sont vides.

[0, ..., 0, <zone non triée>, 1, ..., 1]

Tant que la zone non triée n’est pas réduite à un seul élément, on regarde son premier élément :

• si cet élément vaut 0, on considère qu’il appartient désormais à la zone ne contenant que des 0 ;
• si cet élément vaut 1, il est échangé avec le dernier élément de la zone non triée et on considère alors qu’il appartient à la zone ne contenant que des 1.

Dans tous les cas, la longueur de la zone non triée diminue de 1.

Compléter la fonction tri suivante :

def tri(tab):
    '''tab est un tableau d'entiers contenant des 0 et des 1.
    La fonction trie ce tableau en plaçant tous les 0 à gauche'''
    i = ... # premier indice de la zone non triée
    j = ... # dernier indice de la zone non triée
    while i < j:
        if tab[i] == 0:
            i = ...
        else:
            valeur = ...
            tab[j] = ...
            ...
            j = ...

Exemple :

>>> tab = [0,1,0,1,0,1,0,1,0]
>>> tri(tab)
>>> tab
[0, 0, 0, 0, 0, 1, 1, 1, 1]

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

Exercice 1

Contraintes :

• tab est de type list et ne contient que des entiers
• 1 <= len(tab) <= 10^4 : les tableaux passés à moyenne lors de l’évaluation sont non vides
• -10^4 <= tab[i] <= 10^4
• moyenne(tab) renvoie un nombre flottant (float)
• aucun comportement particulier n’est imposé ni évalué pour le tableau vide

Exercice 2

Contraintes :

• tab est de type list et ne contient que des entiers
• 0 <= len(tab) <= 10^4
• tab[i] vaut 0 ou 1
• tri(tab) modifie tab sur place et ne renvoie rien (None)

Corrigé - Sujet 39

Exercice 1 - la moyenne d’un tableau

L’idée. La moyenne, c’est la somme des éléments divisée par leur nombre. Comme on n’a pas le droit d’utiliser sum, on calcule la somme nous-mêmes : on part d’un total à 0 et on parcourt le tableau en ajoutant chaque valeur au total. À la fin, on divise ce total par len(tab). Le tableau vide est un cas à part : on ne peut pas diviser par 0, il faut donc décider de ce qu’on renvoie.

Un petit exemple. Pour [5, 3, 8], le total vaut 5, puis 8, puis 16 ; il y a 3 éléments, donc la moyenne est 16 / 3, c’est-à-dire 5.333333333333333.

def moyenne(tab):
    if len(tab) == 0:
        return None
    total = 0
    for valeur in tab:
        total = total + valeur
    # La division / renvoie toujours un flottant, même quand le total tombe juste
    return total / len(tab)

total accumule la somme au fur et à mesure du parcours : il doit être créé avant la boucle, sinon on le remettrait à 0 à chaque tour. La boucle for valeur in tab suffit ici, on n’a pas besoin des indices puisqu’on lit toutes les valeurs.

Le choix pour le tableau vide. Ici on renvoie None, qui se lit comme « il n’y a pas de moyenne ». C’était le traitement demandé par le sujet ; d’autres réponses sont acceptables (renvoyer 0, ou déclencher une erreur avec assert len(tab) > 0), du moment que le cas est traité explicitement et que le programme ne plante pas sur une division par zéro.

Exercice 2 - trier un tableau de 0 et de 1

L’idée. Le tableau se lit en trois morceaux : les 0 déjà placés à gauche, une zone encore en désordre au milieu, et les 1 déjà placés à droite. Deux variables retiennent les bords de la zone du milieu : i son premier indice, j son dernier. On regarde tab[i], le premier élément non trié :

• s’il vaut 0, il est déjà du bon côté : on avance simplement i d’un cran, la zone des 0 grandit ;
• s’il vaut 1, sa place est à droite : on l’échange avec tab[j], puis on recule j d’un cran, la zone des 1 grandit.

Dans les deux cas la zone non triée perd un élément, donc la boucle finit toujours.

Un petit exemple. Sur [0, 1, 0] : i = 0, j = 2. tab[0] vaut 0, donc i passe à 1. tab[1] vaut 1, on échange avec tab[2] (le tableau devient [0, 0, 1]) et j passe à 1. Maintenant i et j sont égaux, la boucle s’arrête.

def tri(tab):
    '''tab est un tableau d'entiers contenant des 0 et des 1.
    La fonction trie ce tableau en plaçant tous les 0 à gauche'''
    i = 0 # premier indice de la zone non triée
    j = len(tab) - 1 # dernier indice de la zone non triée
    while i < j:
        if tab[i] == 0:
            i = i + 1
        else:
            valeur = tab[j]
            tab[j] = tab[i]
            tab[i] = valeur
            j = j - 1

Au départ, rien n’est trié : la zone non triée est le tableau entier, d’où i = 0 et j = len(tab) - 1. Les trois lignes valeur = tab[j], tab[j] = tab[i], tab[i] = valeur sont l’échange classique : on met de côté une des deux valeurs dans valeur avant de l’écraser, sinon on la perdrait.

Attention au test while i < j et non while i <= j : quand i et j sont égaux, il ne reste qu’un seul élément non trié, et il est forcément déjà à sa place (tout ce qui est à sa gauche est un 0, tout ce qui est à sa droite est un 1). Continuer serait donc inutile : avec <=, on ferait un tour de boucle de plus qui, si cet élément vaut 1, l’échangerait avec lui-même sans rien changer au tableau. C’est bien i < j que le sujet imprime.

Remarquez enfin que tri ne contient aucun return : elle modifie tab sur place et renvoie None. C’est bien ce que montre l’exemple du sujet, où l’on affiche tab après l’appel.