Devoir de contrôle n°1 (série E) : tri par sélection, fichier des livres, insertion dans un fichier trié, matrices

Exercice 1 : tri par sélection (5 pts)

Le tri par sélection cherche, à l'étape i, le plus petit élément parmi les cases T[i] à T[n - 1] et l'échange avec T[i]. Après l'étape i, les cases T[0] à T[i] sont à leur place définitive.

• 1) Écrire la procédure TriSelection(T, n) qui trie un tableau T de n entiers dans l'ordre croissant par sélection (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 4, 2, 5, 1, 3 après chaque étape i = 0, 1, 2, 3 (1,5 pt).

Pour n = 5 et les valeurs 4, 2, 5, 1, 3, le programme affiche :

1 2 3 4 5

Exercice 2 : le fichier des livres (7 pts)

La bibliothèque du lycée de Kairouan range ses livres dans le fichier texte livres.txt, une ligne par livre sous la forme titre;annee, par exemple « Le reseau;2009 ».

• 1) Déclarer dans un TDNT l'enregistrement Livre (titre : chaîne ; annee : entier) et le type Tab, tableau de 50 livres (1 pt).
• 2) Écrire la procédure Creer qui lit n (1 ≤ n ≤ 50, saisie contrôlée) puis, pour chaque livre, son titre et son année (entre 1900 et 2026, saisie contrôlée), et écrit la ligne titre;annee dans livres.txt (1,5 pt).
• 3) Écrire la procédure Charger qui lit livres.txt et remplit le tableau T et le nombre n de livres (1,5 pt).
• 4) Écrire la procédure TriAnnee(T, n) qui trie T par année croissante avec le tri à bulles (1,5 pt).
• 5) Écrire la procédure Recents(T, n) qui lit une année a (entre 1900 et 2026, saisie contrôlée), écrit dans recents.txt la ligne annee : titre de chaque livre paru en a ou après (dans l'ordre du tableau trié), puis affiche le contenu de recents.txt et le nombre de ces livres (1,5 pt).

Le programme appelle Creer, Charger, TriAnnee puis Recents. Pour n = 4, les livres Algo facile 2015, Python au lycee 2021, Le reseau 2009, Bases de donnees 2018 et l'année 2015, il affiche :

2015 : Algo facile
2018 : Bases de donnees
2021 : Python au lycee
3 livre(s)

Exercice 3 : insérer dans un fichier trié (4 pts)

Le fichier texte nombres.txt contient au plus 49 entiers, un par ligne, rangés dans l'ordre croissant.

• 1) Écrire la procédure CreerTrie qui lit n (1 ≤ n ≤ 49, saisie contrôlée) puis n entiers, chacun devant être supérieur ou égal au précédent (saisie contrôlée), et les écrit dans nombres.txt (1 pt).
• 2) Écrire la procédure ChargerNombres qui copie les entiers de nombres.txt dans un tableau T et donne leur nombre n (0,5 pt).
• 3) Écrire la procédure Inserer(T, n, x) qui insère l'entier x à sa place dans le tableau trié T, en décalant vers la droite les éléments plus grands ; n augmente de 1 (1,5 pt).
• 4) Écrire la procédure Sauver(T, n) qui réécrit nombres.txt avec les n éléments de T, puis le programme qui appelle CreerTrie et ChargerNombres, lit x, l'insère, sauve le tableau et affiche le contenu de nombres.txt sur une ligne (1 pt).

Pour n = 4, les entiers 3, 8, 8, 15 et x = 10, le programme affiche :

3 8 8 10 15

Exercice 4 : ranger les lignes 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 fonction SommeLigne(M, i, c) qui renvoie la somme des éléments de la ligne i (1 pt).
• 2) Écrire la procédure TrierLignes(M, l, c) qui range les lignes de M par somme croissante avec le tri par sélection ; échanger deux lignes, c'est échanger leurs c cases une par une (2 pts).
• 3) Écrire le programme qui lit l et c (saisies contrôlées) puis les éléments de M ligne par ligne, range les lignes et affiche chaque ligne suivie de « -> » et de sa somme (1 pt).

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

1 0 2 -> 3
4 4 0 -> 8
5 5 5 -> 15