Accueil › Devoirs › Bac SI

Exercice 1 : tri à bulles avec drapeau (7 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,5 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 (2 pts).
• 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 (6 pts)

• 1) Écrire une fonction récursive Inverse(ch) qui renvoie la chaîne ch écrite à l'envers, sans boucle (2 pts).
• 2) Écrire une fonction récursive NbOcc(c, ch) qui renvoie le nombre d'apparitions du caractère c dans ch, sans boucle (2 pts).
• 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 (7 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 (2 pts).
• 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 (3 pts).
• 3) Combien d'appels au plus pour un tableau de 100 éléments ? Comparer avec la recherche séquentielle (1 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 ».

Correction détaillée

Sujet original écrit pour Mission Carthage, deuxième série d'entraînement pour le devoir de contrôle du 1er trimestre du bac Sciences de l'informatique.

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