|
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 quelle 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
constante entier N <- ...
constante entier M <- ...
{ Calcul du nombre de booleens vrai }
{ presents dans un tableau de booleens }
entier fonction nombreDeVrais(t)
Donnees
t : Tableau [N] de booleen
Locales
i : entier
nb : entier
nb <- 0
pour i de 0 à N-1 faire
si t[i] alors
nb <- nb+1
fsi
fait
retourner nb
fin fonction
{ Calcul du nombre de series de booleens }
{ identiques consecutifs presentes }
{ dans un tableau de booleens }
entier fonction nombreSeries(t)
Donnees
t : Tableau [N] de booleen
Locales
i : entier
nb : entier
enCours : booleen
nb <- 1
enCours <- t[0]
pour i de 1 à N-1 faire
si t[i] <> enCours alors
nb <- nb+1
enCours <- t[i]
fsi
fait
retourner nb
fin fonction
{ Calcul de la longueur maximale de toutes }
{ les series de vrais consecutifs presentes }
{ dans un tableau de booleens }
entier fonction longueurMaxSeriesVrais(t)
Donnees
t : Tableau [N] de booleen
Locales
i : entier
lMax : entier
cpt : entier
enCours : booleen
lMax <- 0
cpt <- 0
enCours <- false
pour i de 0 à 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 }
booleen fonction concordance(motif,t,p)
Donnees
t : Tableau [N] de booleen
motif : Tableau [M] de booleen
p : entier
Locales
i : entier
res : booleen
i <- 0
res <- vrai
tantque res et ( i < M ) faire
res <- ( motif[i] = t[p] )
i <- i+1
p <- p+1
fait
retourner res
fin fonction
{ Determination de l'indice de la premiere }
{ occurrence d'un motif de booleens }
{ recherche dans un tableau de booleens }
{ Retourne -1 si motif non present }
entier fonction premiereOccurrence(motif,t)
Donnees
t : Tableau [N] de booleen
motif : Tableau [M] de booleen
Locales
pos : entier
i : entier
nt : entier
pos <- -1
i <- 0
nt <- N-M+1
tantque ( pos = -1 ) et ( i < nt ) faire
si concordance(motif,t,i) alors
pos <- i
fsi
i <- i+1
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 alphabétique croissant.
b) Implanter un sous-algorithme de tri par ordre alphabétique d'un tableau de chaînes de caractères. L'algorithme
employé sera le tri à bulle.
|
TriBulleTableauDeChaines.lda
constante N : entier <- ... { nombre de chaines }
constante M : entier <- ... { longueur des chaines }
{ Methode de comparaison de deux chaines }
{ de caracteres vis a vis }
{ de l'ordre alphabetique }
{ 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(s1,s2)
Donnees
s1 : chaine
s2 : chaine
Locales
res : entier
t1 : Tableau [M] de caracteres
t2 : Tableau [M] de caracteres
i : entier
go : booleen
t1 <- s1.toCharArray()
t2 <- s2.toCharArray()
go <- vrai
res <- 0
i <- 0
tantque go et ( i < M ) faire
si t1[i] < t2[i] alors
go <- faux
res <- -1
sinon
si t1[i] > t2[i] alors
go <- false
res <- 1
fsi
fsi
i <- i+1
fait
retourner res
fin fonction
{ Methode de tri a bulle d'un tableau }
{ de N chaines de M caracteres }
{ par ordre alphabetique }
action triBulleTableauDeChaines(t)
Donnees / Resultat
t : Tableau [N] de chaine
Locales
i : entier
j : entier
aux : chaine
permutation : booleen
ne : entier
np : entier
cpt : entier
ne <- N-1
np <- N-1
cpt <- 0
faire
cpt <- cpt+1
permutation <- faux
pour j de 0 à np-1 faire
si ordre(t[j],t[j+1]) > 0 alors
aux <- t[j]
t[j] <- t[j+1]
t[j+1] <- aux
permutation <- vrai
fsi
np <- np-1
fait
tantque permutation et ( cpt < ne )
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
constante N : entier <- ... { nombre de dates }
{ Type agrege de stockage des informations }
{ relatives a une date codee sous la forme }
{ jour, mois, annee }
structure date
j : entier <- 1
m : entier <- 1
a : entier <- 1901
fin structure
{ Methode 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(d1,d2)
Donnees
d1 : date
d2 : date
Locales
res : entier
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
{ Methode de tri a bulle d'un tableau }
{ de date par ordre chronologique }
action triBulleTableauDeDates(t)
Donnees / Resultat
t : Tableau [N] de date
Locales
i : entier
j : entier
aux : date
permutation : booleen
ne : entier
np : entier
cpt : entier
ne <- N-1
np <- N-1
cpt <- 0
faire
cpt <- cpt+1
permutation <- faux
pour j de 0 à np-1 faire
si ordre(t[j],t[j+1]) > 0 alors
aux <- t[j]
t[j] <- t[j+1]
t[j+1] <- aux
permutation <- vrai
fsi
np <- np-1
fait
tantque permutation et ( cpt < ne )
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
x : reel <- 0.0
y : reel <- 0.0
z : reel <- 0.0
fin structure
Implanter un sous-algorithme de tri par sélection d'un tableau de position3D.
|
TriSelectionTableauDePosition3D.lda
constante N : entier <- ...
{ Type agrege de stockage des informations }
{ relatives a une position en trois dimensions }
structure position3D
x : reel <- 0.0
y : reel <- 0.0
z : reel <- 0.0
fin structure
{ Methode de calcul de la distance }
{ entre une positon3D et l'origine }
reel fonction distanceOrigine(p)
Données
p : position3D
Locales
d : reel
d = sqrt(p.x*p.x+p.y*p.y+p.z*p.z)
retourner d
fin fonction
{ Methode de recherche de l'indice de la valeur }
{ maximale d'un tableau de position3D restreint }
{ a ses n premieres valeurs }
entier fonction indiceMaximum(n,t)
Données
n : entier
t : Tableau [N] de position3D
Locales
max : reel
iMax : entier
i : entier
d : reel
max <- distanceOrigine(t[n])
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
{ Methode de tri par selection d'un tableau }
{ de position3D en fonction de la distance }
{ a l'origine }
action triSelectionTableauPosition3D(t)
Donnees / Resultat
t : Tableau [N] de position3D
Locales
i : entier
aux : position3D
iMax : entier
pour i de N-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 }
reel fonction racine(v)
Données
v : réel
Locales
ai : réel
af : réel
mid : réel
ai <- 0.0
af <- 10.0
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
|
|
