|
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.
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(t)-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
|
|
