Algorithmique & Programmation Orientée Objet 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 consécutives de "vrai" et de "faux" 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. Exemple d'exécution 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. Exemple d'exécution 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)? Exemple d'exécution 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. Exemple d'exécution 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. Exemple d'exécution