Correction de l'examen de TD
Complexité de l'algorithme de recherche dichotomique de la position d'une valeur entière dans un tableau trié de valeurs entières.
Cet algorithme de recherche est construit au moyen d'une simple boucle tant que. Sa
complexité sera de l'ordre du nombre d'exécution du contenu de la boucle.
A chaque exécution de la boucle, l'intervalle de recherche voit sa taille divisée par
deux. L'algorithme s'exécute jusqu'à ce que cet intervalle soit de taille 1. Le nombre
de fois où un nombre n doit être divisé par deux pour arriver à 1 est de l'ordre de
log2(n).
001 Action algo(tab,val)
002 Données-Résultats tab : Tableau [N] de entier
003 Données val : entier
004 Locales g,d : entier { Indices de parcours gauche et droit }
005 temp : entier { Variable auxiliaire de permutation }
006 g := 0
007 d := N-1
008 tant que g < d faire
009 tant que g < N et tab[g] <= val faire
010 g := g+1
011 fait
012 tant que d >= 0 et tab[d] > val faire
013 d := d+1
014 fait
015 si g < d alors
016 temp := tab[g]
017 tab[g] := tab[d]
018 tab[d] := temp
019 fsi
020 fait
021 fin action
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class Complexite {
static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
/* Fonction de creation d'un tableau d'entiers */
/* tires au hasard dans l'intervalle [0,99] */
/* n : nombre d'entiers du tableau */
/* Resultat fonction : Tableau de n entiers */
public static int [] creationTableauAleatoire(int n) {
int [] m = new int[n];
for ( int i = 0 ; i < n ; i++ )
m[i] =(int) (Math.random()*(100));
return(m);
}
/* Fonction d'affichage d'un tableau d'entiers */
/* t : Tableau d'entier a afficher */
public static void affichageTableau(int [] t) {
for ( int i = 0 ; i < t.length ; i++ )
System.out.print(" "+t[i]);
System.out.println();
}
/* Fonction de traitement d'un tableau d'entiers vis */
/* a vis d'une valeur v de maniere a regrouper dans */
/* la partie gauche toutes les valeurs plus petite */
/* que v et dans la partie droite toutes les valeurs */
/* plus grandes que v */
/* t : Tableau d'entiers a traiter */
/* v : Valeur de borne a traiter sur le tableau t */
public static void traitement(int [] t,int v) {
int g = 0;
int d = t.length-1;
System.out.println(g+" "+d);
while ( g < d ) {
while ( ( g < t.length ) && ( t[g] <= v ) )
g++;
while ( ( d >= 0 ) && ( t[d] > v ) )
d--;
System.out.println(g+" "+d);
if ( g < d ) {
int temp = t[g];
t[g] = t[d];
t[d] = temp; } }
}
/* Fonction principale */
public static void main(String [] args) throws IOException {
/* Initialisation du tableau de l'examen et de val */
int [] tab = { 7,8,2,3,6 };
int val = 4;
/* Affichage du tableau tab */
System.out.println("Le tableau initial est :");
affichageTableau(tab);
/* Traitement */
traitement(tab,val);
/* Affichage du resultat de l'execution de l'algorithme */
System.out.println("Apres traitement :");
affichageTableau(tab);
/* Lecture au clavier de la taille du tableau */
System.out.print("Taille du tableau : ");
int n = Integer.valueOf(flux.readLine()).intValue();
/* Lecture au clavier de la valeur de traitement */
System.out.print("Valeur : ");
int v = Integer.valueOf(flux.readLine()).intValue();
/* Creation d'un tableau de n entiers aleatoires */
int [] m = creationTableauAleatoire(n);
/* Affichage de ma matice m */
System.out.println("Le tableau initial est :");
affichageTableau(m);
/* Traitement */
traitement(m,v);
/* Affichage du resultat de l'execution de l'algorithme */
System.out.println("Apres traitement :");
affichageTableau(m);
}
}
Question 1
En deux itérations du tant que g < d, deux permutations sont réalisées entre les
couples de valeurs d'indice 0 et 3, et 1 et 2 pour obtenir en fin d'exécution le tableau
{ 3, 2, 8, 7, 6 }.
Cet algorithme réorganise les valeurs d'un tableau de telle manière que toutes les
valeurs inférieures à val soient placées dans la partie gauche du tableau et toutes les
valeurs supérieures à val soit placées dans la partie gauche. Dans ces deux parties,
les valeurs ne sont pas triées.
Question 2
N est le nombre de valeurs du tableau.
Dans le meilleur des cas, aucune permutation ne sera réalisée. Ce cas se produit
lorsque la répartition gauche-droite est déjà réalisée dans le tableau initial.
-> L'expression conditionnelle du "si" est évaluée au mieux 1 fois et
conduit à 0 affectations.
Pour les deux "tant que" internes, 2*(N+2) expressions conditionnelles sont
réalisées ainsi que N affectations.
Pour le "tant que" global, 2 expressions conditionnelles sont réalisées.
On ajoute les 2 affectations initiales.
Au total : N+2 affectations et 2*N+7 tests
Dans le pire des cas, le nombre de permutations est de l'ordre N/2. En effet, la cas le
plus défavorable se produit lorsqu'une permutation se produit autant de fois que
possible. Or une permutation à l'itération i entraine obligatoirement un déplacement
des indices g et d vers les indice g+1 et d-1 à l'itération i+1 car, à cette
itération, les valeurs en g et d sont correctement placées. Une permutation à une
itération est donc synonyme de convergence d'au minimum 2 valeurs d'indice (exactement 2
dans le cas défavorable) de g et d à l'itération suivante.
-> N/2 permutations au maximum (N nombre de valeurs du tableau).
-> L'expression conditionnelle du "si" est évaluée au pire (N/2)+1 fois et
conduit à 3*(N/2) affectations.
Pour les deux "tant que" internes, 2*N+(N/2+1)*2*2 expressions conditionnelles
sont réalisées ainsi que N affectations.
Pour le "tant que" global, (N/2)+1+1 expressions conditionnelles sont
réalisées.
On ajoute les 2 affectations initiales.
Au total : 3*(N/2)+N+2 affectations et 6*(N/2)+2*N+7 tests
Question 1
L'ensemble du planning est parcouru (2 boucles "pour"imbriquées). A chaque
créneau occupé, une variable compteur entière est incrémentée. A l'issue du parcours,
cette variable contient le nombre total de créneaux occupés.
Le pourcentage est obtenu en divisant cette valeur par le nombre total de créneaux du
planning (nombre de jours x nombre de créneaux par jour) et en multipliant par 100. On
prêtera attention à effectuer les calculs en réel pour éviter les problèmes
éventuels liés aux divisions entières.
001 Fonction pourcentageReservation(p) : reel
002 Données p : Tableau [NBJ][NBC] de booleen
003 Locale cpt : entier { Compteur de creneaux affectes }
004 j,c : entier { Indices de parcours du planning }
005 res : reel { Resultat de la fonction }
006 cpt := 0
007 pour j de 0 à NBJ-1 faire
008 pour c de 0 à NBC-1 faire
009 si p[j][c] alors
010 cpt := cpt+1
011 fsi
012 fait
013 fait
014 res = (cpt*100.0)/(NBJ*NBC)
015 Resultat : res
016 fin fonction
Question 2
La ligne du planning correspondant au jour testé est parcourue à la recherche d'un
créneau occupé. Si aucun créneau n'est occupé, vrai est rendu, sinon faux.
Un "tant que" est utilisé de manière à rendre possible l'interuption du
parcours lorsqu'un créneau réservé est trouvé.
001 Fonction estLibre(p,j) : booleen
002 Données p : Tableau [NBJ][NBC] de booleen
003 j : entier
004 Locales c : entier { Indice de parcours des creneaux }
005 { du jour j du planning p }
006 b : booleen { Resultat de la fonction }
007 c := 0
008 b := vrai
009 tant que b et ( c < NBC ) faire
010 si p[j][c] alors
011 b := faux
012 fsi
013 c := c+1
014 fait
015 Resultat : b
016 fin fonction
Question 3
Une action doit être développée car deux paramètres sont des résultats dont un par
ailleurs est en données.
Le compteur entier en paramètre est initialisé à O.
Un "tantque" est utilisé pour parcourir le tableau des demandes de
réservation. Deux conditions d'arrêt sont implantées:
- Tous le tableau a été parcouru.
- On a trouvé un -1 en indice 0 de la ligne courante.
Si le créneau correspondant à une demande de réservation est libre, on le réserve,
sinon le compteur du nombre de réservation non satisfaites est incrémenté de 1.
001 Action reservation(p,r,cpt) : entier
002 Données-Résultats p : Tableau [NBJ][NBC] de booleen
003 Données r : Tableau [MAX][2] de entier
004 Résultats cpt : entier
005 Locales cpt : entier { Compteur de reservation non realisees }
006 i : entier { Indice de parcours du tableau }
007 { de demandes de reservation }
008 cpt := 0
009 i := 0
010 tant que ( i < MAX ) et ( r[i][0] != -1 ) faire
011 si p[r[i][0]][r[i][1]] alors
012 cpt := cpt+1
013 sinon
014 p[r[i][0]][r[i][1]] := vrai
015 fsi
016 i := i+1
017 fait
018 fin action
Implantation complète en Java
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class ReservationSalle {
static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
/* Fonction de creation d'un planning */
/* initialise avec des booleens aleatoires */
/* nbj : Nombre de jours du planning */
/* nbc : Nombre de creneaux du planning */
/* v : reel coefficient de chance qu'un creneau */
/* soit affecte */
/* Resultat fonction : Matrice de booleens */
public static boolean [][] creationPlanningAleatoire(int nbj,int nbc,double v) {
/* Allocation de la matrice */
boolean [][] p = new boolean[nbj][nbc];
/* Pour tous les jours du planning a initialiser */
for ( int j = 0 ; j < nbj ; j++ )
/* Pour tous les creneaux du planning a initialiser */
for ( int c = 0 ; c < nbc ; c++ )
/* Initialisation avec un booleen aleatoire */
p[j][c] = (Math.random() < v);
/* Resultat de la fonction */
return(p);
}
/* Fonction de creation d'une matrice de reservations */
/* initialisee avec des valeurs aleatoires */
/* t : Nombre de reservations possibles de la matrice */
/* nb : Nombre de reservations effectives */
/* nbj : Nombre de jours de reservation */
/* nbc : Nombre de creneaux de reservation */
/* Resultat fonction : Matrice d'entiers */
public static int [][] creationAleatoireReservations(int t,int nb,int nbj,int nbc) {
/* Allocation de la matrice */
int [][] r = new int[t][2];
/* Pour toutes les reservations a initialiser */
for ( int i = 0 ; i < nb ; i++ ) {
/* Initialisation d'une reservation */
r[i][0] =(int) (Math.random()*nbj);
r[i][1] =(int) (Math.random()*nbc); }
/* Pour toutes les reservations restantes possibles */
/* dans r */
for ( int i = nb ; i < t ; i++ ) {
/* Initialisation d'une reservation a libre */
r[i][0] = -1; }
/* Resultat de la fonction */
return(r);
}
/* Fonction d'affichage d'un planning */
/* p : Planning a afficher */
public static void affichagePlanning(boolean [][] p) {
/* Pour tous les jours du planning */
for ( int j = 0 ; j < p.length ; j++ ) {
/* Pour tous les creneaux du jour courant */
for ( int c = 0 ; c < p[j].length ; c++ )
/* Si le creneau courant du jour courant est libre */
if ( p[j][c] )
/* On affiche sans retour a la ligne le caractere V */
System.out.print(" V");
else
/* Sinon, on affiche F sans retour a la ligne */
System.out.print(" F");
/* On va a la ligne quand les creaneaux d'un jour */
/* sont tous affiches */
System.out.println(); }
}
/* Fonction d'affichage d'une matrice de demandes */
/* de reservations */
/* r : Tableau de reservations a afficher */
public static void affichageDemandesReservation(int [][] r) {
/* Definition et initialisation a 0 d'un indice */
/* de parcours de la matrice des reservations */
int i = 0;
/* Tant que tous le tableau des reservations n'est pas */
/* parcouru et que la reservation courante est valide */
while ( ( i < r.length ) && ( r[i][0] != -1 ) ) {
/* Affichage de la demande de reservation courante */
System.out.println(r[i][0]+" "+r[i][1]);
/* L'indice de parcours du tableau des demandes */
/* de reservation est incremente de 1 */
i++; }
}
/* Fonction de calcul du pourcentage de reservation */
/* de l'ensemble des creneaux d'un planning */
/* p : Planning a traiter */
/* Resultat fonction : Reel (pourcentage de creneaux */
/* reserves) */
public static double pourcentageReservation(boolean [][] p) {
/* Definition et initialisation a 0 d'un compteur */
int cpt = 0;
/* Pour tous les jours du planning */
for ( int j = 0 ; j < p.length ; j++ ) {
/* Pour tous les creneaux du jour courant */
for ( int c = 0 ; c < p[j].length ; c++ )
/* Si le creneau courant du jour courant est reserve */
if ( p[j][c] )
/* Le compteur est incremente de 1 */
cpt++; }
/* Resultat fonction : Compteur/nombre de creneaux */
/* total du planning * 100 */
return((double) cpt/p.length/p[0].length*100.0);
}
/* Fonction de determination si tous les creneaux */
/* d'un jour d'un planning sont libres */
/* p : Planning a traiter */
/* j : Jour a tester */
/* Resultat fonction : Booleen (vrai si tous */
/* sont libres, faux sinon) */
public static boolean estLibre(boolean [][] p,int j) {
/* Definition et initialisation a 0 d'un indice */
/* de parcours des creneaux du jour j du planning p */
int c = 0;
/* Pour tous les creneaux du jour j */
while ( c < p[j].length ) {
/* Si le creneau c du jour j est reserve */
if ( p[j][c] )
/* La fonction est terminee avec pour resultat faux */
return(false);
/* l'indice de parcours des creneaux est incremente */
/* de 1 */
c++; }
/* Resultat fonction : Si la fonction ne s'est pas */
/* terminee avec pour resultat faux, le resultat */
/* est vrai */
return(true);
}
/* Fonction de reservation dans un planning */
/* des demandes de reservation stockees dans un tableau */
/* de reservations */
/* p : Planning a traiter */
/* r : Tableau des reservations a traiter */
/* Resultat fonction : Entier (nombre de reservations */
/* non effectuees car non possibles */
public static int reservation(boolean [][] p,int [][] r) {
/* Definition et initialisation a 0 d'un compteur */
/* de reservations non effectuees */
int cpt = 0;
/* Definition et initialisation a 0 d'un indice */
/* de parcours de la matrice des reservations */
int i = 0;
/* Tant que tous le tableau des reservations n'est pas */
/* parcouru et que la reservation courante est valide */
while ( ( i < r.length ) && ( r[i][0] != -1 ) ) {
/* Si le creneau correspondant a la demande */
/* de reservation courante est deja reserve */
if ( p[r[i][0]][r[i][1]] )
/* Le compteur de reservation est incremente de 1 */
cpt++;
else
/* Sinon, la reservation est effectuee */
p[r[i][0]][r[i][1]] = true;
/* L'indice de parcours du tableau des demandes */
/* de reservation est incremente de 1 */
i++; }
/* Resultat fonction : Entier (Nombre de reservations */
/* non effectuees */
return(cpt);
}
/* Fonction principale */
public static void main(String [] args) throws IOException {
/* Lecture au clavier du nombre de jours du planning */
System.out.print("Nombre de jours : ");
int nbj = Integer.valueOf(flux.readLine()).intValue();
/* Lecture au clavier du nombre de creneaux par jour */
System.out.print("Nombre de creneaux par jour : ");
int nbc = Integer.valueOf(flux.readLine()).intValue();
/* Lecture au clavier du facteur de reservation */
System.out.print("Facteur de reservation : ");
double f = Double.valueOf(flux.readLine()).doubleValue();
/* Creation d'un tableau de n entiers aleatoires */
boolean [][] p = creationPlanningAleatoire(nbj,nbc,f);
/* Affichage du planning */
System.out.println("Le planning initial est :");
affichagePlanning(p);
/* Calcul et affichage du pourcentage de reservation */
System.out.println("Le pourcentage de reservation est : "+pourcentageReservation(p));
/* Lecture au clavier du jour a tester */
System.out.print("Jour a tester : ");
int j = Integer.valueOf(flux.readLine()).intValue();
/* Calcul et affichage de la diponibilte entiere */
/* d'un jour */
System.out.println("Le jour "+j+" est libre : "+estLibre(p,j));
/* Lecture au clavier de la taille du tableau */
/* des reservations */
System.out.print("Taille du tableau : ");
int t = Integer.valueOf(flux.readLine()).intValue();
/* Lecture au clavier du nombre de reservations */
System.out.print("Nombre de reservations : ");
int nb = Integer.valueOf(flux.readLine()).intValue();
int [][] re = creationAleatoireReservations(t,nb,nbj,nbc);
/* Affichage de l'ensemble des demandes de reservation */
affichageDemandesReservation(re);
/* Reservation et affichage du resultat */
System.out.println("Le nombre de reservations non effectuees est : "+reservation(p,re));
/* Affichage du planning apres reservations */
System.out.println("Le planning final est :");
affichagePlanning(p);
}
}
Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr
