|
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.
e) Développer un sous-algorithme permettant de générer un tableau de n booléens tirés au hasard.
f) Développer un sous-algorithme permettant d'afficher un tableau de booléens de manière que les "vrais" soient affichés au moyen de
caractères '1' et les "faux" au moyen de caractères '0'.
g) Développer un sous-algorithme permettant de créer un tableau de booléens à partir d'une chaîne de caractères considérée comme ne contenant
que des '0' et des '1' codant respectivement des faux et des vrais.
|
RecherchesDansTableauBooleen.java
/* Generation et retour d'un tableau de booleens */
/* tires au sort avec equiprobabilite */
/* n : La taille du tableau à générer */
static boolean [] generationAleatoire(int n) {
boolean [] t = new boolean[n];
for ( int i = 0 ; i < n ; i++ ) {
t[i] = ( Math.random() < 0.5); }
return t;
}
/* Affichage complet d'un tableau de booleens */
/* - '0' pour false */
/* - '1' pour true */
/* t : Le tableau de booleens à afficher */
static void afficher(boolean [] t) {
for ( int i = 0 ; i < t.length ; i++ ) {
if ( t[i] ) {
Ecran.afficher('1'); }
else {
Ecran.afficher('0'); } }
}
/* Calcul et retour du nombre de booleens true */
/* presents dans un tableau de booleens */
/* t : Le tableau de booleens */
static int nombreDeVrais(boolean [] t) {
int nb = 0;
for ( int i = 0 ; i < t.length ; i++ ) {
if ( t[i] ) {
nb++; } }
return nb;
}
/* Calcul et retour du nombre de series */
/* de booleens identiques consecutifs presentes */
/* dans un tableau de booleens */
/* t : Le tableau de booleens */
static int nombreSeries(boolean [] t) {
int nb = 1;
boolean enCours = t[0];
for ( int i = 1 ; i < t.length ; i++ ) {
if ( t[i] != enCours ) {
nb++;
enCours = t[i]; } }
return nb;
}
/* Calcul et retour de la longueur maximale */
/* de toutes les series de true consecutifs */
/* presents dans un tableau de booleens */
/* t : Le tableau de booleens */
static int longueurMaxSeriesVrais(boolean [] t) {
int lMax;
int cpt;
boolean enCours;
lMax = 0;
cpt = 0;
enCours = false;
for ( int i = 0 ; i < t.length ; i++ ) {
if ( t[i] ) {
if ( !enCours ) {
cpt = 0;
enCours = true; }
cpt++; }
else {
if ( enCours ) {
if ( cpt > lMax ) {
lMax = cpt; }
enCours = false; } } }
if ( enCours ) {
if ( cpt > lMax ) {
lMax = cpt; } }
return lMax;
}
/* Test si un motif de booleens coincide */
/* avec les booleens presentes dans un tableau */
/* de booleens a partir d'un indice */
/* motif : Le tableau de booleens motif */
/* t : Le tableau de booleens où est effectué */
/* le test */
/* p : L'indice de recherche */
static boolean concordance(boolean [] motif,boolean [] t,int p) {
int i;
boolean res;
i = 0;
res = true;
while ( ( res ) && ( i < motif.length ) ) {
res = ( motif[i] == t[p] );
i++;
p++; }
return res;
}
/* Determination et retour de l'indice */
/* de la 1ère occurrence d'un motif de booleens */
/* recherché dans un tableau de booleens */
/* Retour de -1 si motif non present */
/* motif : Le tableau de booleens motif */
/* t : Le tableau de booleens où est effectuée */
/* la recherche */
static int premiereOccurrence(boolean [] motif,boolean [] t) {
int pos;
int i;
int nt;
pos = -1;
i = 0;
nt = t.length-motif.length+1;
while ( ( pos == -1 ) && ( i < nt ) ) {
if ( concordance(motif,t,i) ) {
pos = i; }
else {
i++; } }
return pos;
}
/* Calcul et retour un tableau de booleens */
/* construit à partir d'une chaine de caracteres */
/* ou les 0 codent des false et les 1 codent */
/* des true */
/* s : La chaine de caractères */
static boolean [] motif(String s) {
boolean [] t = new boolean[s.length()];
char [] tc = s.toCharArray();
for ( int i = 0 ; i < t.length ; i++ ) {
switch (tc[i]) {
case '0' :
t[i] = false;
break;
case '1' :
t[i] = true;
break;
default :
Ecran.afficherln("Erreur!!!");
break; } }
return t;
}
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.java
/* Fonction de comparaison de deux chaines */
/* de caracteres de longueurs identiques */
/* vis a vis de l'ordre alphabetique */
/* Valeur entiere retournee: */
/* 0 si chaines egales */
/* -1 si la premiere chaine est avant */
/* la seconde par ordre alphabetique */
/* 1 si la premiere chaine est apres */
/* la seconde par ordre alphabetique */
static int ordre(String s1,String s2) {
char [] t1 = Chaine.tableauCaracteres(s1);
char [] t2 = Chaine.tableauCaracteres(s2);
int lc = t1.length;
int res = 0;
int i = 0;
boolean go = true;
while ( go ) {
if ( i == lc ) {
go = false; }
else {
if ( t1[i] < t2[i] ) {
go = false;
res = -1; }
else {
if ( t1[i] > t2[i] ) {
go = false;
res = 1; } } }
i++; }
return(res);
}
/* Fonction de tri par ordre alphabetique */
/* d'un tableau de chaines de caracteres */
/* Technique de tri: Tri a bulle */
static void triBulleTableauDeChaines(String [] t) {
String aux;
boolean permutation;
int np = t.length-1;
do {
permutation = false;
for ( int j = 0 ; j < np ; j++ ) {
if ( ordre(t[j],t[j+1]) > 0 ) {
aux = t[j];
t[j] = t[j+1];
t[j+1] = aux;
permutation = true; } }
np--; }
while ( permutation ) ;
}
Clavier.class - Ecran.class - Chaine.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 au modifications suivantes près:
- Il s'applique à un tableau de Date et non à un tableau de String.
- La permutation entre variables s'applique à des Date et on à des String.
- La fonction de comparaison est à réécrire et doit comparer des Date.
|
TriBulleTableauDeDates.java
/* Type agrege de stockage d'une date */
/* formee d'un numero de jour, d'un numero */
/* de mois et d'un numero d'annee */
static class Date {
int jour = 1;
int mois = 1;
int annee = 1901; };
/* 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 */
static int ordre(Date d1,Date d2) {
int res;
if ( d1.annee < d2.annee ) {
res = -1; }
else {
if ( d1.annee > d2.annee ) {
res = 1; }
else {
if ( d1.mois < d2.mois ) {
res = -1; }
else {
if ( d1.mois > d2.mois ) {
res = 1; }
else {
if ( d1.jour < d2.jour ) {
res = -1; }
else {
if ( d1.jour > d2.jour ) {
res = 1; }
else {
res = 0; } } } } } }
return(res);
}
/* Fonction de tri par ordre alphabetique */
/* d'un tableau de Date */
/* Technique de tri: Tri a bulle */
static void triBulleTableauDeDate(Date [] t) {
Date aux;
boolean permutation;
int np = t.length-1;
do {
permutation = false;
for ( int j = 0 ; j < np ; j++ ) {
if ( ordre(t[j],t[j+1]) > 0 ) {
aux = t[j];
t[j] = t[j+1];
t[j+1] = aux;
permutation = true; } }
np--; }
while ( permutation ) ;
}
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.java
/* Type agrege de stockage des informations */
/* relatives a une position en trois dimensions */
static class Position3D {
double x = 0.0;
double y = 0.0;
double z = 0.0; };
/* Fonction de calcul de la distance */
/* entre une Positon3D et l'origine */
static double distanceOrigine(Position3D p) {
double d = Math.sqrt(p.x*p.x+p.y*p.y+p.z*p.z);
return d;
}
/* Fonction de recherche de l'indice de la valeur */
/* maximale d'un tableau de Position3D restreint */
/* a ses n premieres valeurs */
static int indiceDuMaximum(int n,Position3D [] t) {
double max = distanceOrigine(t[n]);
int iMax = n;
double d;
for ( int i = n-1 ; i >= 0 ; i-- ) {
d = distanceOrigine(t[i]);
if ( d > max ) {
max = d;
iMax = i; } }
return iMax;
}
/* Fonction de tri par selection d'un tableau */
/* de Position3D en fonction de la distance */
/* a l'origine */
static void triSelectionTableauDePosition3D(Position3D [] t) {
Position3D aux;
int iMax;
for ( int i = t.length-1 ; i > 0 ; i-- ) {
iMax = indiceDuMaximum(i,t);
if ( iMax != i ) {
aux = t[iMax];
t[iMax] = t[i];
t[i] = aux; } }
}
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 l'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.java
static final double 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) */
static double racine(double v) {
double ai = 0.0;
double af = 10.0;
double mid;
do {
mid = (af+ai)/2.0;
if ( mid*mid > v ) {
af = mid; }
else {
ai = mid; } }
while ( af-ai > EPSILON );
return mid;
}
Clavier.class - Ecran.class - Exemple d'exécution
|
|
