Semestre 2 ST
Algorithmes de recherche et de tri
| Cours | TD - Corrections | TP |
Exercice n°1: Recherche
On considère un tableau de booléens quelconques. On souhaite effectuer diverses recherches au sein de ce tableau.
a) Développer un sous-algorithme permettant de calculer le nombre de "vrai" contenus dans un tableau de boolééns.
b) Développer un sous-algorithme permettant de calculer le nombre de séries de "vrai" et de "faux" consécutifs contenues dans un tableau de booléens.
c) Développer un sous-algorithme permettant de calculer la longueur maximale des suites de "vrai" contenues dans un tableau de booléens.
d) On considère un "motif" de booléens stocké dans un tableau de booléens. Développer un sous-algorithme permettant de calculer l'indice de première apparition de ce motif dans un tableau de booléens. Si le motif n'apparait pas, le sous-algorithme devra retourner -1.
Exercice n°2: Tri à bulle
On souhaite trier par ordre alphabétique des chaînes de caractères composées uniquement de lettres minuscules.
a) Développer un sous-algorithme permettant de comparer deux chaînes de caractères de même longueur. Ce sous-algorithme doit retourner un entier égal à -1, 0 ou 1 suivant que la première chaîne est inférieure, égale ou supérieure à la seconde au sens de l'ordre des codes ASCII des caractères.
b) Implanter un sous-algorithme de tri par ordre de code ASCII d'un tableau de chaînes de caractères. L'algorithme employé sera le tri à bulle.
c) On souhaite maintenant trier des dates (année, mois, jour) par ordre chronologique (de la plus ancienne à la moins ancienne). Comment adapter à cette fin l'algorithme de tri à bulle de la question (b)?
Exercice n°3: Tri par sélection
On souhaite trier par ordre de distance à l'origine (du moins distant au plus distant) des positions dans un espace à 3 dimensions. Pour ce faire,
on définit le type agrégé "position3D" suivant:
structure position3D
reel x <- 0.0
reel y <- 0.0
reel z <- 0.0
fin structure
Implanter un sous-algorithme de tri par sélection d'un tableau de position3D.
Exercice n°4: Recherche dichotomique
On souhaite calculer la racine carrée d'un nombre réel compris dans l'intervalle [0.0,100.0]. On ne dispose que des opérations mathématiques addition, soustraction, multiplication et division ainsi que des tests de comparaison.
Développer un sous-algorithme de calcul de la racine carrée. On utilisera une méthode dichotomique.