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. Un compteur est défini. Un parcours séquentiel complet du tableau est réalisé. Un booleen "enCours" permet de savoir quel type de série (série de "vrai" ou série de "faux") est en cours de parcours dans le tableau. Chaque fois que le booléen enCours est différent du booléen traité dans le tableau, enCours change de valeur et le compteur est incrémenté de 1. c) Développer un sous-algorithme permettant de calculer la longueur maximale des suites de "vrai" contenues dans un tableau de booléens. Une variable entière lMax est définie pour la recherche de maximum. Une variable booléenne enCours est définie pour indiquer que l'on est en train de parcourir une serie de vrai. Une variable entière cpt est définie pour compter la longueur de la série de vrai en cours de parcours. Un parcours séquentiel complet du tableau est réalisé booléen après booléen. - Si le booléen parcouru est vrai. (1) Si on n'était pas en train de parcourir une série de vrai alors on commence le parcours d'une série de vrai et donc cpt est affecté à 0 et enCours à vrai. (2) cpt est incrémenté de 1 car on est en train de parcourir une série de vrai. - Si le booléen parcouru est faux. Si on vient de finir de parcourir une série de vrai. (1) Il faut ajuster cpt (si cpt est plus grand que lMax alors lMax est affecté avec cpt). (2) encours est affecté à faux. 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. On développe une fonction permettant de tester si les booléens contenus dans un tableau à partir de l'indice p correspondent aux booléens contenus dans un tableau à partir de l'indice 0. On utilise cette fonction pour tester l'existence d'une concordance du motif recherché dans le tableau de recherche. Un parcours séquentiel est réalisé depuis l'indice 0 jusqu'au (éventuellement) dernier indice compatible avec les tailles du tableau de recherche et du motif.
RecherchesDansTableauBooleen.lda { Calcul et retour du nombre de booleens vrai } { presents dans un tableau de booleens } { t : Le tableau de booleens } entier fonction nombreDeVrais(-> booleen [] t) entier i entier nb <- 0 pour i de 0 à longueur(t)-1 faire si t[i] alors nb <- nb+1 fsi fait retourner nb fin fonction { Calcul et retour du nombre de series } { de booleens identiques consecutifs } { presentes dans un tableau de booleens } { t : Le tableau de booleens } entier fonction nombreSeries(-> booleen [] t) entier i entier nb <- 1 booleen enCours <- t[0] si longueur(t) > 1 alors pour i de 1 à longueur(t)-1 faire si t[i] <> enCours alors nb <- nb+1 enCours <- t[i] fsi fait fsi retourner nb fin fonction { Calcul et retour de la longueur maximale } { de toutes les series de vrais consecutifs } { presentes dans un tableau de booleens } { t : Le tableau de booleens } entier fonction longueurMaxSeriesVrais(-> booleen [] t) entier i entier lMax <- 0 entier cpt <- 0 booleen enCours <- faux pour i de 0 à longueur(N)-1 faire si t[i] alors si non(enCours) alors cpt <- 0 enCours <- vrai fsi cpt <- cpt+1 sinon si enCours alors si cpt > lMax alors lMax <- cpt fsi enCours <- faux fsi fsi fait si enCours alors si cpt > lMax alors lMax <- cpt fsi fsi retourner lMax fin fonction { Test si un motif de booleens coincide } { avec les booleens presents dans un tableau } { de booleens a partir d'un indice (position) } { motif : Le tableau de booleens motif } { t : Le tableau de booleens où est effectué } { le test } { p : L'indice de recherche } booleen fonction concordance(-> booleen [] motif, -> booleen [] t, -> entier p) entier i <- 0 booleen res <- vrai entier pos <- p tantque res et ( i < longueur(motif) ) faire si motif[i] <> t[pos] alors res <- faux sinon i <- i+1 pos <- pos+1 fsi fait retourner res fin fonction { Determination et retour de l'indice } { de la 1ère occurrence d'un motif de booleens } { recherché dans un tableau de booleens } { Retourne -1 si motif non present } { motif : Le tableau de booleens motif } { t : Le tableau de booleens où est effectuée } { la recherche } entier fonction premiereOccurrence(-> booleen [] motif, -> booleen [] t) entier pos <- -1 entier i <- 0 entier nt <- longueur(t)-longueur(motif)+1 tantque ( pos == -1 ) et ( i < nt ) faire si concordance(motif,t,i) alors pos <- i sinon i <- i+1 fsi fait retourner pos fin fonction Clavier.class - Ecran.class - 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.
TriBulleTableauDeChaines.lda { Fonction de comparaison de deux chaines } { de caracteres de longueurs identiques } { vis a vis de l'ordre au sens du code ASCII } { Valeur entiere retournee: } { 0 si chaines egales } { -1 si la premiere chaine est inferieure } { a la seconde } { 1 si la premiere chaine est superieure } { a la seconde } entier fonction ordre(-> chaine s1,-> chaine s2) entier lc <- longueur(s1) caracteres [] t1 <- tableauCaracteres(s1) caracteres [] t2 <- tableauCaracteres(s2) entier res <- 0 booleen go <- vrai entier i <- 0 tantque go faire si ( i == lc ) alors go <- faux sinon si t1[i] < t2[i] alors go <- faux res <- -1 sinon si t1[i] > t2[i] alors go <- faux res <- 1 fsi fsi fsi i <- i+1 fait retourner res fin fonction { Action de tri a bulle d'un tableau } { de chaines de caracteres } { de longueurs identiques } { par ordre de code ASCII } action triBulleTableauDeChaines(-> chaine [] t ->) entier j chaine aux booleen permutation entier np np <- longueur(t)-1 faire permutation <- faux pour j de 0 à np-1 faire si ordre(t[j],t[j+1]) == 1 alors aux <- t[j] t[j] <- t[j+1] t[j+1] <- aux permutation <- vrai fsi fait np <- np-1 tantque permutation fin action Clavier.class - Ecran.class - 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)? Pour trier des dates au moyen de la méthode de tri à bulle, l'algorithme reste identique aux modifications suivantes près: - Il s'applique à un tableau de "date" et non à un tableau de "chaine". - La permutation entre variables s'applique à des "date" et non à des "chaine". - La fonction de comparaison est à réécrire et doit comparer des "date".
TriBulleTableauDeDates.lda { Type agrege de stockage des informations } { relatives a une date codee sous la forme } { jour, mois, annee } structure date entier j <- 1 entier m <- 1 entier a <- 1901 fin structure { Fonction de comparaison de deux date } { vis a vis de l'ordre chronologique } { Valeur entiere retournee: } { 0 si date egales } { -1 si la premiere date est anterieure } { a la seconde } { 1 si la premiere date est posterieure } { a la seconde } entier fonction ordre(-> date d1,-> date d2) entier res si d1.annee < d2.annee alors res <- -1 sinon si d1.annee > d2.annee alors res <- 1 sinon si d1.mois < d2.mois alors res <- -1 sinon si d1.mois > d2.mois alors res <- 1 sinon si d1.jour < d2.jour alors res <- -1 sinon si d1.jour > d2.jour alors res <- 1 sinon res <- 0 fsi fsi fsi fsi fsi fsi retourner res fin fonction { Action de tri a bulle d'un tableau } { de date par ordre chronologique } action triBulleTableauDeDates(-> date [] t ->) entier j date aux booleen permutation entier np np <- longueur(t)-1 faire permutation <- faux pour j de 0 à np-1 faire si ordre(t[j],t[j+1]) == 1 alors aux <- t[j] t[j] <- t[j+1] t[j+1] <- aux permutation <- vrai fsi fait np <- np-1 tantque permutation == vrai fin action Clavier.class - Ecran.class - 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.
TriSelectionTableauDePosition3D.lda { Type agrege de stockage des informations } { relatives a une position en trois dimensions } structure position3D reel x <- 0.0 reel y <- 0.0 reel z <- 0.0 fin structure { Fonction de calcul de la distance } { entre une positon3D et l'origine } reel fonction distanceOrigine(-> position3D p) reel d <- sqrt(p.x*p.x+p.y*p.y+p.z*p.z) retourner d fin fonction { Fonction de recherche de l'indice } { de la valeur maximale d'un tableau } { de position3D restreint } { a ses n+1 premieres valeurs } entier fonction indiceMaximum(-> entier n, -> position3D [] t) entier i reel d reel max <- distanceOrigine(t[n]) entier iMax <- n pour i de n-1 à 0 pas -1 faire d <- distanceOrigine(t[i]) si d > max alors max <- d iMax <- i fsi fait retourner iMax fin fonction { Action de tri par selection d'un tableau } { de position3D en fonction de la distance } { a l'origine } action triSelectionTableauPosition3D(-> position3D [] t ->) entier i position3D aux entier iMax pour i de longueur(t)-1 à 1 pas -1 faire iMax <- indiceMaximum(i,t) si iMax <> i alors aux <- t[iMax] t[iMax] <- t[i] t[i] <- aux fsi fait fin action Clavier.class - Ecran.class - 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.
RechercheRacineCarree.lda constante reel EPSILON <- 0.0000001 { Recherche de la racine carree d'un reel } { compris entre 0.0 et 100.0 } { Utilisation d'une methode dichotomique } { v : Valeur dont on recherche la racine carree } { (comprise entre 0.0 et 100.0) } reel fonction racine(-> reel v) reel ai <- 0.0 reel af <- 10.0 reel mid faire mid <- (af+ai)/2.0 si mid*mid > v alors af <- mid sinon ai <- mid fsi tant que ( af-ai > EPSILON ) retourner mid fin fonction Clavier.class - Ecran.class - Exemple d'exécution