Devoir de contrôle n°1 (série B) : tri à bulles, récursivité, recherche dichotomique, matrices

Exercice 1 : tri à bulles avec drapeau (6 pts)

Le tri à bulles parcourt le tableau et échange deux voisins T[i] et T[i + 1] quand ils sont dans le mauvais ordre. On recommence les parcours tant qu'au moins un échange a eu lieu.

• 1) Écrire la procédure TriBulles qui trie un tableau T de n entiers dans l'ordre croissant et renvoie le nombre de parcours effectués. Utiliser une variable booléenne permut (2 pts).
• 2) Améliorer la procédure : après chaque parcours, le plus grand élément restant est à sa place définitive, donc le parcours suivant peut s'arrêter une case plus tôt (1,5 pt).
• 3) Écrire le programme qui lit n (2 ≤ n ≤ 50, saisie contrôlée) et les n entiers, trie le tableau et affiche les éléments triés puis le nombre de parcours (1,5 pt).
• 4) Donner l'état du tableau 5, 1, 4, 2, 8 après chaque parcours (1 pt).

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

1 2 4 5 8
Parcours : 3

Exercice 2 : fonctions récursives sur les chaînes (5 pts)

• 1) Écrire une fonction récursive Inverse(ch) qui renvoie la chaîne ch écrite à l'envers, sans boucle (1,5 pt).
• 2) Écrire une fonction récursive NbOcc(c, ch) qui renvoie le nombre d'apparitions du caractère c dans ch, sans boucle (1,5 pt).
• 3) Dérouler les appels de NbOcc("a", "bac") (1 pt).
• 4) Écrire le programme qui lit un mot puis un caractère, et affiche le mot à l'envers et le nombre d'apparitions du caractère (1 pt).

Pour le mot informatique et le caractère i, le programme affiche :

euqitamrofni
2

Exercice 3 : recherche dichotomique récursive (5 pts)

Un tableau T contient n entiers rangés dans l'ordre croissant. La recherche dichotomique compare la valeur cherchée x avec l'élément du milieu, puis continue dans la moitié gauche ou dans la moitié droite.

• 1) Écrire la procédure Remplir qui lit n (1 ≤ n ≤ 100) puis n entiers rangés dans l'ordre croissant : chaque valeur lue doit être supérieure ou égale à la précédente, sinon on la redemande (1,5 pt).
• 2) Écrire la fonction récursive Dicho(T, x, g, d) qui renvoie l'indice de x entre les indices g et d, ou -1 si x n'y est pas (2 pts).
• 3) Combien d'appels au plus pour un tableau de 100 éléments ? Comparer avec la recherche séquentielle (0,5 pt).
• 4) Écrire le programme principal qui lit x et affiche le résultat (1 pt).

Pour n = 6, les valeurs 2, 5, 8, 12, 16, 23, puis x = 16, le programme affiche :

16 se trouve à l'indice 4

Si x n'est pas dans le tableau, il affiche par exemple « 7 n'existe pas ».

Exercice 4 : trier 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) Écrire la procédure TriLigne(M, i, c) qui trie la ligne i de M dans l'ordre croissant par le tri à bulles (1,5 pt).
• 2) Écrire la fonction récursive SommeRec(M, i, j) qui renvoie la somme des éléments de la ligne i entre les colonnes 0 et j, sans 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 triée puis la somme de chaque ligne calculée par SommeRec (1 pt).

Pour l = 2, c = 3 et les éléments 5 1 4, 9 9 2, le programme affiche :

1 4 5
2 9 9
Somme ligne 1 : 10
Somme ligne 2 : 20