Devoir de contrôle n°1 (série F) : tri à bulles des mots, fichier des candidats, fusion de deux fichiers triés, matrices

Exercice 1 : ranger des mots par le tri à bulles (5 pts)

On veut ranger n mots écrits en minuscules sans accents dans l'ordre alphabétique. Deux chaînes se comparent avec < et > comme dans un dictionnaire : "ail" < "ble".

• 1) Écrire la procédure TriMots(T, n) qui trie un tableau T de n mots dans l'ordre alphabétique par le tri à bulles, avec une variable booléenne permut (2 pts).
• 2) Écrire le programme qui lit n (2 ≤ n ≤ 20, saisie contrôlée) et les n mots, trie le tableau et affiche les mots triés, un par ligne (1,5 pt).
• 3) Donner le contenu des cases T[0] à T[3] après chaque parcours pour le tableau sel, ail, thym, ble (1,5 pt).

Pour n = 4 et les mots sel, ail, thym, ble, le programme affiche :

ail
ble
sel
thym

Exercice 2 : le fichier des candidats (7 pts)

Pour l'entrée dans un lycée pilote, le fichier texte candidats.txt contient une ligne par candidat sous la forme nom;score, où le score est un entier entre 0 et 200, par exemple « Amine;150 ».

• 1) Déclarer dans un TDNT l'enregistrement Candidat (nom : chaîne ; score : entier) et le type Tab, tableau de 40 candidats (1 pt).
• 2) Écrire la procédure Creer qui lit n (1 ≤ n ≤ 40, saisie contrôlée) puis, pour chaque candidat, son nom et son score (entre 0 et 200, saisie contrôlée), et écrit la ligne nom;score dans candidats.txt (1,5 pt).
• 3) Écrire la procédure Charger qui lit candidats.txt et remplit le tableau T et le nombre n de candidats (1,5 pt).
• 4) Écrire la procédure TriScore(T, n) qui trie T par score décroissant avec le tri par insertion (1,5 pt).
• 5) Écrire la procédure Admis(T, n) qui lit le nombre k de places (1 ≤ k ≤ n, saisie contrôlée), écrit dans admis.txt la ligne nom;score des k premiers candidats du tableau trié, puis affiche le contenu de admis.txt et le score du dernier admis (1,5 pt).

Le programme appelle Creer, Charger, TriScore puis Admis. Pour n = 5, les candidats Amine 150, Salma 182, Yassine 150, Rim 120, Omar 199 et k = 3, il affiche :

Omar;199
Salma;182
Amine;150
Score minimal : 150

Exercice 3 : fusionner deux fichiers triés (4 pts)

Les fichiers texte a.txt et b.txt contiennent chacun au plus 20 entiers, un par ligne, rangés dans l'ordre croissant. On veut obtenir tous ces entiers dans l'ordre croissant sans refaire de tri.

• 1) Écrire la procédure CreerTrie(nom) qui lit n (1 ≤ n ≤ 20, saisie contrôlée) puis n entiers, chacun supérieur ou égal au précédent (saisie contrôlée), et les écrit dans le fichier dont le nom est donné (1 pt).
• 2) Écrire la procédure ChargerFichier(nom, T, n) qui copie les entiers du fichier nom dans le tableau T et donne leur nombre n (0,5 pt).
• 3) Écrire la procédure Fusion(A, na, B, nb, C, nc) qui range dans C les na + nb éléments des tableaux triés A et B dans l'ordre croissant, en avançant dans A et dans B en même temps (2 pts).
• 4) Écrire le programme qui crée a.txt puis b.txt, les charge, les fusionne et affiche le tableau obtenu sur une ligne (0,5 pt).

Pour a.txt contenant 2, 5, 9 et b.txt contenant 1, 5, 6, 10, 12, le programme affiche :

1 2 5 5 6 9 10 12

Exercice 4 : une matrice aux lignes triées (4 pts)

Soit M une matrice de l lignes et c colonnes d'entiers (2 ≤ l ≤ 6, 2 ≤ c ≤ 6). On dit que M est triée quand chaque ligne est croissante de gauche à droite et chaque colonne croissante de haut en bas.

• 1) Déclarer le type Mat dans un TDNT et écrire la procédure TriLigne(M, i, c) qui trie la ligne i de M dans l'ordre croissant par le tri par insertion (1,5 pt).
• 2) Écrire la fonction ColonnesCroissantes(M, l, c) qui renvoie Vrai si chaque colonne de M est croissante de haut en bas, sans sortie forcée de boucle (1,5 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 ligne, affiche la matrice obtenue puis « Matrice triée » ou « Matrice non triée » (1 pt).

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

1 2 3
4 5 6
Matrice triée