Devoir de contrôle n°1 (série B) : procédures, tri par insertion, insertion dans un tableau trié

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

On considère la procédure Python suivante.

def mystere(t, n):
    k = 0
    for i in range(n):
        if t[i] != 0:
            t[k] = t[i]
            k = k + 1
    for i in range(k, n):
        t[i] = 0

• 1) Donner le contenu du tableau t après l'appel mystere(t, 5) avec t = [0, 5, 0, 3, 7]. Détailler les valeurs de k (2 pts).
• 2) Dire en une phrase ce que fait cette procédure (1 pt).
• 3) Pourquoi le tableau t est-il modifié dans le programme appelant, alors que la procédure ne renvoie rien ? (1 pt)
• 4) Écrire l'algorithme de cette procédure (Procédure) et le programme qui lit n puis n entiers, appelle la procédure et affiche le tableau (2 pts).

Exercice 2 : classement d'une course (7 pts)

Lors d'une course, on enregistre le nom de chaque coureur dans un tableau Nom et son temps en secondes (réel) dans un tableau Temps : Nom[i] et Temps[i] concernent le même coureur.

• 1) Écrire la procédure Saisir qui lit n (3 ≤ n ≤ 40, saisie contrôlée) puis le nom et le temps (strictement positif, saisie contrôlée) de chaque coureur (2 pts).
• 2) Écrire la procédure TriInsertion qui trie les coureurs du plus rapide au plus lent, avec la méthode du tri par insertion. Attention : quand on déplace un temps, il faut déplacer le nom avec lui (3 pts).
• 3) Écrire le programme principal qui affiche le podium (les 3 premiers) (2 pts).

Pour n = 4 et les coureurs Ahmed 12.8, Ines 11.9, Karim 13.1, Sarra 12.2, le programme affiche :

1 Ines 11.9
2 Sarra 12.2
3 Ahmed 12.8

Exercice 3 : insérer dans un tableau trié (7 pts)

Un tableau T contient n entiers rangés dans l'ordre croissant (n < 50). On veut y ajouter une valeur x en gardant le tableau trié.

• 1) Écrire la fonction Position qui renvoie, par une recherche dichotomique, l'indice où x doit être inséré : le plus petit indice p tel que T[p] ≥ x, ou n si x est plus grand que tous les éléments (3 pts).
• 2) Écrire la procédure Inserer qui décale vers la droite les éléments à partir de la position trouvée, place x et augmente n de 1 (2 pts).
• 3) Écrire le programme qui lit n, les n éléments (déjà triés), puis x, et affiche le nouveau tableau, éléments séparés par un espace (2 pts).

Pour n = 5, T = 3, 8, 10, 15, 20 et x = 12, le programme affiche :

3 8 10 12 15 20