Devoir de contrôle n°1 : procédures, tri par sélection, recherche dichotomique

Exercice 1 : que fait cette procédure ? (6 pts)

On considère la procédure Python suivante, puis son appel.

def mystere(T, n):
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if T[j] < T[m]:
                m = j
        aux = T[i]
        T[i] = T[m]
        T[m] = aux
        print(T[:n])

T = [5, 2, 9, 1, 7]
mystere(T, 5)

• 1) Donner l'affichage obtenu, en indiquant pour chaque valeur de i la valeur de m (3 pts).
• 2) Quel est le rôle de la procédure mystere ? (1 pt)
• 3) Combien de comparaisons T[j] < T[m] sont faites pour n = 5 ? Et pour un n quelconque ? (1 pt)
• 4) Que faut-il modifier pour obtenir l'ordre décroissant ? (1 pt)

Exercice 2 : les notes d'une classe (8 pts)

Une classe compte n élèves (5 ≤ n ≤ 30). On veut un programme qui :

• saisit n (saisie répétée tant que n n'est pas dans [5, 30]) ;
• remplit un tableau T avec les n notes des élèves, chaque note étant un réel de [0, 20] (saisie contrôlée) ;
• trie T dans l'ordre décroissant par la méthode de sélection ;
• affiche les notes triées, la moyenne arrondie à deux décimales et le nombre d'élèves admis (note ≥ 10).

Pour réaliser ce programme, on utilise les modules suivants : la procédure Remplir(T, n), la procédure Trier(T, n), la fonction Moyenne(T, n) et la fonction NbAdmis(T, n).

Exemple : pour n = 5 et les notes 12, 15.5, 7.5, 18, 9, le programme affiche :

Notes triées : 18.0 15.5 12.0 9.0 7.5
Moyenne : 12.4
Admis : 3

• 1) Décomposer le problème en modules, avec leur rôle (2 pts).
• 2) Écrire l'algorithme du programme principal et celui de chaque module (3 pts).
• 3) Traduire le tout en Python (3 pts).

Exercice 3 : recherche dichotomique (6 pts)

Un tableau T de n entiers (n ≥ 1) est trié dans l'ordre strictement croissant. On veut savoir si un entier x appartient à T.

• 1) Écrire la fonction Chercher(T, n, x) qui renvoie l'indice de x dans T s'il y est, et -1 sinon, en utilisant la recherche dichotomique (3 pts).
• 2) Pour T = [1, 3, 5, 8, 10, 12, 15] (n = 7) et x = 10, dresser le tableau des valeurs successives de d, f et m (1,5 pt).
• 3) Combien de comparaisons au maximum faut-il pour un tableau de 1000 éléments ? Comparer avec la recherche séquentielle (1,5 pt).

Le programme principal lit n, les n éléments de T, puis x. Il affiche « x trouvé à l'indice p » ou « x est absent ».