Devoir de contrôle n°1 (série B) : tri par sélection, recherche séquentielle et dichotomique

Exercice 1 : le tri par sélection (7 pts)

On veut trier un tableau T de n entiers dans l'ordre croissant avec le tri par sélection : à l'étape i, on cherche le plus petit élément parmi T[i], …, T[n - 1] et on l'échange avec T[i].

• 1) Écrire la fonction PosMin(T, d, n) qui renvoie l'indice du plus petit élément parmi T[d], …, T[n - 1] (2 pts).
• 2) Écrire la procédure TriSelection(T, n) qui utilise PosMin et renvoie le nombre d'échanges réellement effectués (on n'échange pas un élément avec lui-même) (3 pts).
• 3) Donner l'état du tableau 8, 3, 6, 1 après chaque étape (1 pt).
• 4) Écrire le programme qui lit n (2 ≤ n ≤ 30) et les n éléments, trie le tableau, l'affiche et affiche le nombre d'échanges (1 pt).

Pour n = 4 et les valeurs 8, 3, 6, 1, le programme affiche :

1 3 6 8
Echanges : 1

Exercice 2 : recherche séquentielle et dichotomique (7 pts)

Un tableau T contient les n codes (entiers) des élèves d'un club, rangés dans l'ordre croissant.

• 1) Écrire la fonction RechSeq(T, n, x) qui renvoie le nombre de comparaisons faites par une recherche séquentielle de x, qui s'arrête dès qu'elle trouve x ou dès qu'elle rencontre un code plus grand que x (2 pts).
• 2) Écrire la fonction RechDicho(T, n, x) qui renvoie le nombre de comparaisons (tours de boucle) faites par une recherche dichotomique de x (3 pts).
• 3) Écrire le programme qui lit n, les n codes (en ordre croissant strict, saisie contrôlée), puis x, et affiche « Trouvé » ou « Absent » et les deux nombres de comparaisons (2 pts).

Pour n = 8, les codes 3, 7, 11, 15, 22, 30, 41, 56 et x = 41, le programme affiche :

Trouvé
Séquentielle : 7 comparaison(s)
Dichotomique : 3 comparaison(s)

Exercice 3 : les nombres parfaits d'un tableau (6 pts)

Un entier n ≥ 2 est parfait s'il est égal à la somme de ses diviseurs autres que lui-même (6 = 1 + 2 + 3).

• 1) Écrire la fonction SommeDiv(n) (2 pts).
• 2) Écrire la procédure Remplir(T, n) qui lit n entiers compris entre 2 et 10000 (saisie contrôlée) (1 pt).
• 3) Écrire la procédure AfficherParfaits(T, n) qui affiche les nombres parfaits du tableau et leur position, ou « Aucun nombre parfait » (2 pts).
• 4) Écrire le programme principal (1 pt).

Pour n = 5 et les valeurs 12, 28, 7, 496, 6, le programme affiche :

28 à la position 1
496 à la position 3
6 à la position 4