Sujet type bac pratique n°5 : tri par sélection et recherche dichotomique récursifs dans une matrice

Sujet : tri et recherche récursifs (20 pts)

On veut lire une matrice M de l lignes et c colonnes d'entiers (2 ≤ l ≤ 10, 2 ≤ c ≤ 10), trier chacune de ses lignes dans l'ordre croissant avec une version récursive du tri par sélection, l'afficher, puis chercher un entier x dans chaque ligne triée avec une version récursive de la recherche dichotomique.

• 1) Créer un programme Python et l'enregistrer sous le nom Recursif.py (1 pt).
• 2) Écrire la procédure Remplir(M, l, c) qui lit les éléments de M ligne par ligne (2 pts).
• 3) Écrire la procédure récursive TriSelection(M, i, d, c) qui trie la ligne i entre les colonnes d et c - 1 : elle place le plus petit élément de cette partie dans la colonne d, puis trie la partie qui commence à la colonne d + 1 par un appel récursif (5 pts).
• 4) Écrire la procédure Afficher(M, l, c) qui affiche M ligne par ligne, les éléments d'une ligne séparés par un espace (2 pts).
• 5) Écrire la fonction récursive Dicho(M, i, g, d, x) qui renvoie Vrai si x se trouve dans la ligne triée i entre les colonnes g et d, Faux sinon (5 pts).
• 6) Écrire le programme principal en Python qui lit l et c (saisies contrôlées), M et x, trie chaque ligne et affiche M, puis affiche « x est dans la ligne k » pour chaque ligne k (à partir de 1) qui contient x, ou « x n'est dans aucune ligne », où x et k sont remplacés par leurs valeurs (5 pts).

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

2 4 7 9
1 3 5 8
0 4 4 6
4 est dans la ligne 1
4 est dans la ligne 3

Correction détaillée

Sujet original écrit pour Mission Carthage, dans le format de l'épreuve pratique d'informatique du bac Sciences de l'informatique. Ce n'est pas un sujet officiel.

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