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

Correction détaillée

Sujet original écrit pour Mission Carthage, cinquiè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