Devoir de contrôle n°1 (série D) : tri par insertion, fichier des coureurs, recherche dans un fichier trié, matrices

Exercice 1 : tri par insertion (5 pts)

Le tri par insertion range les éléments un par un : à l'étape i, les cases T[0] à T[i - 1] sont déjà triées, et on insère T[i] à sa place parmi elles en décalant d'une case vers la droite les éléments plus grands que lui.

• 1) Écrire la procédure TriInsertion(T, n) qui trie un tableau T de n entiers dans l'ordre croissant par insertion (2 pts).
• 2) Écrire le programme qui lit n (2 ≤ n ≤ 30, saisie contrôlée) et les n entiers, trie le tableau et affiche ses éléments triés (1,5 pt).
• 3) Donner l'état du tableau 7, 3, 9, 1, 5 après chaque étape i = 1, 2, 3, 4 (1,5 pt).

Pour n = 5 et les valeurs 7, 3, 9, 1, 5, le programme affiche :

1 3 5 7 9

Exercice 2 : le fichier des coureurs (7 pts)

Pour le cross du lycée de Nabeul, le fichier texte coureurs.txt contient une ligne par coureur sous la forme nom;temps, où le temps est un nombre entier de secondes, par exemple « Amine;754 ».

• 1) Déclarer dans un TDNT l'enregistrement Coureur (nom : chaîne ; temps : entier) et le type Tab, tableau de 40 coureurs (1 pt).
• 2) Écrire la procédure Creer qui lit n (1 ≤ n ≤ 40, saisie contrôlée) puis, pour chaque coureur, son nom et son temps (strictement positif, saisie contrôlée), et écrit la ligne nom;temps dans coureurs.txt (1,5 pt).
• 3) Écrire la procédure Charger qui lit coureurs.txt et remplit le tableau T et le nombre n de coureurs (1,5 pt).
• 4) Écrire la procédure TriTemps(T, n) qui trie T par temps croissant avec le tri par sélection (1,5 pt).
• 5) Écrire la procédure Classement(T, n) qui écrit dans classement.txt, pour chaque coureur du tableau trié, la ligne rang;nom;m min s s (le temps en minutes et secondes), puis affiche le contenu de classement.txt (1,5 pt).

Le programme appelle Creer, Charger, TriTemps puis Classement. Pour n = 4 et les coureurs Amine 754, Salma 698, Yassine 812 et Rim 731, il affiche :

1;Salma;11 min 38 s
2;Rim;12 min 11 s
3;Amine;12 min 34 s
4;Yassine;13 min 32 s

Exercice 3 : chercher un mot dans un fichier trié (4 pts)

Le fichier texte dico.txt contient au plus 100 mots écrits en minuscules sans accents, un par ligne, rangés dans l'ordre alphabétique.

• 1) Écrire la procédure CreerDico qui lit n (1 ≤ n ≤ 100, saisie contrôlée) puis n mots, chaque mot devant être strictement plus grand que le précédent (saisie contrôlée), et les écrit dans dico.txt (1 pt).
• 2) Écrire la procédure ChargerMots qui copie les mots de dico.txt dans un tableau T et donne leur nombre n (1 pt).
• 3) Écrire la fonction Dicho(T, n, mot) qui renvoie l'indice de mot dans T par la recherche dichotomique, ou -1 s'il n'y est pas, sans sortie forcée de boucle (1,5 pt).
• 4) Écrire le programme qui appelle CreerDico et ChargerMots, lit un mot et affiche son numéro de ligne dans le fichier ou qu'il est absent (0,5 pt).

Pour n = 5, les mots ail, ble, figue, menthe, olive et le mot cherché figue, le programme affiche :

figue est à la ligne 3

Exercice 4 : trier les colonnes d'une matrice (4 pts)

Soit M une matrice de l lignes et c colonnes d'entiers (2 ≤ l ≤ 6, 2 ≤ c ≤ 6).

• 1) Déclarer le type Mat dans un TDNT et écrire la procédure TriColonne(M, l, j) qui trie la colonne j de M dans l'ordre décroissant par le tri à bulles (1,5 pt).
• 2) Écrire la fonction SommeLigne(M, i, c) qui renvoie la somme des éléments de la ligne i (1 pt).
• 3) Écrire le programme qui lit l et c (saisies contrôlées) puis les éléments de M ligne par ligne, trie chaque colonne, affiche la matrice obtenue, puis la somme des maximums (première ligne) et la somme des minimums (dernière ligne) des colonnes (1,5 pt).

Pour l = 3, c = 3 et les lignes 4 9 2, 7 1 8 et 5 6 3, le programme affiche :

7 9 8
5 6 3
4 1 2
Somme des maximums : 24
Somme des minimums : 7

Correction détaillée

Sujet original écrit pour Mission Carthage, quatrième série d'entraînement pour le devoir de contrôle du 1er trimestre du bac Sciences de l'informatique, centrée sur les tris et les fichiers texte.

Tout le programme : Bac Sciences de l'informatique · Revoir le cours · Tous les devoirs