Syllabus 2023-2024

Haute École Bruxelles-Brabant
École Supérieure d’Informatique

Rue Royale, 67. 1000 Bruxelles
02/219.15.46 – esi@he2b.be
Algorithmique
2023-2024
Bachelor en Informatique
ALG2
G. Cuvelier(CUV), A. Hallal(HAL), C. Leignel(CLG),

A. Pollaris(APO).
Document produit avec LATEX.
Version du 16 mars 2024.
Table des matières
1 Algorithmes d’insertions et de recherches 1

1.1 Insertion dans un tableau non trié . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Gestion des tableaux non triés . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Insertion dans un tableau trié . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Gestion des tableaux triés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 La recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 Introduction à la complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Algorithmes de tris 19
2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Tri par sélection des minima successifs . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Tri bulle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Cas particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 Références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Les tableaux à 2 dimensions 27

3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Parcours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 La liste 41
4.1 L’idée de liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Comment implémenter une liste en mémoire ? . . . . . . . . . . . . . . . . . . . 42
4.3 Les ArrayList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.5 L’interface d’une liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.6 Implémenter une ArrayList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.7 Liste chaînées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.8 Implémenter une linked list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.9 Les listes : un exemple d’application . . . . . . . . . . . . . . . . . . . . . . . . 57
4.10 Les listes : exercices récapitulatifs . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5 La pile 61
5.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Implémentation orienté-objet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3 Exemple d’utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6 La file 65
6.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2 Implémentation orienté-objet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7 La récursivité 69
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.2 Définitions récursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3
TABLE DES MATIÈRES
7.3 Algorithme récursif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7.4 Un grand exemple classique de programmation récursive : la factorielle . . . . . 72
7.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
8 Mises en pratique 75
8.1 Se poser les bonnes questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8.2 Les structures de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
8.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Compléments 85
.1 Énumération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
.2 Gestion des erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Notre pseudo-code 87
.3 Exemple : un mot dans un miroir . . . . . . . . . . . . . . . . . . . . . . . . . . 88
.4 Exemple : Position des minimums. . . . . . . . . . . . . . . . . . . . . . . . . . 89
Aide mémoire 91
.5 Manipuler le hasard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
.6 La liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
.7 ArrayList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
.8 SinglyLinkedList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4
Introduction
Dans les cours de ALG1 et DEV1, vous avez appris les bases de la programmation et du
développement logiciel. L’une des difficultés auxquelles vous avez été confrontées était celle
de résoudre des problèmes, plus ou moins difficiles : jouer au Mastermind, afficher une suite
d’entiers déterminée, afficher un calendrier, etc.
Penser l’algorithme de résolution d’un problème et décrire cet algorithme, sont deux étapes
qui s’entremêlent : en réfléchissant au problème, on commence à écrire une solution, on change
d’avis, on ré-écrit, etc. Durant cette phase, il est nécessaire de pouvoir décrire sa pensée de
façon simple mais suffisamment précise. Ceci nous amène à écrire en langage naturel ou en
pseudo-code. Cela ressemble à du code, mais on ne se force pas à avoir une syntaxe parfaite.
Sur un document tel que celui-ci, l’utilisation de pseudo code se justifie pour :
. montrer à l’apprenant·e comment il ou elle peut écrire son pseudo-code, et
. gagner en place et en lisibilité pour des algorithmes plus complexes.
Voyez l’annexe .2 pour une explication du pseudo-code que nous utilisons.
5
Chapitre
Algorithmes d’insertions et de re-
1 cherches
Souvent lorsque les applications stockent des données, ces données changent. Il est nécessaire
d’en ajouter, de modifier certaines, d’en rechercher, d’en supprimer.
Exemple Imaginons qu’une école organise un événement libre et gratuit pour les étudiants et
les étudiantes. Mais pour y assister, il est nécessaire de s’inscrire. Nous voulons fournir ce qu’il
faut pour :
. inscrire un ou une étudiant·e ;

. vérifier l’inscription ;
. désinscrire ;
. afficher la liste des personnes inscrites.
Nous allons, pour l’exemple, stocker les numéros d’étudiants et d’étudiantes dans un tableau 1 .
Comme le tableau ne sera généralement pas rempli, nous allons créer un tableau « trop grand »
et gérer sa taille logique. Nous avons deux variables :
. registered : le tableau des numéros d’étudiants

. nRegistered : le nombre d’étudiant·es actuellement inscrit·es (la taille logique du ta-
bleau)
Nous allons envisager deux cas :

1. les numéros seront placés dans le tableau sans ordre imposé ;
2. les numéros seront placés dans l’ordre.
1.1 Insertion dans un tableau non trié

Les valeurs sont stockées dans le tableau dans un ordre quelconque. Par exemple :
registered = 42010 41390 43342 42424 ? ? ? ? ...
nRegistered = 4
Il y a pour le moment quatre personnes inscrites dont les numéros sont ceux repris dans les
quatre premières cases du tableau.
1.1.1 Inscription
Pour inscrire un étudiant ou une étudiante, il suffit de l’ajouter à la suite dans le tableau. Par
exemple, en partant de la situation décrite ci-dessus, l’inscription de l’étudiant numéro 42123
aboutit à la situation suivante :
registered = 42010 41390 43342 42424 42123 ? ? ? ...
nRegistered = 5
1. Ce n’est bien sûr pas la bonne manière de faire pour une application réelle pour laquelle nous utiliserions
probablement une base de données. . . mais c’est une autre histoire. . . et un autre cours.
1
1.1. INSERTION DANS UN TABLEAU NON TRIÉ
L’algorithme est assez simple :
int register(int[n] registered, int nRegistered, int number)

registered[nRegistered] = number
return nRegistered + 1
En langage Java, il n’est pas possible de passer nRegistered en entrée sortie puisque le passage
de paramètre se fait par valeur et que int est un type primitif. Il faudra que ce soit en valeur
de retour. Nous pourrions écrire :

public static int register(int[] registered, int nRegistered, int number){
// On peut imaginer vérifier que l'étudiant n'est pas déjà inscrit
// On peut imaginer vérifier qu'il reste de la place
// (c-à-d que le tableau n'est pas plein)
registered[nRegistered] = number;
return nRegistered + 1;
}

Dans ce cas, c’est bien le code appelant qui devra maintenir la valeur de la taille logique à
jour.
1.1.2 Vérifier une inscription

Pour vérifier si un étudiant est déjà inscrit, il faut le rechercher dans la partie utilisée du
tableau. Cette recherche se fait via un parcours avec sortie prématurée.
L’algorithme ne va pas se contenter de retourner un booléen précisant si le numéro est trouvé
mais va retourner l’indice dans le tableau de ce numéro, -1 sinon.
int check(int[n] registered, int nRegistered, int number)

int i = 0
while i < nRegistered AND registered[i] 6= number
i=i+1
if i < nRegistered
return i
else
return-1
En Java :

public static int check(int[] registered, int nRegistered, int number){
int i = 0;
while (i < nRegistered && registered[i] != number){
i++;
}
if (i<nRegistered){
return i;
} else {
return -1;
}
}

1.1.3 Désinscription
Pour désinscrire un étudiant, il faut le trouver dans le tableau et l’enlever. Attention, il ne
peut pas y avoir de trou dans un tableau (il n’y a pas de case vide). Le plus simple est d’y
déplacer le dernier élément. Par exemple, reprenons la situation après inscription de l’étudiant
numéro 42123.
registered = 42010 41390 43342 42424 42123 ? ? ? ...
nRegistered = 5
2
1.2. GESTION DES TABLEAUX NON TRIÉS
La désinscription de l’étudiant numéro 41390 donnerait ce qui suit.

Nous avons volontairement indiqué le 42123 en 5e position. Il est toujours là mais ne sera pas
considéré par les algorithmes puisque cette case est au-delà de la taille logique (donnée par la
variable nRegistered).
registered = 42010 42123 43342 42424 42123 ? ? ? ...
nRegistered = 4
L’algorithme est assez simple à écrire en utilisant la recherche écrite juste avant :
int unsubscribe(int[n] registered, int nRegistered, int number)

int pos = check(registered, nRegistered, number)
registered[pos] = registered[nRegistered - 1]
return nRegistered - 1
En Java :

public static int unsubscribe(int[] registered, int nRegistered, int number){
int pos = check(registered, nRegistered, number);
registered[pos] = registered[nRegistered - 1];
return nRegistered - 1;
}

1.1.4 Exercices
1. Éviter la double inscription.
Comment modifier l’algorithme d’inscription pour s’assurer qu’un étudiant ne s’inscrive
pas deux fois ?
2. Limiter le nombre d’inscriptions.
Comment modifier l’algorithme d’inscription pour refuser une inscription si le nombre
maximal de participant est atteint en supposant que ce maximum est égal à la taille
physique du tableau ?
3. Vérifier la désinscription.
Que se passerait-il avec l’algorithme de désinscription tel qu’il est si on demande à
désinscrire un étudiant non inscrit ? Que suggérez-vous comme changement ?
4. Optimiser la désinscription.
Dans l’algorithme de désinscription tel qu’il est, voyez-vous un cas où on effectue une
opération inutile ? Avez-vous une proposition pour l’éviter ?
1.2 Gestion des tableaux non triés

Par gestion des tableaux, on s’interesse à présent aux actions suivantes : rechercher, ajouter,
supprimer des données dans un tableau non trié d’entiers.
Dans notre cours d’Alg2, on considère tout comme en Alg1 que le contenu d’un tableau n’est
pas initialisé lors de sa déclaration. Il est cependant utile d’avoir une fonction initialiser() qui
reçoit le tableau à initialiser et une valeur que l’on assignera à chaque case. Pour un tableau
d’entiers par exemple, l’algorithme ressemblerait à :
void initialiser(int[n] tab, int val)

for i from 0 to n-1
tab[i] = val
3
1.2.1 Rechercher
Spécification
Retourner l’indice d’une donnée trouvée dans un tableau non trié ou -1 si elle n’est pas trouvée.
Nous supposons que le tableau n’est pas rempli, l’algorithme recevra donc une valeur repré-
sentant le nombre d’éléments du tableau. Cette valeur est inférieure à la taille physique du
tableau bien sûr.
Données : le tableau à analyser, le nombre d’éléments dans ce tableau (taille logique), la
valeur à rechercher
Résultat : la position de l’élément si il est dans le tableau et -1 sinon.
Solution
Il suffit de parcourir le tableau jusqu’à ce que l’on trouve la valeur ou bien que l’on arrive à la
fin de sa taille logique.
tant que l’on n’est pas à la fin et la val n’est pas trouvée
incrémenter l’indice
fin tant que
si on n’est pas à la fin alors
on a trouvé
sinon
on n’a pas trouvé et on retourne -1
fin si
langage naturel
int indexValue(int[n] is,int nValues, int value)

int i = 0
while i < nValues AND is[i] 6= value
i=i+1
if i < nValues
return i
else
return-1

public static int indexValue(int[] is, int nValues, int value){
int i = 0;
while (i < nValues && is[i] != value){
i++;
}
if (i < nValues){
return i;
} else {
return -1;
}
}

1.2.2 Ajouter
Spécification
Ajouter une donnée non encore présente dans le tableau de données non triées.
Données : le tableau à modifier, le nombre d’éléments dans ce tableau, la valeur à ajouter
Résultat : le tableau reçu est modifié en lui ajoutant la valeur si elle n’y était pas déjà
4
Solution
Si l’algorithme reçoit le tableau, le nombre d’éléments et la valeur à ajouter, il suffit d’insérer
la valeur dans le tableau à la première place disponible. . . après avoir vérifié qu’elle n’est pas
présente. Cette vérification peut se faire simplement en utilisant l’algorithme indexValue. Si
celui-ci retourne -1, c’est que la valeur n’est pas présente.
if nValues < taille du tableau AND indexValue = -1

ajouter la valeur à la fin du tableau
langage naturel
void add(int[n] is, int nValues, int value)

if nValues < is.length AND indexValue(is, nValues, value) = -1
is[nValues] = value
nValues = nValues + 1
Remarque En langage Java, le passage de paramètre se faisant par valeur (cfr. Chapitre
1 page 1), la taille logique du tableau doit être retournée et maintenue à jour par le code
appelant. En langage Java, cet algorithme aurait l’allure suivante :

public static int add(int[] is, int nValues, int value){
if (nValues < is.length && indexValue(is, nValues, value) == -1){
is[nValues] = value;
nValues = nValues + 1;
}
return nValues;
}

1.2.3 Supprimer
Spécification
Supprimer une donnée d’un tableau de données non triées.
Données : le tableau à modifier, le nombre d’éléments dans ce tableau, la valeur à supprimer
Résultat : le tableau reçu est modifié en lui supprimant la valeur
Solution
Comme le tableau n’est pas trié, pour supprimer une valeur, il suffit de trouver l’index de cette
valeur et de placer la dernière valeur à sa place.
index = l’index de la valeur à supprimer

if index != -1
is[index] = is[nValues-1]
nValues - -
end if
langage naturel
void delete( int[n] is,int nValues,int value )

int index = indexValue(is, nValues, value)
if index 6= -1
is[index] = is[nValues-1]
nValues = nValues - 1

public static int delete(int[] is, int nValues, int value){
int index = indexValue(is, nValues, value);
if (index != -1){
5
is[index] = is[nValues];
nValues = nValues - 1;
}
return nValues;
}

6
1.3. INSERTION DANS UN TABLEAU TRIÉ
1.3 Insertion dans un tableau trié

Imaginons à présent que nous maintenons un ordre dans les données du tableau. En reprenant
l’exemple utilisé pour les données non triées, nous avons :
registered = 41390 42010 42424 43342 ? ? ? ? ...
nRegistered = 4
— Qu’est-ce que ça change au niveau des algorithmes ?

— Beaucoup !
Par exemple, plus question de placer un nouvel inscrit à la suite des autres ; il faut trouver sa
place.
1.3.1 Rechercher la position d’une inscription

Tous les algorithmes que nous allons voir dans le cadre de données triées ont une partie en
commun : la recherche de la position du numéro, s’il est présent ou de la position où il aurait
dû être s’il est absent. Commençons par cela.
L’algorithme est assez proche de celui de la vérification d’une inscription vu précédemment si
ce n’est que l’algorithme peut s’arrêter dès qu’un numéro plus grand est trouvé. Nous allons
décomposer l’algorithme en deux parties : la première pour la recherche de la position à laquelle
devrait se trouver le numéro et la seconde pour vérifier que c’est bien le bon numéro qui se
trouve à cette position.
int find(int[n] registered, int nRegistered, int number)

int pos = findPosition(registered, nRegistered, number)
if registered[pos] == number
return pos
else
return-1
int findPosition(int[n] registered, int nRegistered, int number)

int pos= 0
while pos < nRegistered AND registered[pos] < number
pos = pos + 1
return pos
En Java :

/∗
∗ Recherche d'un étudiant ou d'une étudiante par son numéro d'id.
∗ return: la position où a été trouvé le numéro
∗ ou -1 si non présent
∗/
public static int find( int[] registered, int nRegistered, int number){
int pos = findPosition(registered, nRegistered, number);
if (registered[pos] == number){
return pos;
} else {
return -1;
}
}
/∗
∗ Recherche d'une position
∗ return: la position à laquelle est ou devrait être le numéro
∗/
public static int findPosition( int[] registered, int nRegistered, int number){
int pos = 0,
while (pos < nRegistered && registered[pos] < number){
pos++;
}
7
return pos;
}

Comprenez-vous pourquoi :
. registered[pos] < number contient un ’<’ dans la condition du tant que et pas un ’6=’ ?
. la condition du if est insuffisante. Que se passe-t-il si la valeur recherchée est absente du
tableau et strictement supérieure à toutes celles figurant dans le tableau ?
Le if tel que présenté dans l’algorithme peut se réécrire grâce à l’opérateur ternaire de Java.
Profitons en pour le présenter.
ConditionalExpression:
Condition ? Expression : Expression
Si la condition est vraie, l’expression prend la première valeur et si la condition est fausse, ce
sera la seconde valeur. Par exemple : heure < 12 ? “matin” : “soir” vaut “soir” si heure vaut 15.

/∗∗
∗ Recherche une inscription dans le tableau.
∗
∗ @param registered le tableau d'inscrits
∗ @param nRegistered le nombre d'inscrits
∗ @param number le numéro à chercher
∗ @return la position dans le tableau, -1 si non présent
∗/
public static int find(int[] registered, int nRegistered, int number){
return registered[pos] == number ? pos : -1;
}
/∗∗
∗ Recherche la position que le nombre soit présent ou pas.
∗ @param number le numéro à chercher
∗ @return la position à laquelle est ou devrait être le numéro.
∗/
public static int findPosition{int[] registered, int nRegistered, int number){
int pos = 0;
while (pos < nRegistered && registered[pos] < number){
pos = pos + 1;
}
return pos;
}

1.3.2 Inscrire un étudiant

L’inscription d’un étudiant se fait en trois étapes :
1. recherche de l’étudiant via l’algorithme vu à l’instant, ce qui nous donne la place où le
placer ;
Nous ne vérifions pas si l’étudiant ou l’étudiante est déjà présent·e dans le tableau.
2. libération de la place pour l’y mettre ;
Cette opération n’est pas triviale. Si vous tenez des cartes en main, il est facile d’insérer
une nouvelle carte à n’importe quelle position. Avec un tableau, il en va tout autrement ;
pour insérer un élément à un endroit donné, il faut décaler tous les suivants d’une position
sur la droite.
3. placer l’élément à la position libérée.
Ce qui nous donne :
8
int subscribe(int[n] registered, int nRegistered, int number)

int pos= findPosition(registered, nRegistered, number)
shiftRight(registred,pos, nRegistered-1)
registered[pos] = number
return nRegistered + 1
void shiftRight(int[n] tab, int begin, int end)
for i from end to begin by −1
tab[i + 1] = tab[i]
En Java :

/∗∗
∗ Inscrit un ou une étudiant.e.
∗
∗ @param number le numéro à enregistrer
∗/
public static int subscribe(int[] registred, int nRegistered, int number){
shiftRight(registred, pos, nRegistered-1);
registered[pos] = number;
return nRegistered + 1;
}
/∗∗
∗ Décale les éléments du tableau de begin à end un à droite.
∗ @param tab le tableau
∗ @param begin l'indice de départ
∗ @param end l'indice de fin
∗/
public static void shiftRight(int[] tab, int begin, int end){
for (int i = end; i >= begin; i = i - 1){
tab[i + 1] = tab[i];
}
}

1.3.3 Désinscription
Ici, il va falloir décaler vers la gauche les éléments qui suivent celui à supprimer.
int unsubscribe(int[n] registered, int nRegistered, int number)

int pos= findPosition(registered, nRegistered, number)
shiftLeft(registred,pos+1, nRegistered)
return nRegistered - 1
void shiftLeft(int[n] tab, int begin, int end)
for i from begin to end
tab[i - 1] = tab[i]
En Java :

/∗∗
∗ Désinscrit un ou une étudiant.e.
∗
∗ @param number le numéro à supprimer
∗/
public static int unsubscribe(int[] registred, int nRegistered, int number){
shiftLeft(registred,pos+1, nRegistered);
return nRegistered - 1;
}
9
1.4. GESTION DES TABLEAUX TRIÉS
/∗∗
∗ Décale les éléments du tableau de begin à end un à gauche
∗ (et écrase donc l'élément en position begin-1).
∗ @param tab le tableau
∗ @param begin l'indice de départ
∗ @param end l'indice de fin
∗/
public static void shiftLeft(int[] tab, int begin, int end){
for (int i = begin; i <= end; i = i + 1){
tab[i - 1] = tab[i];
}
}

1.3.4 Exercices
1. Éviter la double inscription.
Comment modifier l’algorithme d’inscription pour s’assurer qu’un étudiant ne s’inscrive
pas deux fois ?
2. Limiter le nombre d’inscriptions.
Comment modifier l’algorithme d’inscription pour refuser une inscription si le nombre
maximal de participants est atteint en supposant que ce maximum est égal à la taille
physique du tableau ?
3. Vérifier la désinscription.
Que se passerait-il avec l’algorithme de désinscription tel qu’il est si on demande à
désinscrire un étudiant non inscrit ? Que suggérez-vous comme changement ?
1.4 Gestion des tableaux triés

Rechercher, ajouter, supprimer des données triées dans un tableau trié. Par exemple dans un
tableau d’entiers.
1.4.1 Rechercher
Spécification
Rechercher la position où a été trouvé l’élément ou la position où il aurait dû être.
Données : le tableau à analyser, le nombre d’éléments dans ce tableau, la valeur à rechercher
Résultat : la position où a été trouvée la valeur ou la position où elle aurait dû être
Solution
L’algorithme retourne la position où a été trouvée la valeur ou celle où elle devrait être. En
parcourant le tableau, il suffit de s’arrêter dès que l’élément du tableau est plus grand ou égal
à la valeur recherchée.
index int findIndex( int[] is, int nValues, int value )

int index = 0
while index < nValues AND is[index] < value
index = index + 1
return index

public static int findIndex(int[] is, int nValues, int value){
int index = 0;
while (index < nValues && is[index] < value){
index++;
}
return index;
10
}

1.4.2 Ajouter
Spécification
Ajouter une donnée non encore présente dans le tableau de données triées.
Données : le tableau à modifier, le nombre d’éléments dans ce tableau, la valeur à ajouter
Résultat : le tableau reçu est modifié en lui ajoutant la valeur si elle n’y était pas déjà
Solution
Pour faire un ajout sans doublon dans un tableau trié, il faut :
1. vérifier que la valeur n’est pas déjà présente ;

2. rechercher l’endroit ou elle devrait être placée ;
3. déplace les valeurs plus grande d’une position vers la droite ;
4. insère la valeur à sa place.
En décomposant le problème, voici une solution :
int add( int[] is, int nValues, int value )

int index
if verify(is, nValues, value) == -1
index = findIndex(is, nValues, value)
shiftRight(is, index, nValues)
is[index] = value
nValues = nValues + 1
return nValues
int verify( int[] is, int nValues, int value )
int index
index = findIndex( is, nValues, value)
if is[index] == value
return index
else
return-1
void shiftRight( int[] is, int begin, int end )
for i from end to begin by −1
is[i+1] = is[i]

/∗∗
∗ Ajoute un nombre s'il n'est pas présent.
∗
∗ @param is le tableau d'éléments
∗ @param nValues le nombre d'éléments du tableau (taille logique)
∗ @param value la valeur à insérer
∗/
public static int add(int[] is, int nValues, int value){
int index;
if (verify(is, nValues, value) == -1){
index = findIndex(is, nValues, value);
shiftRight(is, index, nValues);
is[index] = value;
nValues++;
}
return nValues;
}
/∗∗
∗ Vérifie si la valeur est dans le tableau.
11
∗
∗ @param nValues le nombre d'éléments du tableau (taille logique)
∗ @param value la valeur à insérer
∗/
public static int verify(int[] is, int nValues, int value){
int index = findIndex(is, nValues, value);
if (is[index] == value) {
return index;
} else {
return -1;
}
}
/∗∗
∗ Décale d'une position vers la droite les éléments
∗ entre position début et fin.
∗
∗ @param begin la position de début
∗ @pasam end la position de fin
∗/
public static void shiftRight(int[] is, int begin, int end){
for (int i = end; i >= begin; i--){
is[i+1] = is[i];
}
}

1.4.3 Supprimer
Spécification
Supprimer une donnée d’un tableau de données triées.
Données : le tableau à modifier, le nombre d’éléments dans ce tableau, la valeur à supprimer
Résultat : le tableau reçu est modifié en lui supprimant la valeur
Solution
Pour supprimer un élément, dès lors qu’il est trouvé, il suffit de décaler tous les éléments à sa
droite vers la gauche et adapter la taille logique.
int delete( int[] is, int nValues, int value )

int index
if verify(is, nValues, value) 6= -1
index = findIndex(is, nValues, value)
shiftLeft(is, index + 1, nValues)
nValues = nValues - 1
return nValues
void shiftLeft( int[] tabt, int begin, int end )
for i from end to begin
is[i-1] = is[i]

public static int delete(int[] is, int nValues, int value){
int index;
if (verify(is, nValues, value) != -1){
index = findIndex(is, nValues, value);
shiftLeft(is, index+1, nValues);
nValues = nValues - 1;
}
return nValues;
}
public static void shiftLeft(int[] is, int begin, int end){
12
1.5. LA RECHERCHE DICHOTOMIQUE
for (int i=begin; i <= end; i++){

is[i-1] = is[i];
}
}

1.4.4 Intérêt de trier les valeurs ?

Est-ce que trier les valeurs est vraiment intéressant ?
La recherche est un peu plus rapide. En moyenne deux fois plus rapide si l’élément ne s’y
trouve pas. Par contre, l’ajout et la suppression d’un élément sont plus lents. Les algorithmes
sont plus complexes à écrire et à comprendre. Le gain ne parait pas évident et en effet, en
l’état, il ne l’est pas.
Mais c’est sans compter un autre algorithme de recherche, beaucoup plus rapide, la recherche
dichotomique, que nous allons voir maintenant.
1.5 La recherche dichotomique

La recherche dichotomique est un algorithme de recherche d’une valeur dans un tableau trié.
Il a pour essence de réduire à chaque étape la taille de l’ensemble de recherche de moitié,
jusqu’à ce qu’il ne reste qu’un seul élément dont la valeur devrait être celle recherchée, sauf
bien entendu en cas d’inexistence de cette valeur dans l’ensemble de départ.
Pour l’expliquer, nous allons considérer un tableau d’entiers complètement rempli. Il sera facile
d’adapter la solution à un tableau partiellement rempli (avec une taille logique) ou un tableau
contenant tout autre type de valeurs qui peut s’ordonner.
Description de l’algorithme
Soit value la valeur recherchée dans une zone délimitée par les indices leftIndex et rightIndex. Il
faut commencer par déterminer l’élément médian, c’est-à-dire celui qui se trouve « au milieu »
de la zone de recherche 2 ; son indice sera déterminé par la formule
medianIndex = (leftIndex + rightIndex) DIV 2
L’algorithme compare alors value avec la valeur de cet élément médian ; il est possible que ce
soit la valeur cherchée ; sinon, il partage la zone de recherche en deux parties : une qui ne
contient certainement pas la valeur cherchée et une qui pourrait la contenir. C’est cette
deuxième partie qui devient la nouvelle zone de recherche. Il adapte leftIndex ou rightIndex en
conséquence. L’algorithme réitère le processus jusqu’à ce que la valeur cherchée soit trouvée ou
que la zone de recherche soit réduite à sa plus simple expression, c’est-à-dire un seul élément.
Exemple de recherche fructueuse
Supposons que l’on recherche la valeur 23 dans un tableau de 20 entiers. La zone ombrée
représente à chaque fois la partie de recherche, qui est au départ le tableau trié dans son
entièreté. Au départ, leftIndex vaut 0 et rightIndex vaut 19.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 3 5 7 7 9 9 10 10 15 16 20 23 23 25 28 28 28 29 29
Première étape : medianIndex = (0 + 19) DIV 2, c’est-à-dire 9.

Comme la valeur en position 9 est 15, la valeur cherchée doit se trouver à sa droite, et on
prend comme nouvelle zone de recherche celle délimitée par leftIndex qui vaut 10 et rightIndex
qui vaut 19.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 3 5 7 7 9 9 10 10 15 16 20 23 23 25 28 28 28 29 29
2. Cet élément médian n’est pas tout à fait au milieu dans le cas d’une zone contenant un nombre pair
d’éléments.
13
1.6. INTRODUCTION À LA COMPLEXITÉ
Deuxième étape : medianIndex = (10 + 19) DIV 2, c’est-à-dire 14.

Comme on y trouve la valeur 25, on garde les éléments situés à la gauche de celui-ci ; la nouvelle
zone de recherche est [10, 13].
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 3 5 7 7 9 9 10 10 15 16 20 23 23 25 28 28 28 29 29
Troisième étape : medianIndex = (10 + 13) DIV 2, c’est-à-dire 11 où se trouve l’élément 20. La
zone de recherche devient leftIndex vaut 12 et rightIndex vaut 13.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 3 5 7 7 9 9 10 10 15 16 20 23 23 25 28 28 28 29 29
Quatrième étape : medianIndex = (12 + 13) DIV 2, c’est-à-dire 12 où se trouve la valeur

cherchée ; la recherche est terminée.
Exemple de recherche infructueuse
Recherchons à présent la valeur 8. Les étapes de la recherche vont donner successivement
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 3 5 7 7 9 9 10 10 15 16 20 23 23 25 28 28 28 29 29
1 3 5 7 7 9 9 10 10 15 16 20 23 23 25 28 28 28 29 29
1 3 5 7 7 9 9 10 10 15 16 20 23 23 25 28 28 28 29 29
1 3 5 7 7 9 9 10 10 15 16 20 23 23 25 28 28 28 29 29
Arrivé à ce stade, la zone de recherche s’est réduite à un seul élément. Ce n’est pas celui
qu’on recherche mais c’est à cet endroit qu’il se serait trouvé ; c’est donc là qu’on pourra
éventuellement l’insérer. Le paramètre de sortie prend la valeur 5.
Algorithme
1 public static int binarySearch(int[] myArray, int value){

2 int leftIndex = 0;
3 int medianIndex = -1;
4 int rightIndex = myArray.length - 1;
5 int candidate;
6 boolean isFound = false;
7
8 while (!isFound && leftIndex <= rightIndex){
9 medianIndex = (leftIndex + rightIndex) / 2;
10 candidate = myArray[medianIndex];
11 if (candidate == value){
12 isFound = true;
13 } else if (value < candidate){
14 rightIndex = medianIndex - 1;
15 } else {
16 leftIndex = medianIndex + 1;
17 }
18 }
19
20 if (isFound){
21 return medianIndex;
22 } else {
23 return -1;
24 }
25 }
1.6 Introduction à la complexité

Un algorithme est idéalement 3 :
correct
il doit résoudre le problème donné, y compris les cas particuliers ;
3. Notons que si l’aspect correct est évidemment primordial, les trois autres sont parfois en concurrence :
il faut quelque fois sacrifier de la mémoire sur l’autel de la rapidité, et les optimisations peuvent conduire à
perdre en lisibilité.
14
lisible
quand on lit l’algorithme, on doit pouvoir se convaincre qu’il est correct ;
optimisé en temps
il doit éviter les instructions inutiles (utilisation du processeur) ;
optimisé en espace
il doit utiliser le moins de mémoire possible (allocations mémoire).
Pour comparer des algorithmes en terme d’utilisation de temps et d’espace, un outil incon-
tournable est la complexité. Cette notion permet de quantifier l’utilisation processeur et/ou
mémoire d’un algorithme donné, aux fins de comparaison avec d’autres algorithmes.
Instructions élémentaires
Dans le cadre de ce cours, nous nous intéressons exclusivement à la complexité temporelle. Une
des façons les plus simples pour quantifier la complexité temporelle est de compter le nombre
d’instructions élémentaires utilisées par un algorithme.
Par exemple si nous reprenons l’algorithme suivant
// Déclare un tableau et donne les 4 premières valeurs.

void remplir4Valeurs()
String[n] vecteur
vecteur[0] = "Un"
vecteur[1] = "Deux"
vecteur[2] = "Trois"
vecteur[3] = "Quatre"
On peut compter 5 instructions élémentaires : une instanciation de tableau, et quatre assigna-

tions dans ce tableau.
Dans l’algorithme suivant
void initialiser(int[n] tab, int valeur)

for i from 0 to n-1
tab[i] = valeur
le nombre d’instructions élémentaires dépend de la taille n du tableau. Il y aura au total n

assignations dans le tableau, mais si nous comptons également les assignations à la variable i
alors on compte précisément 2n assignations.
Par exemple pour n = 2 :
i=0
tab[0] = valeur
i=1
tab[1] = valeur
Dans l’algorithme suivant :
void peutÊtreInitialisé(int[n] tab, int valeur)

if valeur != 0
initialiser(tab, valeur)
le nombre d’instructions élémentaires dépend de la valeur donnée en paramètre. Si la valeur

vaut 0, il y aura une seule instruction (le if ), mais sinon il y en aura 1 + 2n (le if, ainsi que
toutes les instructions liées à l’appel à l’algorithme initialiser).
15
Complexité dans le pire des cas

Nous allons contourner le fait que le nombre d’instructions dépend des paramètres en estimant
un nombre d’instructions « dans le pire des cas 4 ». En d’autres termes, si parfois il y a 1
instruction et parfois il y en a 1 + 2n, alors nous allons considérer que la complexité est de
1 + 2n : c’est le pire des cas.
Grand O
Pour s’affranchir d’un calcul précis du nombre d’instructions, nous allons nous intéresser à la
complexité en « grand O ». Dans ce qui suit, n représente un entier qui estime la taille des
données d’un algorithme. Il s’agit souvent de la taille d’un tableau donné en paramètre, ou
d’un entier donné en paramètre. La signification de la notation « grand O » est la suivante :
. On dit qu’un algorithme (qui dépend a priori d’un entier n) a une complexité en O(1) si le
nombre d’instructions exécutées ne dépend pas de n. On dit qu’il est en temps constant.
. On dit qu’un algorithme (qui dépend a priori d’un entier n) a une complexité en O(n) si
le nombre d’instructions exécutées est toujours inférieur à une quantité proportionnelle
à n. (Notons qu’un algorithme en O(1) est également en O(n).)
. Similairement un algorithme aura une complexité en O(n2 ) si le nombre d’instructions
exécutées est toujours inférieur à une quantité proportionnelle à n2 .
De manière générale, un algorithme a une complexité en O(f (n)) si le nombre d’instructions

exécutées est toujours inférieur à une quantité proportionnelle à f (n).
À titre d’exemples :
. l’algorithme remplir4Valeurs est en temps constant : le nombre d’instructions est toujours
égal à 5, peu importe la taille du tableau.
. l’algorithme initialiser est en O(n) : le nombre d’instructions est égal à 2n.
. l’algorithme peutÊtreInitialisé est également en O(n) (complexité dans le pire des cas).
L’arithmétique des grands O

Une complexité dans le pire des cas d’un algorithme peut être calculée à partir des com-
plexités des constituants de cet algorithme. Voici quelques règles naturelles. Considérons des
algorithmes dépendant d’un paramètre n :
. A1 en O(f (n)),
. A2 en O(g(n)) et
. A3 en O(h(n)).
Concaténation Lorsque l’on réalise l’algorithme A1 suivi de l’algorithme A2 , l’algorithme

résultant est en O(f (n) + g(n)).
Appel de méthode Un appel à une méthode compte pour une instruction, dès lors seule
la complexité de la méthode elle-même rentre en ligne de compte 5 .
Alternative Un algorithme tel que
if A3
A1
else
A2
a une complexité en O(max(g(n), f (n)) + h(n)).

4. Un autre choix commun est de considérer une complexité moyenne, mais ceci amène à faire des calculs
plus difficiles, dont nous n’avons pas besoin dans le cadre de ce cours.
5. Attention toutefois aux méthodes récursives, mais celles-ci seront abordées à la fin de ce cours.
16
Boucle L’algorithme
while A3
A1
a une complexité O(K × (h(n) + f (n))) où K est le nombre de tours de boucle.
Comparons les complexités les plus courantes Pour la recherche dichotomique, la com-
plexité est logarithmique, et on le note O(log2 (n)) ce qui veut dire que si on double la taille
du problème, on a juste une itération en plus dans la boucle.
n 10 100 1000 104 105 106 109
O(1) 1 1 1 1 1 1 1
O(log2 (n)) 4 7 10 14 17 20 30
O(n) 10 100 1000 104 105 106 109
O(n2 ) 100 104 106 108 1010 1012 1018
O(n3 ) 1000 106 109 1012 1015 1018 1027
O(2n ) 1024 1030 10301 103010 1030102 10301029 10301029995
On voit ainsi que si on trouve un algorithme correct pour résoudre un problème mais que cet
algorithme est de complexité exponentielle alors cet algorithme ne sert à rien en pratique. Par
exemple un algorithme de recherche de complexité exponentielle, exécuté sur une machine pou-
vant effectuer un milliard de comparaisons par secondes, prendrait plus de dix mille milliards
d’années pour trouver une valeur dans un tableau de 100 éléments.
1.6.1 Exercices
Exercice 1 Calcul de complexités

Quelle est la complexité d’un algorithme qui :
1. recherche le maximum d’un tableau de n éléments ?
2. remplace par 0 toutes les occurrences du maximum d’un tableau de n éléments ?
3. vérifie si un tableau contient deux éléments égaux ?
4. vérifie si les éléments d’un tableau forment un palindrome ?
5. cherche un élément dans un tableau en essayant des cases au hasard jusqu’à le trouver ?
Exercice 2 Gestion des données

Comparer les algorithmes d’ajout, de recherche et de suppression de valeurs dans le cas d’un
tableau trié et d’un tableau non trié.
Exercice 3 Réflexion
L’algorithme de recherche dichotomique est-il toujours à préférer à l’algorithme de recherche
linéaire ?
17
Chapitre
2 Algorithmes de tris
Dans ce chapitre nous voyons quelques algorithmes simples pour trier un ensemble d’informa-
tions : recherche des maxima, tri par insertion et tri bulle dans un tableau. Des algorithmes
plus efficaces seront vus en deuxième année.
2.1 Motivation
Dans le chapitre précédent, nous avons vu que la recherche d’information est beaucoup plus
rapide dans un tableau trié grâce à l’algorithme de recherche dichotomique. Nous avons vu
comment garder un ensemble trié en insérant toute nouvelle valeur au bon endroit.
Dans certaines situations, nous serons amené à devoir trier toute une collection de valeurs. Par
exemple un tableau.
1. D’abord les situations impliquant le classement total d’un ensemble de données « brutes »,
c’est-à-dire complètement désordonnées.
Prenons pour exemple les feuilles récoltées en vrac à l’issue d’un examen ; il y a peu de
chances que celles-ci soient remises à l’examinateur de manière ordonnée ; celui-ci devra
donc procéder au tri de l’ensemble des copies, par exemple par ordre alphabétique des
noms des étudiants ou des étudiantes, ou par numéro de groupe, etc.
2. Enfin, les situations qui consistent à devoir retrier des données préalablement ordonnées
sur un autre critère.
Prenons l’exemple d’un paquet de copies d’examen déjà triées sur l’ordre alphabétique
des noms des étudiants et des étudiantes, et qu’il faut retrier cette fois-ci sur les numéros
de groupe. Il est clair qu’une méthode efficace veillera à conserver l’ordre alphabétique
déjà présent dans la première situation afin que les copies apparaissent dans cet ordre
dans chacun des groupes.
Le dernier cas illustre un classement sur une clé complexe (ou composée) impliquant la
comparaison de plusieurs champs d’une même structure : le premier classement se fait sur le
numéro de groupe, et à numéro de groupe égal, l’ordre se départage sur le nom de la personne.
Nous dirons de cet ensemble qu’il est classé en majeur sur le numéro de groupe et en mineur
sur le nom d’étudiant.
Notons que certains tris sont dits stables parce qu’en cas de tri sur une nouvelle clé, l’ordre de
la clé précédente est préservé pour des valeurs identiques de la nouvelle clé, ce qui évite de faire
des comparaisons sur les deux champs à la fois. Les méthodes nommées tri par insertion,
tri bulle et tri par recherche de minima successifs (que nous allons aborder dans ce
chapitre) sont stables.
Certains tris sont évidemment plus performants que d’autres. Le choix d’un tri particulier
dépend de la taille de l’ensemble à trier et de la manière dont il se présente, c’est-à-dire déjà
plus ou moins ordonné. La performance quant à elle se juge sur deux critères :
. le nombre de tests effectués (comparaisons de valeurs) et ;
. le nombre de transferts de valeurs réalisés.
19
2.1. MOTIVATION
Les algorithmes classiques de tri présentés dans ce chapitre le sont surtout à titre pédagogique.
Ils ont tous une « complexité en n2 » (on dit qu’ils sont « en O(n2 ) »), ce qui veut dire que si n
est le nombre d’éléments à trier, le nombre d’opérations élémentaires (tests et transferts de va-
leurs) est proportionnel à n2 . Ils conviennent donc pour des ensembles de taille « raisonnable »,
mais peuvent devenir extrêmement lents à l’exécution pour le tri de grands ensembles, comme
par exemple les données de l’annuaire téléphonique. Plusieurs solutions existent, comme la
méthode de tri Quicksort. Cet algorithme très efficace faisant appel à la récursivité et qui
sera étudié en bloc deux (Q3) a une complexité en O(n log(n)) en général et dans de rares cas
en O(n2 ).
Dans ce chapitre, les algorithmes traiteront du tri dans un tableau d’entiers à une dimen-
sion. Toute autre situation peut bien entendu se ramener à celle-ci moyennant la définition de
la relation d’ordre propre au type de données utilisé. Ce sera par exemple l’ordre alphabétique
pour les chaines de caractères, l’ordre chronologique pour des objets Date ou Moment (que nous
verrons plus tard), etc. De plus, le seul ordre envisagé sera l’ordre croissant des données. Plus
loin, nous envisagerons le tri d’autres structures de données.
Enfin, dans toutes les méthodes de tri abordées, nous supposerons la taille physique du tableau
à trier égale à sa taille logique, celle-ci n’étant pas modifiée par l’action de tri. Nous supposons
trier tout le tableau.
20
2.2. TRI PAR INSERTION
2.2 Tri par insertion

Cette méthode de tri repose sur le principe d’insertion de valeurs dans un tableau ordonné.
Description de l’algorithme. Le tableau à trier sera à chaque étape subdivisé en deux

sous-tableaux : le premier cadré à gauche contiendra des éléments déjà ordonnés, et le second,
cadré à droite, ceux qu’il reste à insérer dans le sous-tableau trié. Celui-ci verra sa taille
s’accroitre au fur et à mesure des insertions, tandis que celle du sous-tableau des éléments non
triés diminuera progressivement.
Au départ de l’algorithme, le sous-tableau trié est le premier élément du tableau. Comme il
ne possède qu’un seul élément, ce sous-tableau est donc bien ordonné ! Chaque étape consiste
ensuite à prendre le premier élément du sous-tableau non trié et à l’insérer à la bonne place
dans le sous-tableau trié.
Prenons comme exemple un tableau tab de 20 entiers. Au départ, le sous-tableau trié est formé
du premier élément, tab[0], qui vaut 20 :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
20 12 18 17 15 14 15 16 18 17 12 14 16 18 15 15 19 11 11 13
L’étape suivante consiste à insérer tab[1], qui vaut 12, dans ce sous-tableau de taille 2 :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
12 20 18 17 15 14 15 16 18 17 12 14 16 18 15 15 19 11 11 13
Ensuite, c’est au tour de tab[2], qui vaut 18, d’être inséré :

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
12 18 20 17 15 14 15 16 18 17 12 14 16 18 15 15 19 11 11 13
Et ainsi de suite jusqu’à insertion du dernier élément dans le sous-tableau trié.
Algorithme. L’algorithme combine la recherche de la position d’insertion et le décalage

concomitant de valeurs.
algorithme insertionSort(myArray )
pour i de 1 à taille(myArray) -1
mémoriser myArray[i] dans value
décaler les éléments myArray[0]..myArray[i-1] qui sont plus grands que value,
en partant de myArray[i-1]
placer value dans le "trou" laissé par le décalage
langage naturel
1 /∗∗
2 ∗ Tri par insertion.
3 ∗
4 ∗ @param myArray tableau à trier
5 ∗/
6 public static void insertionSort(int[] myArray) {
7 for (int i = 1; i < myArray.length; i++) {
8 int value = myArray[i];
9 int pos = i - 1;
10 while (pos >= 0 && value < myArray[pos]) {
11 myArray[pos + 1] = myArray[pos];
12 pos = pos - 1;
13 }
14 myArray[pos + 1] = value;
15 }
16 }
21
2.3. TRI PAR SÉLECTION DES MINIMA SUCCESSIFS
2.3 Tri par sélection des minima successifs

Dans ce tri, l’algorithme recherche à chaque étape la plus petite valeur de l’ensemble non
encore trié et la place immédiatement à sa position définitive.
Description de l’algorithme. Prenons par exemple un tableau de 20 entiers.

La première étape consiste à rechercher la valeur minimale du tableau. Il s’agit de l’élément
d’indice 9 et de valeur 17.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
20 52 61 47 82 64 95 66 84 17 32 24 46 48 75 55 19 61 21 30
Celui-ci devrait donc apparaitre en 1re position du tableau. Or cette position est occupée par
la valeur 20. Comment procéder dès lors pour ne perdre aucune valeur et sans faire appel à
un second tableau ? La solution est simple, il suffit d’échanger le contenu des deux éléments
d’indices 0 et 9 :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
17 52 61 47 82 64 95 66 84 20 32 24 46 48 75 55 19 61 21 30
Le tableau se subdivise à présent en deux sous-tableaux, un sous-tableau déjà trié (pour le

moment réduit au seul élément tab[0]) et le sous-tableau des autres valeurs non encore triées
(de l’indice 1 à 19). On recommence ce processus dans ce second sous-tableau : le minimum est
à présent l’élément d’indice 16 et de valeur 19. Celui-ci viendra donc en 2e position, échangeant
sa place avec la valeur 52 qui s’y trouvait :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
17 19 61 47 82 64 95 66 84 20 32 24 46 48 75 55 52 61 21 30
Le sous-tableau trié est maintenant formé des deux premiers éléments, et le sous-tableau non
trié par les 18 éléments suivants.
Et ainsi de suite, jusqu’à obtenir un sous-tableau trié comprenant tout le tableau. En pratique
l’arrêt se fait une étape avant car lorsque le sous-tableau non trié n’est plus que de taille 1, il
contient nécessairement le maximum de l’ensemble.
algorithme selectionSort(myArray )
pour i de 0 à taille(myArray) -2
rechercher la position du minimum de myArray[i] à la fin du tableau
échanger les valeurs myArray[i] et le minimum trouvé
langage naturel
22
2.4. TRI BULLE
1 /∗∗
2 ∗ Trie le tableau reçu en paramètre via un tri par sélection
3 ∗ des minima successifs
4 ∗
5 ∗ @param myArray le tableau à trier
6 ∗/
7 public static void selectionSort(int[] myArray) {
8 for (int i = 0; i < myArray.length - 1; i++) {
9 int minIndex = searchMinIndex(myArray, i, myArray.length - 1);
10 if (minIndex != i) {
11 swap(myArray, i, minIndex);
12 }
13 }
14 }
15
16 /∗∗
17 ∗ Retourne l'indice du minimum entre les indices début et fin
18 ∗ du tableau reçu.
19 ∗
20 ∗ En cas d'égalité, c'est l'indice le plus petit qui est retourné.
21 ∗
22 ∗ @param myArray le tableau d'entiers
23 ∗ @param begin l'indice de début
24 ∗ @param end l'indice de fin
25 ∗/
26 public static int searchMinIndex(int[] myArray, int begin, int end) {
27 int minIndex = begin;
28 for (int i = begin + 1; i <= end; i++) {
29 if (myArray[i] < myArray[minIndex]) {
30 minIndex = i;
31 }
32 }
33 return minIndex;
34 }
35
36 /∗∗
37 ∗ Échange deux valeurs dans un tableau
38 ∗
39 ∗ @param myArray un tableau
40 ∗ @param pos1 une position
41 ∗ @param pos2 une (autre) position
42 ∗/
43 private static void swap(int[] myArray, int pos1, int pos2) {
44 int value = myArray[pos1];
45 myArray[pos1] = myArray[pos2];
46 myArray[pos2] = value;
47 }
2.4 Tri bulle

Il s’agit d’un tri par permutations ayant pour but d’amener à chaque étape à la « surface » du
sous-tableau non trié (on entend par là l’élément d’indice minimum) la valeur la plus petite,
appelée la bulle. La caractéristique de cette méthode est que les comparaisons ne se font
qu’entre éléments consécutifs du tableau.
Description de l’algorithme Prenons pour exemple un tableau de taille 14. En partant

de la fin du tableau, on le parcourt vers la gauche en comparant chaque couple de valeurs
consécutives. Quand deux valeurs sont dans le désordre, on les permute. Le premier parcours
s’achève lorsqu’on arrive à l’élément d’indice 0 qui contient alors la « bulle », c’est-à-dire la
plus petite valeur du tableau, soit 1 dans l’exemple :
0 1 2 3 4 5 6 7 8 9 10 11 12 13
10 5 12 15 4 8 1 7 12 11 3 6 5 4
10 5 12 15 4 8 1 7 12 11 3 6 4 5
10 5 12 15 4 8 1 7 12 11 3 4 6 5
10 5 12 15 4 8 1 7 12 11 3 4 6 5
10 5 12 15 4 8 1 7 12 3 11 4 6 5
10 5 12 15 4 8 1 7 3 12 11 4 6 5
10 5 12 15 4 8 1 3 7 12 11 4 6 5
10 5 12 15 4 8 1 3 7 12 11 4 6 5
23
2.5. CAS PARTICULIERS
10 5 12 15 4 1 8 3 7 12 11 4 6 5
10 5 12 15 1 4 8 3 7 12 11 4 6 5
10 5 12 1 15 4 8 3 7 12 11 4 6 5
10 5 1 12 15 4 8 3 7 12 11 4 6 5
10 1 5 12 15 4 8 3 7 12 11 4 6 5
1 10 5 12 15 4 8 3 7 12 11 4 6 5
Ceci achève le premier parcours. On recommence à présent le même processus dans le sous-
tableau débutant au deuxième élément, ce qui donnera le contenu suivant :
1 3 10 5 12 15 4 8 4 7 12 11 5 6
Et ainsi de suite. Au total, il y aura n − 1 étapes.
algorithme bubbleSort(myArray )
pour i de de 0 à taille(myArray)-2
pour j de taille(myArray)-1 à i
si myArray[j] < myArray[j-1]
échanger les valeurs myArray[j] et myArray[j-1]
langage naturel
Algorithme.
1 /∗∗
2 ∗ Tri bulle d'un tableau d'entiers.
3 ∗
4 ∗ @param myArray
5 ∗/
6 public static void bubbleSort(int[] myArray) {
7 // La bulle part de la droite,
8 // en faisant remonter l'élément le plus petit,
9 // et éclate à gauche.
10 for (int burstPos = 0; burstPos < myArray.length - 1; burstPos++) {
11 for (int bubblePos = myArray.length - 1; bubblePos > burstPos; bubblePos--) {
12 if (myArray[bubblePos] < myArray[bubblePos - 1]) {
13 swap(myArray, bubblePos, bubblePos - 1);
14 }
15 }
16 }
17 }
18
19 /∗∗
20 ∗ Échange deux valeurs dans un tableau
21 ∗
22 ∗ @param myArray un tableau
23 ∗ @param pos1 une position
24 ∗ @param pos2 une (autre) position
25 ∗/
26 private static void swap(int[] myArray, int pos1, int pos2) {
27 int value = myArray[pos1];
28 myArray[pos1] = myArray[pos2];
29 myArray[pos2] = value;
30 }
2.5 Cas particuliers

Tri partiel
Parfois, un tri complet de l’ensemble n’est pas utile au problème. Il n’est nécessaire de n’avoir
que les « k » plus petites (ou plus grandes) valeurs. Le tri par recherche des minima et le
tri bulle sont particulièrement adaptés à cette situation ; il suffit de les arrêter plus tôt. Par
contre, le tri par insertion est inefficace car il ne permet pas un arrêt anticipé.
Sélection des meilleurs
24
2.6. RÉFÉRENCES
Une autre situation courante est la suivante : un ensemble de valeurs sont traitées (lues,
calculées. . .) et il ne faut garder que les k plus petites (ou plus grandes).
L’algorithme est plus simple à écrire si on utilise une position supplémentaire en fin de tableau.
Notons aussi qu’il faut tenir compte du cas où il y a moins de valeurs que le nombre de valeurs
voulues ; c’est pourquoi on ajoute une variable indiquant le nombre exact de valeurs dans le
tableau.
Exemple : on lit un ensemble de valeurs strictement positives (un 0 indique la fin de la lecture)
et on ne garde que les k plus petites valeurs.

public static int bests(int[] smallers){
Scanner keyboard = new Scanner(System.in);
int val;
nbValues = 0;
val = keyboard.nextInt();
while (val >= 0){
nbValues = insert(val, smallers, nbValues);
val = keyboard.nextInt();
}
}
public static int insert(int val, int[] smallers, nbValues){

int i = nbValues - 1;
while ( i >= 0 && val < smallers[i]){
smallers[i+1] = smallers[i];
i = i - 1;
}
smallers[i+1] = val;
if (nbValues < smallers.length){
nbValues++;
}
return nbValues;
}

2.6 Références
. http://interstices.info/jcms/c_6973/les-algorithmes-de-tri
Ce site trivisuels permet de visualiser les méthodes de tris en fonctionnement. Il présente
tous les tris vus en bloc 1 plus quelques autres comme le « tri rapide » (« quicksort »)
que vous verrez en bloc 2.
25
Chapitre
3 Les tableaux à 2 dimensions
3.1 Définition
La dimension d’un tableau est le nombre d’indices qu’on utilise pour faire référence à un de
ses éléments.
Attention
Ne pas confondre la dimension avec la taille !
En dev1 , nous avons introduit les tableaux à une dimension. Un seul indice suffisait à localiser
un de ses éléments. Pour le dire autrement, chaque case possédait un numéro. De nombreuses
situations nécessitent cependant l’usage de tableaux à deux dimensions. Ils vous sont déjà fami-
liers par leur présence dans beaucoup de situations courantes : calendrier, grille horaire, grille
de mots croisés, sudoku, jeux se déroulant sur un quadrillage (damier, échiquier, scrabble. . .).
Dans ces situations, chaque case est désignée par deux numéros.
3.2 Notations
3.2.1 Déclarer
Pour déclarer un tableau à 2 dimensions, on écrira :
TypeElément[nbLignes × nbColonnes] nomTableau
ou en Java :

TypeElément[][] nomTableau = new TypeElément[nbLignes][nbColonnes];

où nbLignes et nbColonnes sont des expressions entières quelconques.
Exemple :
int[5×10] tab
ou en Java :

int[][] tab = new int[5][10];

déclare un tableau de 5 lignes par 10 colonnes dont chaque case contient un entier.
27
3.2. NOTATIONS
3.2.2 Utiliser
Pour accéder à une case du tableau on donnera les deux indices entre crochets. On considère
que la première ligne et la première colonne portent le numéro (l’indice) 0.
Exemple :
print tab[2,4] // affiche le 5e élément de la 3e ligne du tableau nommé tab.
et en Java :

System.out.println(tab[2][4]);

3.2.3 Visualiser
Notez que la vue sous forme de tableau avec des lignes et des colonnes est une vision humaine.
Il n’y a pas de lignes ni de colonnes en mémoire.
Exemple : Soit le tableau déclaré ainsi :
int[4×5] nombres
On peut le visualiser à l’aide d’une grille à 4 lignes et 5 colonnes.

0 1 2 3 4
0 0 1 2 3 4
1 10 11 12 13 14
2 20 21 22 23 24
3 30 31 32 33 34
Ainsi, la valeur de nombres[2,3] est 23.
Mais on pourrait considérer que le 1er indice désigne la colonne et le second indice la ligne. On
le visualiserait alors ainsi :
0 1 2 3
0 0 10 20 30
1 1 11 21 31
2 2 12 22 32
3 3 13 23 33
4 4 14 24 34
Cela ne change pas le fait que la valeur de nombres[2,3] est toujours 23.
On pourrait aussi visualiser un tableau à deux dimensions comme un tableau à une dimension
dont chacun des éléments est lui-même un tableau à une dimension. La vision « tableau de
tableaux » (ou décomposition en niveaux) donnerait :
0 1 2 3
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
0 1 2 3 4 10 11 12 13 14 20 21 22 23 24 30 31 32 33 34
Dans cette représentation, le tableau nombres est d’abord décomposé à un premier niveau en
quatre éléments auxquels on accède par le premier indice. Ensuite, chaque élément de premier
niveau est décomposé en cinq éléments de deuxième niveau accessibles par le deuxième indice.
Convention
Pour être précis, on devrait juste parler de première dimension et de deuxième dimension
mais la notion de ligne et de colonne est un abus de langage qui simplifie le discours.
28
3.2. NOTATIONS
3.2.4 Exemples
Exemple 1 – Remplir les coins. Dans ce petit exemple, on a un tableau de chaines et on
donne des valeurs aux coins.
"NO" "NE"
"SO" "SE"
// Déclare un tableau et donne des valeurs aux coins.

void remplirCoins()
String[3×5] grille
grille[0,0] = "NO"
grille[0,4] = "NE"
grille[2,0] = "SO"
grille[2,4] = "SE"
La version Java :
1 public static void remplirCoins() {

2 String[][] grille = new String[3][5];
3 grille[0][0] = "NO";
4 grille[0][4] = "NE";
5 grille[2][0] = "SO";
6 grille[2][4] = "SE";
7 } // Pour afficher : System.out.println(Arrays.deepToString(grille));
Syntaxe Java
On vous renvoie à votre cours de Java pour les précisions sur la syntaxe Java.
Notez juste ici :
. Comment est déclaré/créé le tableau.
. Le double [] pour accéder à un élément.
Exemple 2 – Gestion des stocks. Prenons l’exemple d’un stock de 10 produits pour
chaque jour de la semaine.
article0 article1 article2 ... article7 article8 article9
lundi cpt[0,0] cpt[0,1] cpt[0,2] ... cpt[0,7] cpt[0,8] cpt[0,9]
mardi cpt[1,0] cpt[1,1] cpt[1,2] ... cpt[1,7] cpt[1,8] cpt[1,9]
mercredi cpt[2,0] cpt[2,1] cpt[2,2] ... cpt[2,7] cpt[2,8] cpt[2,9]
jeudi cpt[3,0] cpt[3,1] cpt[3,2] ... cpt[3,7] cpt[3,8] cpt[3,9]
vendredi cpt[4,0] cpt[4,1] cpt[4,2] ... cpt[4,7] cpt[4,8] cpt[4,9]
samedi cpt[5,0] cpt[5,1] cpt[5,2] ... cpt[5,7] cpt[5,8] cpt[5,9]
dimanche cpt[6,0] cpt[6,1] cpt[6,2] ... cpt[6,7] cpt[6,8] cpt[6,9]
// Calcule et affiche la quantité vendue de 10 produits

// pour chaque jour de la semaine (de 0 : lundi à 6 : dimanche).
void statistiquesVentesSemaine()
int[7×10] cpt
initialiser(cpt, 0)
for jour from 0 to 6 // Pour chaque jour de la semaine
print "jour : ", jour
traiterStock1Jour(cpt, jour)
for produit from 0 to 9
print "quantité vendue de produit ", produit, " ce jour ", jour, " : ", cpt[jour,produit]
29
3.2. NOTATIONS
void initialiser(int[n×m] tab, int valeur)

for i from 0 to n-1
for j from 0 to m-1
tab[i,j] = valeur
// Effectue le traitement du stock pour une journée.

void traiterStock1Jour(int[n×m] cpt, int jour)
int numéroProduit, quantité
read numéroProduit
while numéroProduit ≥ 0 et numéroProduit < m
read quantité
cpt[jour,numéroProduit] = cpt[jour,numéroProduit] + quantité
read numéroProduit
En Java :
1 public static void statistiquesVentesSemaine() {

2 int[][] cpt = new int[7][10];
3 // initialiser(cpt, 0); // rien à faire : en Java, les tableaux d'entiers sont initialisés à 0.
4 for (int jour = 0; jour < 7; jour++) {
5 System.out.println("Jour : " + jour);
6 traiterStock1Jour(cpt, jour);
7 for (int produit = 0; produit < 10; produit++) {
8 System.out.println("quantité vendue du produit " + produit
9 + " ce jour " + jour + " : " + cpt[jour][produit]);
10 }
11 }
12 }
1 private static void traiterStock1Jour(int[][] cpt, int jour) {

2 int numéroProduit, quantité;
3 // askInt est une méthode utilitaire pour lire un entier de façon conviviale et robuste
4 numéroProduit = askInt("Introduisez le numéro du produit");
5 while (numéroProduit >= 0 && numéroProduit < 10) {
6 quantité = askInt("Introduisez la quantité vendue");
7 cpt[jour][numéroProduit] += quantité;
8 numéroProduit = askInt("Introduisez le numéro du produit");
9 }
10 }
11 public static void main(String[] args) {
12 statistiquesVentesSemaine();
13 }
14
3.2.5 Complexité
Regardons un peu la complexité avec les tableaux 2D.
Dans l’algorithme suivant
void initialiser(int[n×m] tab, int valeur)

for i from 0 to n-1
for j from 0 to m-1
tab[i,j] = valeur
le nombre d’instructions élémentaires dépend de la taille n × m du tableau. Il y aura au total

n ∗ m assignations dans le tableau, mais si nous comptons également les assignations aux
variable i et j alors on compte précisément n + 2mn assignations.
Il est en O(nm).
30
3.3. PARCOURS
3.2.6 Exercices
Ces exercices ne nécessitent pas encore de parcours du tableau (pas de boucle). Nous verrons
les algorithmes de parcours juste après.
Pour chaque exercice, donnez la complexité « grand O » de votre solution.
Exercice 1 Case nulle ?

Écrire un algorithme qui reçoit un tableau d’entiers (à n lignes et m colonnes) ainsi que les
coordonnées d’une case (ligne, colonne) et qui retourne un booléen indiquant si la case désignée
contient ou pas la valeur nulle.
boolean estNul(int[n × m] tab, int lg, col)
Exercice 2 Case existe ?

Écrire un algorithme qui reçoit un tableau d’entiers (à n lignes et m colonnes) ainsi que des
coordonnées et qui retourne un booléen indiquant si ces coordonnées désignent bien une case
du tableau, c’est-à-dire qu’elles sont dans le bon intervalle (0 à n − 1 et 0 à m − 1).
boolean existe(int[n × m] tab, int lg, col)
Exercice 3 Assigner une case

coordonnées d’une case (ligne, colonne) et une valeur entière. L’algorithme met la valeur donnée
dans la case indiquée pour autant que la case contienne actuellement la valeur nulle. Dans le
cas contraire, l’algorithme ne fait rien.
void assigner(int[n × m] tab, int lg, col, val)
Exercice 4 Un bord du tableau

coordonnées d’une case (ligne, colonne). L’algorithme doit indiquer si la case donnée est ou
non sur un bord du tableau.
boolean estBord(int[n × m] tab, int lg, col)
Exercice 5 Un coin du tableau

coordonnées d’une case (ligne, colonne). L’algorithme doit indiquer si la case donnée est ou
non sur un des 4 coins du tableau.
boolean estCoin(int[n × m] tab, int lg, col)
3.3 Parcours
Comme nous l’avons fait pour les tableaux à une dimension, envisageons le parcours des
tableaux à deux dimensions (n lignes et m colonnes). Nos algorithmes sont valables quel que
soit le type des éléments. Utilisons un type T 1 , pour désigner un type quelconque.
T[n × m] tab
1. Nos versions Java seront écrites avec des tableau d’entiers. Il est possible de les écrire avec un type
générique T mais ça requiert des notions avancées de Java.
31
3.3. PARCOURS
Commençons par des cas plus simples où on ne parcourt qu’une seule des dimensions puis
attaquons le cas général.
3.3.1 Parcours d’une dimension

Certains parcours ne visitent qu’une partie du tableau et ne nécessitent qu’une seule boucle.
Examinons quelques cas.
Une ligne. On peut vouloir ne parcourir qu’une seule ligne du tableau. Si on parcourt la
ligne l, on visite les cases (l, 0), (l, 1), . . ., (l, m − 1). L’indice de ligne est constant et c’est
l’indice de colonne qui varie.
l 1 2 3 4 5
Ce qui donne l’algorithme :
pour chaque colonne et en commençant par la première

afficher l’élément à cette colonne tout en restant sur la ligne l
langage naturel
// Parcours de la ligne lg d’un tableau à deux dimensions

void afficherLigne(T[n × m] tab, int lg)
for col from 0 to m-1
print tab[ lg, col ] // On peut faire autre chose qu’afficher
1 public static void afficherLigne(int[][] tab, int lg) {

2 for (int col = 0; col < tab[lg].length; col++) {
3 System.out.println(tab[lg][col]);
4 }
5 }
Retenons
Pour parcourir une ligne, on utilise une boucle sur les colonnes.
La complexité d’un tel algorithme est O(m), où m est le nombre de colonnes.
Une colonne. Symétriquement, on pourrait considérer le parcours d’une colonne avec l’al-
gorithme suivant.
// Parcours de la colonne col d’un tableau à deux dimensions

void afficherColonne(T[n × m] tab, int col)
for lg from 0 to n-1
print tab[ lg, col ] // On peut faire autre chose qu’afficher
1 public static void afficherColonne(int[][] tab, int col) {

2 for (int lg = 0; lg < tab.length; lg++) {
4 }
5 }
La complexité d’un tel algorithme est O(n), où n est le nombre de lignes.
La diagonale descendante. Si le tableau est carré (n = m) on peut aussi envisager le

parcours des deux diagonales.
Pour la diagonale descendante, parfois appelée diagonale principale, les éléments à visiter sont
en coordonnées (0, 0), (1, 1), (2, 2), . . ., (n − 1, n − 1).
32
3.3. PARCOURS
1
2
3
Une seule boucle suffit comme le montre l’algorithme suivant.
// Parcours de la diagonale descendante d’un tableau carré

void afficherDiagonaleDescendante(T[n × n] tab)
for i from 0 to n-1
print tab[i,i] // On peut faire autre chose qu’afficher
1 public static void afficherDiagonaleDescendante(int[][] tab) {

2 for (int i = 0; i < tab.length; i++) {
3 System.out.println(tab[i][i]);
4 }
5 }
La diagonale montante. Pour la diagonale montante 2 d’un tableau carré (n = m), repré-
sentée ci-dessous, on peut envisager deux solutions :
. avec deux indices, ou
. avec un seul indice, en se basant sur le fait que
lg + col = n − 1 ⇒ lg = n − 1 − col.
3
2
1
// Parcours de la diagonale montante d’un tableau carré - version 2 indices

// lg part du début et augmente / col part de la fin et diminue
void afficherDiagonaleMontante(T[n × n] tab)
int col
lg = n-1
for col from 0 to n-1
print tab[lg, col] // On peut faire autre chose qu’afficher
lg = lg - 1
// Parcours de la diagonale montante d’un tableau carré - version 1 indice

void afficherDiagonaleMontante(T[n × n] tab)
for col from 0 to n-1
print tab[n-1-col, col] // On peut faire autre chose qu’afficher
Ces deux algorithmes ont une complexité égale à O(n).
1 // Version avec deux variables

2 public static void afficherDiagonaleMontanteV1(int[][] tab) {
3 int lg = tab.length - 1;
4 for (int col = 0; col < tab[0].length; col++) {
6 lg--;
7 }
8 }
1 // En Java, on peut placer les 2 variables dans le for

3 for (int col = 0, lg = tab.length - 1; col < tab[0].length; lg--, col++) {
5 }
6 }
2. On l’appelle montante car elle semble monter, si on la parcourt de gauche à droite. On l’appellera encore
montante même si on la parcourt de droite à gauche.
33
3.3. PARCOURS
1 // Version avec la colonne calculée à partir de la ligne

4 int n = tab.length;
5 System.out.println(tab[n - 1 - col][col]);
6 }
7 }
34
3.3. PARCOURS
3.3.2 Parcours des deux dimensions

Les parcours précédents ne concernaient qu’une partie du tableau. Voyons à présent comment
visiter toutes les cases du tableau.
Parcours par lignes et par colonnes. Les deux parcours les plus courants sont les parcours
« ligne par ligne » et « colonne par colonne ». Les tableaux suivants montrent dans quel ordre
chaque case est visitée dans ces deux parcours.
Parcours ligne par ligne Parcours colonne par colonne
1 2 3 4 5 1 4 7 10 13
6 7 8 9 10 2 5 8 11 14
11 12 13 14 15 3 6 9 12 15
Le plus simple est d’utiliser deux boucles imbriquées
// Parcours d’un tableau à 2 dimensions, ligne par ligne

void afficherLigneParLigne(T[n × m] tab)
print tab[lg,col] // On peut faire autre chose qu’afficher
Il suffit d’inverser les deux boucles pour effectuer un parcours par colonne.
// Parcours d’un tableau à 2 dimensions, colonne par colonne

void afficherColonneParColonne(T[n × m] tab)
Ces deux algorithmes ont une complexité O(nm).
1 public static void afficherLigneParLigne(int[][] tab) {

4 System.out.print(tab[lg][col]+" ");
5 }
6 System.out.println();
7 }
8 }
1 public static void afficherColonneParColonne(int[][] tab) {

5 }
7 }
8 }
Mais on peut obtenir le même résultat avec une seule boucle si l’indice sert juste à compter le
nombre de passages (n ∗ m) et que les indices de lignes et de colonnes sont gérés manuellement.
L’algorithme suivant montre ce que ça donne pour un parcours ligne par ligne. La solution
pour un parcours colonne par colonne est similaire et laissée en exercice.
35
3.3. PARCOURS
algorithme afficherLigneParLigne(tab[n x m])

On commence à la 1re case, en haut à gauche.
Répéter n*m fois
afficher tab[lg,col]
si on n’est pas sur le bord droit
Passer sur la case de droite
sinon
Passer à la case de gauche de la ligne suivante
langage naturel
En plus détaillé :
// Parcours d’un tableau à 2 dimensions via une seule boucle

void afficherLigneParLigne(T[n × m] tab)
int lg, col
lg = 0
col = 0
for i from 1 to n*m
col = col + 1 // Passer à la case suivante
if col == m // On déborde sur la droite, passer à la ligne suivante
col = 0
lg = lg + 1
Cet algorithme a également une complexité O(nm).

Et en Java :
1 public static void afficherLigneParLigneV2(int[][] tab) {

2 int nbÉléments = tab.length ∗ tab[0].length;
3 int lg = 0;
4 int col = 0;
5 for (int i = 0; i < nbÉléments; i++) {
7 col++;
8 if (col == tab[0].length) {
9 col = 0;
10 lg++;
12
13 }
14 }
15 }
L’avantage de cette solution apparaitra quand on verra des situations plus difficiles.
36
3.3. PARCOURS
3.3.3 Interrompre le parcours.

Comme avec les tableaux à une dimension, envisageons l’arrêt prématuré lors de la rencontre
d’une certaine condition.
Adaptons la version du parcours à une boucle (nous pourrions également adapter la version à
deux boucles, mais cela conduit à plus de code à écrire).
Version avec 1 boucle. Illustrons-le au travers d’un algorithme qui cherche un élément
particulier et retourne un booléen indiquant si l’élément a été trouvé ou pas.
boolean chercherElément(T[n × m] tab, T élt)

int lg, col, i
lg = 0
col = 0
i=1
while i ≤ n*m ET tab[lg, col] 6= élt
col = col + 1 // Passer à la case suivante
if col == m // On déborde sur la droite, passer à la ligne suivante
col = 0
lg = lg + 1
i=i+1
return i ≤ n ∗ m
Remarquez qu’ici, naturellement, la ligne et la colonne s’arrêtent exactement à l’endroit où la

valeur est trouvée.
En Java, ça donne :
1 public static boolean chercherLigneParLigneV2(int[][] tab, int élt) {

3 int lg = 0;
4 int col = 0;
5 int i = 1;
6 while (i <= nbÉléments && tab[lg][col] != élt) {
7 col++;
8 if (col == tab[0].length) {
9 col = 0;
10 lg++;
11 }
12 i++;
13 }
14 return i <= nbÉléments;
15 }
37
3.3. PARCOURS
3.3.4 Parcours plus compliqués

Le serpent. Envisageons un parcours plus difficile où on inverse le sens du parcours d’une
ligne à l’autre comme illustré par le tableau suivant.
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
Le plus simple est d’adapter l’algorithme de parcours avec une seule boucle en introduisant un
sens de déplacement, ce qui donne l’algorithme :
algorithme afficherElémentsSerpent(tab[n x m])

Se placer sur la 1re case
Commencer à se déplacer à droite
Répéter n*m fois
afficher tab[lg,col]
si le déplacement dans le sens courant (droite/gauche) ne sort pas de tab
Se déplacer dans le sens courant
sinon
Passer à la ligne suivante
Inverser le sens de déplacement (droite ⇐⇒ gauche)
langage naturel
Pour retenir le sens du déplacement, nous allons utiliser un entier (−1 pour gauche et 1 pour
droite) ce qui va faciliter le calcul du déplacement.
// Parcours du serpent dans un tableau à deux dimensions

void afficherElémentsSerpent(T[n × m] tab)
int lg, col, depl
lg = 0 ; col = 0 ; sens = 1 // 1 pour avancer, -1 pour reculer
for i from 1 to n*m
print tab[lg, col] // On peut faire autre chose qu’afficher
if 0 ≤ col + sens ET col + sens < m
col = col + sens // On se déplace dans la ligne
else
lg = lg + 1 // On passe à la ligne suivante
sens = -sens // et on change de sens
Cet algorithme a également une complexité O(nm).

Voici la version Java :
1 public static void parcoursSerpent(int[][] tab) {

3 int lg = 0;
4 int col = 0;
5 int sens = 1;
6 for (int i = 0; i < nbÉléments; i++) {
8 if (0 <= col + sens && col + sens < tab[0].length) {
9 col += sens;
10 } else {
11 lg++;
12 sens = -sens;
13 }
14 }
15 System.out.print()
16 }
38
3.4. EXERCICES
3.4 Exercices
Pour chaque exercice, donnez la complexité « grand O » de votre solution.
Exercice 6 Affichage
Écrire un algorithme qui affiche tous les éléments d’un tableau (à n lignes et m colonnes) ligne
par ligne.
Écrivez un autre algorithme qui affiche cette fois les éléments colonne par colonne
Exercice 7 Cases adjacentes

coordonnées d’une case (ligne, colonne) et affiche les coordonnées des cases adjacentes.
Exercice 8 Les nuls

Écrire un algorithme qui reçoit un tableau (n x m) d’entiers et qui retourne la proportion
d’éléments nuls dans ce tableau.
Exercice 9 Le tableau de cotes

Soit un tableau à n lignes et m colonnes d’entiers où une ligne représente les notes sur 20 d’un
étudiant et les colonnes toutes les notes d’un cours.
Écrire un algorithme recevant ce tableau en paramètre et retournant le pourcentage d’étudiants
ayant obtenu une moyenne supérieure à 50%.
Exercice 10 Le triangle de Pascal

Le triangle de Pascal est construit de la façon suivante :
. la ligne initiale contient un seul élément de valeur 1 ;
. chaque ligne possède un élément de plus que la précédente ;
. chaque ligne commence et se termine par 1 ;
. pour calculer un nombre d’une autre case du tableau, on additionne le nombre situé dans
la case située juste au-dessus avec celui dans la case à la gauche de la précédente.
Écrire un algorithme qui reçoit en paramètre un entier n, et
qui renvoie un tableau contenant les n + 1 premières lignes 1
du triangle de Pascal (indicées de 0 à n). 1 1
1 2 1
N.B. : le « triangle » sera renvoyé dans un tableau 2D 1 3 3 1
(carré) dont certaines cases ne seront pas initialisées. En 1 4 6 4 1
Java, on peut créer des tableaux non-carrés. 1 5 10 10 5 1
Par exemple, pour n qui vaut 5, on aura le tableau ci-contre.
Exercice 11 Tous positifs

Écrire un algorithme qui reçoit un tableau (n x m) d’entiers et qui vérifie si tous les nombres
qu’il contient sont strictement positifs. Bien sûr, on veillera à éviter tout travail inutile ; la
rencontre d’un nombre négatif ou nul doit arrêter l’algorithme.
Exercice 12 Toute une ligne de valeurs non nulles ?

Écrire un algorithme qui reçoit un tableau d’entiers (à n lignes et m colonnes) ainsi qu’un
numéro de ligne et qui retourne un booléen indiquant si la ligne donnée du tableau ne contient
que des valeurs non nulles.
boolean lignePleine(int[n × m] tab, int lg)
Faites de même pour une colonne.
39
3.4. EXERCICES
Exercice 13 Le carré magique

Un carré magique est un tableau d’entiers carré (c’est-à-dire possédant autant de lignes que de
colonnes) ayant la propriété suivante : si on additionne les éléments d’une quelconque de ses
lignes, de ses colonnes ou de ses deux diagonales, on obtient à chaque fois le même résultat.
Écrire un algorithme recevant en paramètres le tableau (n x n) d’entiers représentant le carré
et renvoyant une valeur booléenne indiquant si c’est un carré magique ou pas.
Exercice 14 Le contour du tableau

On donne un tableau d’entiers à n lignes et m colonnes. Écrire un algorithme retournant la
somme de tous les éléments impairs situés sur le bord du tableau.
Exemple : pour le tableau suivant, l’algorithme doit renvoyer 32
3 4 6 11
2 21 7 9
1 5 12 3
Et pour le suivant, l’algorithme doit renvoyer 6
4 1 2 8 5
Exercice 15 À vos pinceaux !

On possède un tableau à n lignes et n colonnes dont les éléments de type Couleur valent NOIR
ou BLANC. On suppose que le tableau est initialisé à BLANC au départ. Écrire un algorithme
qui noircit les cases de ce tableau comme le suggèrent les dessins suivants (les exemples sont
donnés pour un tableau 10 x 10 mais les algorithmes doivent fonctionner quelle que soit la
taille du tableau).
Notes
. Le zèbre doit toujours présenter des lignes obliques et parallèles, quelle que soit la taille.
. La spirale est un véritable défi et vous est donné comme exercice facultatif. Ne le faites
pas si vous êtes en retard.
40
Chapitre
4 La liste
Dans ce chapitre, nous allons étudier une nouvelle structure de donnée plus souple que le ta-
bleau : la liste. Nous verrons comment il est possible d’implémenter une telle liste en mémoire
en orienté objet, ce qui vous permettra de mettre en pratique une des notions fondamen-
tales vues au cours de Java : l’encapsulation (les autres piliers de l’orienté objet, héritage et
polymorphisme, ne seront pas vus dans ce cours d’algorithmique).
4.1 L’idée de liste

Imaginons que l’on désire manipuler par programme une liste de courses. Cette liste va varier ;
sa taille n’est donc pas fixée. Utiliser un tableau à cet effet n’est pas l’idéal : la taille d’un
tableau ne peut plus changer une fois le tableau créé. On peut bien sûr s’en sortir avec un
tableau, mais cela implique :
. de tenir à jour sa taille logique ;
. de gérer le cas où le tableau n’est pas « assez grand » pour pouvoir mettre tous les
éléments de la liste.
Il serait intéressant de disposer d’une structure nouvelle, qui offre des facilités similaires à celles
des tableaux, tout en ayant une taille dynamique, c’est-à-dire changeante au fil des additions
et suppressions.
Par exemple, considérons une liste de courses. On pourrait la représenter ainsi :
1. "fromage"
2. "pain"
3. "salami"
On pourrait ajouter un élément en fin de liste, par exemple de l’eau, pour obtenir la liste :
1. "fromage"
2. "pain"
3. "salami"
4. "eau"
On pourrait aussi supprimer un élément de la liste, par exemple le pain, et obtenir :
1. "fromage"
2. "salami"
3. "eau"
On pourrait aussi insérer un élément dans la liste, par exemple une baguette, ce qui décale, de
facto, la position des suivants.
1. "fromage"
2. "salami"
41
4.2. COMMENT IMPLÉMENTER UNE LISTE EN MÉMOIRE ?
3. "baguette"
4. "eau"
Et au niveau du code ? Nous aimerions pouvoir écrire des choses comme :
List<String> liste = new List<String>() // bien entendu, ce constructeur n’existe pas en java.
liste.add("fromage")
liste.add("pain")
liste.add("salami")
liste.add("eau")
liste.remove("pain")
liste.add(2, "pain français")
liste.set(2, "baguette")
liste.clear() // Efface la liste
Dans cet exemple nous avons créé une liste de chaînes de caractères (String). De façon générale
on pourra imaginer une liste d’entiers, de booléens, ou d’autres choses encore. Voici par exemple
un morceau de code manipulant une liste d’entiers :
List<int> liste
liste = new List<int>()
liste.add(42)
liste.add(54)
liste.set(1,44)
liste.add(1,43)
liste.removePos(2)
liste.remove(42)
liste.clear()
Après sa création, la liste est vide. Ensuite, elle passe par les états suivants :
0. 42 0. 42 0. 42 0. 42 0. 42 0. 43
1. 54 1. 44 1. 43 1. 43
2. 44
Enfin, le dernier appel la vide complètement
4.2 Comment implémenter une liste en mémoire ?

Nous venons de voir le principe général d’une liste. La question qui se pose alors est de savoir
comment implémenter une liste en mémoire. Il est bien pratique de pouvoir disposer d’une
structure de donnée aussi souple, mais comment faire pour développer une classe Liste per-
mettant d’utiliser concrètement un tel objet ? Rappelons qu’une classe permet de définir un
nouveau type de données, et donc d’encapsuler au sein d’une seule entité différentes propriétés.
Rappelons aussi que pour les tableaux, le problème est nettement plus simple : il suffit de
réserver le bon nombre de cases en mémoire, et on accède à chaque case via son indice (ses
indices dans le cas d’un tableau 2D). Comme la taille d’un tableau ne peut plus changer une
fois créé (on ne peut ni supprimer ni ajouter des cases !), ceci suffit.
A l’évidence, le problème est plus complexe pour une liste, et nous allons donc devoir nous
pencher sur la façon d’implémenter une classe Liste. Dans ce chapitre, nous allons voir qu’il
est en fait possible d’écrire une telle classe de deux façons distinctes, à savoir :
1. au moyen d’un tableau géré dynamiquement par la classe. Le tableau est encapsulé par
la classe et remplacé par un tableau plus grand lorsque cela devient nécessaire (une
ArrayList),
2. en chaînant les éléments les uns à la suite des autres en mémoire (une LinkedList).
42
4.3. LES ARRAYLIST
Nous verrons également que choisir une de ces implémentations (ArrayList ou LinkedList)
impacte les performances : la complexité des algorithmes implémentés par les méthodes add
et get par exemples varie d’une classe à l’autre.
4.3 Les ArrayList

Nous avons vu dans le chapitre 1 qu’un tableau a une taille fixe, appelée sa taille physique. On
y accède en Java avec la propriété length (par exemple : tab.length ).
Lorsqu’on ne connaît pas a priori le nombre d’éléments à mettre dans le tableau, on peut
instancier un tableau « suffisamment grand » pour y mettre les éléments. Le nombre de cases
effectivement utilisées est alors appelé la taille logique. Cette taille doit être ajustée au fur et
à mesure qu’on ajoute ou retire des éléments.
Pour rappel voici deux méthodes écrites au chapitre 1 :
. une méthode register qui permet d’ajouter une valeur dans un tableau :

int register(int[] registered, int nRegistered, int number)

. une méthode unsubscribe qui supprime la valeur donnée du tableau :

int unsubscribe(int[] registered, int nRegistered, int number)

Ces deux méthodes acceptent le tableau registered ainsi que la taille logique nRegistered
en paramètre, modifient le tableau et retournent la nouvelle taille logique.
Le principe d’une ArrayList est alors d’implémenter une liste au moyen d’un tableau encapsulé
dans la classe, la taille logique du tableau étant géré par les méthodes de la classe.
Avant de voir l’implémentation d’une ArrayList, voyons la façon dont les choses se passent en
Java. Une classe ArrayList est déjà implémentée pour vous dans le package java.util , voici
un exemple de son utilisation :
43
4.4. EXERCICES
1 package dev2.algo.liste;
2
3 import java.util.ArrayList;
4
5 public class ArrayListesEnJava{
6
8 /∗ On crée une nouvelle ArrayList vide. On précise le type
9 de donnée à stocker entre les < > ∗/
10 ArrayList<String> liste = new ArrayList<>();
11
12 // Illustration des méthodes add, set et remove
13 liste.add("fromage");
14 liste.add("pain");
15 liste.add("salami");
16 liste.add("eau");
17
18 liste.remove("pain");
19
20 /∗ Je peux préciser à la méthode add l'endroit dans la liste
21 ou effectuer l'insertion. ∗/
22 liste.add(2, "pain français");
23
24 liste.set(2, "baguette");
25
26 // Récupère et affiche l'élément en position 1
27 System.out.println(liste.get(1));
28
29 // La méthode contains() permet de tester l'existence d'un élément
30 if(liste.contains("salami")){
31 System.out.println("La liste contient du salami !");
32 }
33
34 // La méthode size() renvoie le nombre d'éléments courant:
35 System.out.println("La liste contient " + liste.size() + " éléments.");
36
37 // Vide la liste
38 liste.clear();
39
40 }
41 }
Ce code illustre quelques méthodes de la classe ArrayList. Essayez de deviner d’autres mé-
thodes utiles de cette classe. Pour les découvrir, nous vous invitons à consulter la documenta-
tion en ligne : https://docs.oracle.com/en/java/javase/13/docs/api/java.base/java/
util/List.html
4.4 Exercices
Le but de ces exercices est simplement de vous familiariser avec la notion de liste. Comme
d’habitude, les algorithmes peuvent être écris en Java ou en pseudo-code (vous supposerez
dans ce dernier cas l’existence d’une classe ArrayList, classe dont l’implémentation sera donnée
dans la suite du chapitre).
Exercice 1 Manipulation d’ArrayListe
Écrire un algorithme qui crée l’ArrayListe suivante :

0. 494
1. 209
2. 425
affiche sa taille, demande (et affiche le résultat) si la valeur 425 est présente, supprime la valeur
209, puis insère la valeur 101 en tête de liste.
44
4.5. L’INTERFACE D’UNE LISTE
Exercice 2 Afficher tous les éléments d’une ArrayListe

Écrire l’algorithme qui affiche tous les éléments d’une ArrayListe, reçue en paramètre.
Exercice 3 ArrayListe des premiers entiers

Écrire un algorithme qui reçoit un entier n en paramètre et retourne la liste contenant les
entiers de 1 à n dans l’ordre décroissant. On peut supposer que n est strictement positif.
Exercice 4 Somme d’une ArrayListe

Écrire un algorithme qui calcule la somme des éléments d’une ArrayListe d’entiers.
4.5 L’interface d’une liste

Les sections précédentes nous ont permis de découvrir les méthodes add, remove, clear, set
et size. Quelles autres méthodes pourraient être intéressantes ?
Inspirons-nous à nouveau de ce qui existe en Java.
// T est un type quelconque

interface List<T>
public :
void List<T>() // construit une liste vide
T get(int pos) // donne un élément en position pos
void set(int pos, T value) // modifie un élément en position pos
int size() // donne le nombre actuel d’éléments
boolean isEmpty() // la liste est-elle vide ?
void add(T value) // ajoute un élément en fin de liste
void add(int pos, T value) // insère un élément en position pos
void removePos(int pos) // supprime l’élément en position pos
boolean remove(T value) // supprime l’élément de valeur donnée
void clear() // vide la liste
boolean contains(T value) // indique si un élément est présent
int indexOf(T value) // donne la position d’un élément
Remarque : Nous ne précisons pas encore la façon dont ces méthodes sont implémentées,
vu que cela va dépendre de la représentation mémoire choisie pour notre liste (ArrayList ou
LinkedList). Nous donnerons ces implémentations dans les sections qui suivent. Les méthodes
fournies ci-dessus ne constituent donc qu’une interface (un contrat où il y a que les signatures
des méthodes).
Quelques précisions s’imposent :
. get(pos) et set(pos,value) permettent de connaitre ou modifier un élément de la liste.

Comme pour les tableaux, le premier élément de la liste est en position 0.
. add(value) ajoute un élément en fin de liste. Elle grandit donc d’une unité.
. add(pos,value) insère un élément à une position donnée (entre 0 et taille-1). L’élément qui
s’y trouvait est décalé d’une position ainsi que tous les éléments suivants.
. remove(value) enlève un élément de valeur donnée en décalant les éléments suivants. Elle
retourne un booléen indiquant si la suppression a pu se faire ou pas (si la valeur était
présente ou pas). Si la valeur existe en plusieurs exemplaires, la méthode n’en supprime
que la première occurrence trouvée.
. removePos(pos) supprime un élément d’une position donnée en décalant les éléments
suivants. Nous avons changé le nom de la version Java qui s’appelle remove pour ne pas
confondre avec la précédente dans le cas d’une liste d’entiers.
. contains(value) permet de savoir si un élément donné existe dans la liste.
. indexOf(value) donne la position d’un élément dans la liste.
. si l’élément n’existe pas, elle retourne −1.
45
4.6. IMPLÉMENTER UNE ARRAYLIST
. si l’élément est présent en plusieurs exemplaires, la méthode donne la position de la

première occurrence de value.
. En pratique, il serait intéressant de chercher un élément à partir d’une partie de l’informa-
tion qu’elle contient 1 mais c’est difficile (pas impossible !) à exprimer de façon générique
c’est-à-dire lorsque le type n’est pas connu a priori.
. Il existe encore plus de méthodes en Java. Nous vous invitons à consulter la documen-
tation : https://docs.oracle.com/en/java/javase/13/docs/api/java.base/java/
util/List.html
4.6 Implémenter une ArrayList

Dans cette section nous décrivons l’implémentation de la classe ArrayList qui encapsule un
tableau et sa taille logique au sein d’un même objet, dans le but de pouvoir gérer ces deux
aspects en parallèle. Le tableau permet de contenir des valeurs, et la taille logique indique
quelles sont les cases du tableau réellement utilisées.
Nous utiliserons des valeurs de type « chaînes de caractères » (String), mais l’implémentation
pourra s’adapter à d’autres types de données 2 .
Les attributs La classe a donc deux attributs privés : un tableau et sa taille logique.
class ArrayList
private :
String[] tab // Le tableau contenant les données.
int size // La taille logique du tableau.
Ces attributs sont accessibles par le constructeur et toutes les méthodes de la classe.
Constructeur Le rôle du constructeur est d’initialiser les attributs de la classe.

Nous allons définir deux constructeurs. Dans le premier, nous recevons un entier qui correspond
à la taille physique du tableau. Ceci correspond au nombre maximal de String que notre objet
sera capable de contenir.
constructor ArrayList(int maxSize)

if maxSize < 0
error La taille maximale doit être un entier positif.
tab = new String[maxSize]
size = 0 // liste vide au départ
La complexité est O(1) 3 .

Par facilité, nous définissons un second constructeur avec une taille physique par défaut :
constructor ArrayList()
this(20) // Appel à l’autre constructeur, comme en Java.
Insertion La classe offrira notamment deux méthodes 4 pour insérer des valeurs :
1. Par exemple : trouver toutes les chaînes d’une liste de chaînes dont la dernière lettre est une voyelle.
2. Voir le mécanisme des génériques (generics), en Java
3. Pour rappel on ne s’intéresse ici qu’à la complexité temporelle. La complexité spatiale est ici évidem-
ment égale à la taille maximale demandée. Notons également que certains langages, et le Java est de ceux-là,
parcourent implicitement le tableau pour l’initialiser. La complexité temporelle devient alors O(n) dans ces
langages.
4. Les deux méthodes ont le même nom, mais pas la même signature, ce qui permet de les différencier.
Beaucoup de langages, y compris le Java, permettent cela.
46
public :
void add(String value) // ajoute un élément en fin de liste
void add(int pos, String value) // insère un élément en position pos
Notons que chacune de ces méthodes est responsable de modifier la taille logique. Il n’y a donc
plus d’utilité de retourner cette taille logique.
Une implémentation de la première méthode add serait :
method void add(String value)

if size >= tab.length
error La taille maximale est atteinte !
tab[size] = value
size++
La complexité est O(1). Notez que les deux dernières lignes pourraient se réduire à :
tab[size++] = value // On gardera plutôt les deux lignes par souci de lisibilité
Complexité amortie
Dans cette implémentation, si la taille maximale est atteinte, une exception est levée.
Une autre façon de gérer la limite est d’augmenter la taille physique : créer un second
tableau, plus grand (typiquement de taille double), et recopier les éléments du premier
vers le second.
Avec cette technique, la complexité de l’ajout n’est plus constante, mais linéaire (c’est-à-
dire O(n)). En effet, dans le pire des cas il faut recopier tout le tableau, ce qui implique
de le parcourir complètement. Cependant cet effet n’apparaît « pas souvent » ; à tel
point qu’en moyenne a , on peut parler de complexité amortie en temps constant.
a. cormen_2009.
Pour la seconde méthode, notons d’abord une conséquence de la simple existence de cette
méthode. En effet, cette méthode permettant d’insérer une valeur à une position précise donnée,
ceci implique que la position des valeurs a de l’importance. Dès lors, insérer une valeur à une
position doit décaler les autres valeurs, afin que l’ordre relatif des valeurs soit préservé. Muni
de cette information nous savons maintenant implémenter la méthode :
method void add(int pos, String value)

if size >= tab.length
error La taille maximale est atteinte !
if (pos < 0 or pos > size)
error Position illégale
for (int i = size ; i > pos ; i--) // Décalage vers la droite
tab[i] = tab[i-1]
tab[pos] = value
size++
Dans la mesure où il faut potentiellement parcourir tout le tableau, cette méthode est en O(n).
Nous aborderons plus tard l’implémentation pour les méthodes de suppression (remove, remo-
vePos).
Taille (size) Comme c’est la classe qui est responsable de tenir à jour sa taille logique, il
doit y avoir une méthode pour récupérer la taille (logique) courante :
public :
47
Voici une implémentation :
method int size()

return size
La complexité est O(1).

Nous ne définissons pas de méthode qui retourne la taille physique du tableau : ceci est considéré
comme un détail d’implémentation.
Accéder à un élément avec son indice (get, set) Dans un tableau, la syntaxe tab[2]
permet d’accéder au troisième élément (élément d’indice 2), mais cette syntaxe est réservée
aux tableaux.
Pour nos objets ArrayList, nous définissons deux méthodes :
public :
String get(int pos) // donne un élément en position pos
void set(int pos, String value) // modifie un élément en position pos
dont une implémentation est :
method String get(int pos)

if pos < 0 or pos >= size
return tab[pos]
method void set(int pos, String value)
tab[pos] = value
La complexité de ces deux méthodes est en O(1).
Trouver un élément Pour retrouver un élément, nous allons définir deux méthodes.
public :
int indexOf(String value) // donne la position d’un élément
boolean contains(String value) // indique si un élément est présent
La méthode indexOf retourne donc la position (l’indice) de la première occurrence de la valeur

dans la liste. Dans le cas particulier où la valeur cherchée n’est pas dans le tableau, nous
retournons par convention −1 :
method int indexOf(String value)

int pos = 0
while pos < size and tab[pos] != value
pos++
return (pos < size) ? pos : -1
(Attention, en Java un test d’égalité ou d’inégalité entre chaînes se réalise avec la méthode
equals .) Cette méthode parcourt la liste, et est donc en complexité O(n) (où n représente la
longueur de la liste).
La méthode contains effectue également une recherche mais retourne seulement un booléen :
method boolean contains(String value)

return indexOf(value) != -1 // indexOf est une méthode d’instance. On pourrait écrire
// this.indexOf.
48
Notons que cette méthode a également une complexité O(n), puisqu’elle appelle indexOf.
Supprimer un élément Pour supprimer un élément, nous définissons deux méthodes :
public :
void removePos(int pos) // supprime l’élément en position pos – O(1)
boolean remove(String value) // supprime l’élément de valeur donnée – O(n)
Avant d’aborder l’implémentation, rappelons qu’il y a deux manières d’envisager la suppres-

sion : soit on considère que les éléments doivent rester dans l’ordre, soit pas. Suivant la discus-
sion dans la méthode add(int, String), nous devons considérer que l’ordre a de l’importance.
Concrètement, on va donc devoir décaler les valeurs pour « combler le trou » laissé par la
valeur supprimée.
method void removePos(int pos)

for (int i = pos+1 ; i < size ; i++) // Décalage vers la gauche
tab[i-1] = tab[i]
size--
La méthode de suppression par valeur peut alors s’écrire simplement en combinant la recherche
de la valeur et la suppression par position :
method boolean remove(String value)

int pos = indexOf(value)
if pos == -1
return false
removePos(pos)
return true
Vider la liste Nous définissons également une méthode permettant de vider complètement
la liste.
public :
Pour l’implémentation, rappelons-nous que l’attribut size détermine la taille de la liste. Si ce

dernier vaut 0, la liste est moralement vide, peu importe ce qui se trouve dans le tableau !
method void clear()

size = 0
Cette méthode est en O(1).
La liste est-elle vide ? La dernière méthode que nous implémentons permet de déterminer
si notre objet ArrayList est vide :
public :
L’implémentation ne devrait surprendre personne :
method boolean isEmpty()

return size == 0
49
4.7. LISTE CHAÎNÉES
4.6.1 Exercices
Exercice 5 Une autre implémentation de remove
Voici une autre implémentation de remove :
method boolean remove(String value)

if not contains(value)
return false
removePos(indexOf(value))
return true
Quelle est la complexité de cette version, et comment comparer les deux versions ?
4.7 Liste chaînées

Nous avons vu une première classe, ArrayList, qui implémente toutes les méthodes de l’interface
List. Nous allons en voir une autre. Cette fois, l’idée est que chaque valeur de la liste sera
contenue dans un objet (de type Node), qui « connaît » son successeur. Pour pouvoir parcourir
une liste, il suffit donc de connaître le premier Node, et de suivre les successeurs successifs.
Ceci est illustré sur le dessin ci-dessous :
Pour cette raison, "une liste" sera un objet (de type SinglyLinkedList) contenant simplement
une référence vers un Node.
Remarquez qu’il serait aussi possible de chaîner la liste dans les deux sens, comme illustré
ci-dessous :
Ce type de liste chaînée est appelée liste chaînée double. Lorsqu’on mentionne une liste chaînée,
il est donc important de savoir de quoi on parle (une liste simplement chaînée ? une liste
double ? 5 ).
L’implémentation que nous allons donner dans les sections qui suivent correspond à une liste
chaînée simple, ce qui explique le nom de la classe : "SinglyLinkedList".
Et en Java ? Avons-nous une classe LinkedList à notre disposition (de même que la classe
ArrayList) ? Oui, mais attention : la classe LinkedList de Java implémente en réalité une liste
chaînée double. Elle se manipule comme on s’y attend :
5. Et il existe encore d’autres variantes/généralisations, nous n’en parlerons pas dans ce cours
50
4.8. IMPLÉMENTER UNE LINKED LIST
1 package dev2.algo.liste;
2
3 import java.util.linkedList;
4
5 public class LinkedListesEnJava{
6
8 /∗ LinkedList est en réalité une liste double ∗/
9 LinkedList<String> liste = new LinkedList<>();
10
11 // Illustration des méthodes add, set et remove
12 liste.add("fromage");
13 liste.add("pain");
14 liste.add("salami");
15 liste.add("eau");
16
17 liste.remove("pain");
18
19 /∗ Je peux préciser à la méthode add l'endroit dans la liste
20 ou effectuer l'insertion. ∗/
21 liste.add(2, "pain français");
22
23 liste.set(2, "baguette");
24
25 // Récupère et affiche l'élément en position 1
26 System.out.println(liste.get(1));
27
28 // La méthode contains() permet de tester l'existence d'un élément
29 if(liste.contains("salami")){
30 System.out.println("La liste contient du salami !");
31 }
32
33 // La méthode size() renvoie le nombre d'éléments courant:
34 System.out.println("La liste contient " + liste.size() + " éléments.");
35
36 // Vide la liste
37 liste.clear();
38
39 }
40 }
Comme vous pouvez le constater, elle se manipule de la même façon qu’une ArrayList (forcé-
ment vu que ces deux classes implémentent la même interface). Nous verrons cependant que
les performances des différentes méthodes peuvent fortement varier.
4.8 Implémenter une linked list
class SinglyLinkedList
private :
Node head // Référence à la tête de liste.
class Node
private :
T value // La valeur du noeud
Node next // Référence à l’élément suivant. null sinon
Cohérence interne : il faut qu’il n’y ait pas de cycles (c’est-à-dire un noeud qui référence un
nœud qui référence un nœud . . . ultimement référence un noeud précédent). En particulier la
chaîne devra forcément se terminer par null .
Voyons comment implémenter certaines méthodes de notre interface selon ce principe.
Constructeur Le rôle du constructeur est d’initialiser les attributs de la classe. Pour rappel
le constructeur de nos listes crée une liste vide. Il n’y a donc aucune valeur, et donc aucun
51
Node.
constructor SinglyLinkedList()
head = null
Insertion Rappelons les méthodes à implémenter :
public :
void add(String value) // ajoute un élément en fin de liste
void add(int pos, String value) // insère un élément en position pos
Pour la première méthode, il faut trouver le dernier Node, et lui ajouter un successeur. Le cas
particulier d’une liste vide doit être traité à part.
method void add(String value)

if head == null
head = new Node(value, null)
else
Node last = last()
last.next = new Node(value, null)
// Un « Node » reste interne à la classe.

private method Node last()
Node cur = head
while cur != null and cur.next != null
cur = cur.next
return cur
La complexité est O(n).

Pour la seconde méthode, il faut avancer dans la liste pour trouver l’élément à la position
voulue. Plus précisément, il faut trouver l’élément qui précède la position donnée, afin de
pouvoir le modifier et insérer la nouvelle valeur.
// Retourne l’élément à la position indiquée, ou null s’il n’existe pas.

private method Node findElemAtPos(int pos)
if pos < 0
return null
Node cur = head
while cur != null and pos > 0
pos = pos - 1
cur = cur.next
return cur // Sera null si l’élément n’a pas été trouvé
method void add(int pos, String value)
if pos == 0
head = new Node(value, head)
else
Node prev = findElemAtPos(pos - 1)
if prev == null
error La position demandée n’existe pas
prev.next = new Node(value, prev.next)
Dans le pire des cas, il faut parcourir (avec findElemAtPos ) toute la liste pour trouver le point
d’insertion, mais l’insertion proprement dite est en temps constant. La complexité est donc
O(n) 6 .
6. Si on considère la position spécifique comme variable, on peut dire que la complexité est O(pos). Il faut
52
Accéder à un élément avec son indice (get, set) avec findElemAtPos nous avons fait
l’essentiel du travail pour implémenter get et set .
method String get(int pos)

Node elem = findElemAtPos(pos)
if elem == null
error La position demandée n’existe pas.
return elem.value
method void set(int pos, String newValue)
Node elem = findElemAtPos(pos)
if elem == null
error La position demandée n’existe pas.
elem.value = newValue
La complexité de ces deux algorithmes est en O(n).
La taille Contrairement au cas de ArrayList , la taille n’est pas un attribut de notre classe 7 .
Pour compter le nombre d’éléments, il faut donc parcourir la liste.
method int size()

Node cur = head
int size = 0
while cur != null
size++
cur = cur.next
return size
La complexité est O(n).
isEmpty Pour déterminer si une liste est vide, il est naturel de se demander si la taille vaut
0. Cependant, notre méthode size a une complexité linéaire. Une implémentation en temps
constant est simplement :
method boolean isEmpty()

return head == null
4.8.1 Parcourir une SinglyLinkedList

afficher Pour rappel, dans les exercices de la section 4.4, nous avions vu l’algorithme suivant
pour afficher une ArrayList :
void afficher( List<int> liste)

for pos from 0 to liste.size()-1
print liste.get(pos)
Ce n’est pas une bonne façon de parcourir une SinglyLinkedList.

En effet, le calcul de liste.get(pos) est en O(n), et il y a bien sûr n tours de boucles, ce qui
donne une complexité en O(n2 ), plutôt mauvaise pour un simple affichage 8 .
toutefois être prudent : cela ne veut pas dire que si pos = 0 la complexité est O(0). Cela n’a pas de sens de
remplacer pos par sa valeur. Si on considère l’insertion d’un élément en tête de liste, alors pos est constant
(pos = 0), et l’opération est en O(1).
7. Il est possible d’ajouter cet attribut et de maintenir sa valeur au travers des opérations sur la liste, mais
il s’agirait d’une optimisation, et c’est un autre sujet.
8. Même en tenant compte du fait que la complexité de liste.get(pos) est en O(pos), le nombre d’instruc-
tions est de l’ordre de 0 + 1 + 2 + 3 + · · · + n = n(n + 1)/2, ce qui reste O(n2 ).
53
La bonne manière d’afficher une liste chaînée est
method void afficher()

Node cur = head
while cur != null
print cur.value
cur = cur.next
La complexité est en O(n).
Parcourir avec un Iterator Cependant la classe Node est privée. Dès lors tout algorithme
voulant parcourir une liste chaînée (faire une somme, trouver un maximum, etc.) devrait être
implémenté comme une méthode, afin d’accéder à ces objets Node, ce qui n’a aucun sens. La
solution standard à ce problème est de retourner un Iterator : c’est un objet permettant de
parcourir (efficacement, donc en O(n)) n’importe quelle liste.
54
Méthode Description ArrayList SinglyLinkedList

void ArrayList/SinglyLinkedList() construit une liste vide O(1) O(1)
String get(int pos) donne un élément en position pos O(1) O(n)
void set(int pos, String value) modifie un élément en position pos O(1) O(n)
int size() donne le nombre actuel d’éléments O(1) O(n)
boolean isEmpty() la liste est-elle vide ? O(1) O(1)
void add(String value) ajoute un élément en fin de liste O(n) ou O(1) O(n)
void add(int pos, String value) insère un élément en position pos O(n) O(n)
void removePos(int pos) supprime l’élément en position pos O(n) O(n)
boolean remove(String value) supprime le premier élément de valeur donnée O(n) O(n)
void clear() vide la liste O(1) O(1)
int indexOf(String value) donne la position d’un élément O(n) O(n)
boolean contains(String value) indique si un élément est présent O(n) O(n)
Table 4.1 – Comparaison des complexités de ArrayList et SinglyLinkedList
Voici à quoi ressemble l’interface Iterator :
interface Iterator<T>
public :
boolean hasNext() // doit être en O(1)
T next() // doit être en O(1)
L’idée est d’ajouter à l’interface de List<T> une méthode

interface List<T>
public :
void List<T>() // construit une liste vide
..
.
Iterator<T> iterator() // idéalement en O(1)
La méthode iterator qui s’utilisera comme suit :
int sum( List<int> l)

Iterator<int> it = l.iterator()
int sum = 0
while it.hasNext()
sum += it.next()
return sum
Remarquons enfin qu’en Java la syntaxe :

for (T obj : liste) {
// ...do something
}

utilisera l’itérateur de la liste pour fonctionner et permet donc un parcours en O(n).
4.8.2 Comparaison ArrayList et SinglyLinkedList

On trouvera dans la table 4.1 un récapitulatif des méthodes de l’interface List, avec la com-
plexité pour chacune des deux implémentations.
Face à un tel tableau, on peut se poser la question de la pertinence d’une structure telle que
SinglyLinkedList .
D’une part la performance réelle dépendra de l’utilisation qui est faite de la structure. À titre
d’exemple, une insertion dans une SinglyLinkedList en connaissant le Node qui précède le point
55
d’insertion se fait en temps constant. C’est notamment le cas pour une insertion en début de
liste, qui est toujours en temps constant alors que c’est en temps linéaire pour une ArrayList.
D’autre part, le concept de liste chaînée peut être modifié selon le besoin :
. ajout d’un attribut size pour garder la taille en mémoire ;
. ajout d’un attribut tail pour garder le dernier Node de la liste en mémoire ;
. modifier la classe Node pour obtenir une version doublement chaînée, parcourable dans
les deux sens.
En Java, ces choix ont été implémentés dans la classe LinkedList .
4.8.3 Exercices
Pour chaque exercice, donnez la complexité de l’algorithme obtenu.
Exercice 6 indexOf
Écrivez la méthode de la classe SinglyLinkedList
int indexOf(String val)
qui retourne la position de la valeur donnée au sein de la liste chaînée. La valeur -1 est retournée
si la valeur ne s’y trouve pas.
Exercice 7 contains
boolean contains(String val)
qui décide si la valeur donnée se trouve dans la liste chaînée.
56
4.9. LES LISTES : UN EXEMPLE D’APPLICATION
Exercice 8 removePos
void removePos(int pos)
qui supprime une valeur à la position donnée.
Exercice 9 remove
On veut écrire la méthode de la classe SinglyLinkedList
boolean remove(String val)
qui supprime la première occurrence de la valeur donnée si elle existe. La méthode renvoie true
si une suppression a été effectuée, false sinon.
4.9 Les listes : un exemple d’application

Donnons pour finir un exemple d’application concrète des listes dans un algorithme.
Dans le chapitre sur les tableaux, vous avez fait un exercice consistant à afficher tous les indices
où se trouve le minimum d’un tableau.
Reprenons-le et modifions-le afin qu’il retourne la liste des indices où se trouvent les différentes
occurrences du minimum. On pourrait l’écrire ainsi :
// Question : Vaut-il mieux travailler avec ArrayList ou des LinkedList ici ?

List<int> indicesMinimum(int[n] tab)
int min
List<int> indicesMin
min = tab[0]
indicesMin = new List<int>()
indicesMin.add(0)
for i from 1 to n-1
if tab[i] == min
indicesMin.add(i)
else if tab[i] < min
indicesMin.clear()
indicesMin.add(i)
min = tab[i]
// rien à faire si tab[i] > min
return indicesMin
En Java ça donne :
57
4.10. LES LISTES : EXERCICES RÉCAPITULATIFS
1 public static List<Integer> indicesMinimum(int[] tab) {

2 List<Integer> indicesMin;
3 Integer min;
4 min = tab[0];
5 indicesMin = new ArrayList<>();
6 indicesMin.add(0);
7 for (int i = 1; i < tab.length; i++) {
8 if (tab[i] == min) {
9 indicesMin.add(i);
10 } else if (tab[i] < min) {
11 indicesMin.clear();
12 indicesMin.add(i);
13 min = tab[i];
14 }
15 }
16 return indicesMin;
17 }
4.10 Les listes : exercices récapitulatifs

Pour les exercices ci-dessous, nous ne précisons pas s’il vaut mieux utiliser une liste chaînée ou
une ArrayList. A vous de décider ce qui est mieux en terme de performances !
Exercice 10 Anniversaires
(cet exercice requiert des notions d’Orienté Objet.)
Écrire un algorithme qui reçoit une liste d’objets Personne 9 et retourne une nouvelle liste de
ceux qui sont nés durant un mois passé en paramètre (donné sous la forme d’un entier entre 1
et 12).
Exercice 11 Concaténation de deux listes

Écrire un algorithme qui reçoit 2 listes et ajoute à la suite de la première les éléments de la
seconde ; la seconde liste n’est pas modifiée par cette opération.
Exercice 12 Le nettoyage
Écrire un algorithme qui reçoit une liste de chaines en paramètre et supprime de cette liste tous
les éléments de valeur donnée en paramètre. L’algorithme retournera le nombre de suppressions
effectuées.
Exercice 13 Les extrêmes

Écrire un algorithme qui supprime le minimum et le maximum des éléments d’une liste
d’entiers. On peut supposer que le maximum et le minimum sont uniques.
Exercice 14 Fusion de deux listes

Soit deux listes triées d’entiers (redondances possibles). Écrire un algorithme qui les fusionne.
Le résultat est une liste encore triée contenant tous les entiers des deux listes de départ (qu’on
laisse inchangées).
Exemple : Si les 2 listes sont (1, 3, 7, 7) et (3, 9), le résultat est (1, 3, 3, 7, 7, 9).
Exercice 15 Éliminer les doublons d’une liste

Soit une liste triée d’entiers avec de possibles redondances. Écrire un algorithme qui enlève
les redondances de la liste.
Exemple : Si la liste est (1, 3, 3, 7, 8, 8, 8), le résultat est (1, 3, 7, 8).
a) Faites l’exercice en créant une nouvelle liste (la liste de départ reste inchangée)
9. comportant des attributs nom et prénom (des chaînes de caractères) et un attribut date, de type Date,
ayant lui-même des attributs jour, mois et année (des entiers).
58
4.10. LES LISTES : EXERCICES RÉCAPITULATIFS
b) Refaites l’exercice en modifiant la liste de départ (pas de nouvelle liste)
Exercice 16 Rendez-vous
(cet exercice requiert des notions d’Orienté Objet.)
Soit la classe RendezVous ayant comme attribut une date (type Date) et un motif de rencontre
(type String).
Écrire un algorithme qui reçoit une liste de rendez-vous et la met à jour en supprimant tous
ceux qui sont désormais passés.
Pour résoudre cet exercice, vous pouvez utiliser sans l’écrire un algorithme aujourdhui() qui
retourne la date du jour.
59
Chapitre
5 La pile
5.1 Définition
Une pile est une collection d’éléments admettant les fonctionnalités suivantes :
. on peut toujours ajouter un élément à la collection ;

. seul le dernier élément ajouté peut être consulté ou enlevé ;
. on peut savoir si la collection est vide.
La pile (en anglais stack) est donc une collection de données de type dernier entré, premier
sorti (en anglais on dit « LIFO », c’est-à-dire last in first out). L’analogie avec la pile de
dossiers sur un bureau est claire : les dossiers sont déposés et retirés du sommet et on ne peut
jamais ajouter, retirer ou consulter un dossier qui se trouve ailleurs dans la pile.
On ne peut donc pas parcourir une pile, ou consulter directement le n-ième élément. Les
opérations permises avec les piles sont donc peu nombreuses, mais c’est précisément là leur
spécificité : elles ne sont utilisées en informatique que dans des situations particulières où
seules ces opérations sont requises et utilisées. Paradoxalement, on implémentera une pile en
restreignant des structures plus riches aux seules opérations autorisées par les piles. Cette
restriction permet de n’utiliser que les fonctionnalités nécessaires de la pile, simplifiant ainsi
son utilisation.
61
5.2. IMPLÉMENTATION ORIENTÉ-OBJET
Des exemples d’utilisations sont la gestion de la mémoire par les micro-processeurs, l’évaluation
des expressions mathématiques en notation polonaise inverse, la fonction « ctrl-Z » dans un
traitement de texte qui permet d’annuler les frappes précédentes, la mémorisation des pages
web visitées par un navigateur, etc. Nous les utiliserons aussi en ALG3 pour parcourir les
arbres et les graphes.
5.2 Implémentation orienté-objet

5.2.1 Allure générale
Nous allons d’abord décrire l’allure générale de l’interface Pile.
Il existe plusieurs possibilités de classes implémentant cette interface. Nous les détaillerons à
titre d’exercice.
// T est le type des éléments de la pile

interface Pile<T>
void empiler(élément : T) // ajoute un élément au sommet de la pile
T sommet() // retourne la valeur de l’élément au sommet de la pile, sans le retirer
T dépiler() // enlève et retourne l’élément au sommet
booléen estVide() // indique si la pile est vide
5.2.2 Remarques :
. Théoriquement, et dans la majorité des utilisations, la pile est infinie, c’est-à-dire qu’on
peut y ajouter un nombre indéterminé d’éléments (comme c’était le cas pour la classe Liste
étudiée au chapitre précédant). Dans certaines situations, on peut cependant imposer une
capacité maximale à la pile (en pratique, c’est le cas de la pile de dossiers dans un bureau,
elle est forcément limitée par la hauteur du plafond !). Nous aborderons ce cas particulier
dans les exercices.
. Lors de l’implémentation de la classe, il faudra songer à envoyer un message d’erreur
lorsqu’on utilise les méthodes sommet et dépiler si la pile est vide. Si la pile possède une
taille maximale, alors c’est empiler qui doit générer une erreur lorsque la pile est pleine.
. Nous avons utilisé ici des noms de méthodes neutres indépendants de tout langage de
programmation. Dans la littérature anglaise, on trouvera souvent push, top et pop en lieu
et place de empiler, sommet et dépiler.
5.3 Exemple d’utilisation

Afin d’illustrer l’utilisation d’une classe implémentant l’interface Pile, nous donnons pour
exemple un algorithme qui lit une suite d’enregistrements d’un fichier fileIn (de type Info) et
les reproduit en ordre inverse dans le fichier fileOut.
62
5.4. EXERCICES
void inverserOrdre(Info fileIn ↓ , Info fileOut ↑ )

// fileIn et fileOut sont des Fichiers dont les enregistrements sont de type Info
Info enr
Pile<Info> pile // on déclare la pile du type de l’interface Pile
pile = new ClassePile<Info> // on la crée du type de la classe qui implémente l’interface Pile
// 1ère étape : parcours du fichier et mise en pile

fileIn.ouvrir( )
enr = fileIn.lire( )
while NON fileIn.EOF( )
pile.empiler(enr)
enr = fileIn.lire( )
fileIn.fermer( )
// 2e étape : vider la pile et écrire les éléments dans le fichier de sortie

fileOut.ouvrir( )
while NON pile.estVide( )
enr = pile.dépiler( )
fileOut.écrire(enr)
fileOut.fermer( )
5.4 Exercices
Exercice 1 Implémentation via une liste chainée

Détaillez l’implémentation de la classe PileListe en utilisant comme attribut privé une liste
chainée. Veillez à utiliser les méthodes qui permettent la gestion la plus efficace.
Exercice 2 La pile de taille finie

On envisage ici une pile dont la capacité est limitée : elle ne peut contenir au plus qu’un
nombre donné d’éléments. On demande d’implémenter ce type de pile en utilisant un tableau.
Les attributs privés de la classe seront les suivants :
class PileTab<T> implémente Pile<T>

private :
T[] tab // tableau (dynamique) contenant les éléments de la pile
int indSommet // indice du sommet de la pile
int tailleMax // taille maximale de la pile
On remplira le tableau en ajoutant les éléments les uns à la suite des autres et en retenant la
position du dernier élément, qui correspondra à la valeur de l’attribut indSommet. Cet attribut
augmentera lorsqu’on ajoute un élément, et va décroître lorsqu’on en retire un.
Détaillez l’implémentation des méthodes de la classe PileTab correspondant à cette situation.
Il faudra aussi adapter le constructeur, en lui donnant comme paramètre la taille maximale de
la pile.
Exercice 3 L’itinéraire retour
Un fichier aller contient la description d’un itinéraire. Chaque enregistrement du fichier est
une structure Étape contenant les champs ville (chaine) et km (réel). Écrire un algorithme
qui crée le fichier retour qui contiendra – au même format que aller – la description de
l’itinéraire retour.
Exemple :
63
5.4. EXERCICES
aller retour
Bruxelles 0 Amsterdam 0
Antwerpen 40 Utrecht 50
Breda 100 Breda 120
Utrecht 170 Antwerpen 180
Amsterdam 220 Bruxelles 220
Exercice 4 Notation polonaise inverse
La notation polonaise inverse (encore appelée notation postfixée) consiste à donner tous les
opérandes d’une opération avant de donner l’opérateur lui-même. Le résultat de l’opération
devient un opérande pouvant à son tour être utilisé comme nouvel opérande d’une opération.
L’intérêt de cette notation est qu’il ne nécessite pas de parenthèse à condition d’écrire les
opérandes dans le bon ordre.
Par exemple,
. 1 + 2 s’écrit « 1 2 + »
. (1 * 2) + 3 s’écrit « 1 2 * 3 + »
. 1 * (2 + 3) s’écrit « 1 2 3 + * »
. (4 + 3) * (3 + 2) s’écrit « 4 3 + 3 2 + * »
. 4 + (3 * 3) + 2 s’écrit « 4 3 3 * + 2 + »
. 32 - 2 * (12 - 3 * (7 - 2)) s’écrit « 32 2 12 3 7 2 - * - * - »
Reprenons l’exemple « 4 3 3 * + 2 + » : une pile contiendra successivement
3
3 3 9 2
4 4 4 4 13 13 15
À l’aide d’une Pile<int>, écrivez un algorithme qui interprète les opérations arithmétiques
simplifiées aux entiers en notation polonaise inverse.
Votre algorithme recevra en paramètre un tableau de chaines et retournera un entier, le résultat
de l’opération.
Vous pouvez utiliser les algorithmes
. estNombre(String c ) qui retourne vrai si c peut être converti en un nombre et faux
sinon.
. nombre(String c ) qui convertit c en l’entier correspondant
Nous supposerons le tableau entré comme ne comportant pas d’erreur et n’utilisant que des
opérateurs binaires +, -, * et / (pour la division entière).
64
Chapitre
6 La file
6.1 Définition
Une file est une collection d’éléments admettant les fonctionnalités suivantes :
. on peut toujours ajouter un élément à la collection

. seul le premier élément ajouté peut être consulté ou enlevé
. on peut savoir si la collection est vide
La file (en anglais queue) est donc une collection de données de type premier entré, premier
sorti (en anglais on dit « FIFO », c’est-à-dire first in first out). L’analogie avec une file de
clients à un guichet (poste, caisse du supermarché, ...) est évidente : c’est le premier arrivé qui
est le premier servi, et il est très malvenu d’essayer de doubler une personne dans une file !
Noter qu’une fois entré dans une file – au sens informatique du terme – on ne peut pas en
sortir par l’arrière, le seul scénario possible pour en sortir est d’attendre patiemment son tour
et d’arriver en tête de la file.
De même que pour la pile, on ne peut donc pas non plus parcourir une file, ou consulter di-
rectement le n-ième élément. Les files sont très utiles en informatique, citons par exemple la
création de mémoire tampon (buffer) dans de nombreuses applications, les processeurs multi-
tâches qui doivent accorder du temps-machine à chaque tâche, la file d’attente des impressions
pour une imprimante, ...
6.2 Implémentation orienté-objet

6.2.1 Allure générale
Comme pour la pile, l’interface File ne contient qu’un nombre restreint de méthodes qui cor-
respondent aux quelques opérations permises avec cette structure : ajouter un élément (« en-
filer »), consulter l’élément de tête, et le retirer (« défiler »). Comme précédemment, le détail
des classes implémentant l’interface sera laissé à titre d’exercices.
65
6.3. EXERCICES
interface File<T>
// T est le type des éléments de la file
void enfiler(T élément) // ajoute un élément dans la file
T tête() // retourne la valeur de l’élément en tête de file, sans le retirer
T défiler() // enlève et retourne l’élément de tête
booléen estVide() // indique si la file est vide
6.2.2 Remarques :
. De même que dans le chapitre précédent, la file est supposée infinie, c’est-à-dire qu’on
peut y ajouter un nombre indéterminé d’éléments. Le cas de la file limitée à une capacité
maximale sera envisagé dans l’exercice 2.
. Dans l’implémentation, il faudra songer à envoyer un message d’erreur lorsqu’on utilise
les méthodes tête et défiler si la file est vide. Si la file possède une taille maximale, alors
c’est enfiler qui doit générer une erreur lorsque la file est pleine.
6.3 Exercices
Exercice 1 Implémentation via une liste chainée bidirectionnelle

Détaillez l’implémentation de la classe file en utilisant comme représentation des données une
liste chainée bidirectionnelle.
Exercice 2 La file de taille limitée

La file de taille limitée ne peut contenir au plus qu’un nombre donné d’éléments. On demande
d’implémenter ce type de file en utilisant un tableau. Les attributs privés de la classe seront
les suivants :
class FileTab<T> implémente File<T>

private :
T[] tab // tableau (dynamique) contenant les éléments de la file
int premier // indice du premier élément entré (tête de file)
int dernier // indice du dernier élément entré (fin de file)
int nbMaxÉlément // nombre maximum d’éléments de la file
Nous proposons ici d’offrir un constructeur qui reçoit le nombre maximum d’éléments de la file
et qui crée un tableau d’indices 0 à nbMaxÉlément (le tableau aura donc un élément de plus
que le nombre maximum d’éléments de la file, nous allons expliquer pourquoi). On remplit
le tableau en ajoutant les éléments les uns à la suite des autres en retenant la position du
premier et du dernier via deux indices. Lorsqu’on ajoute un élément, la position du dernier va
augmenter, et lorsqu’on enlève un élément, cela revient à augmenter la position du premier,
afin d’éviter de devoir retasser l’ensemble de la file en début de tableau, ce qui serait une perte
d’efficacité.
66
6.3. EXERCICES
Exemple :
Supposons qu’après la création de la file, les éléments 4, 3, 6 et 2 ont été ajoutés.
L’indice du premier est 0 et celui du dernier est 3.
4 3 6 2
On ajoute l’élément 7. L’indice du dernier est à présent 4.
4 3 6 2 7
On enlève un élément de la file. L’indice du premier vaut maintenant 1
3 6 2 7
Ce mécanisme peut se faire de façon circulaire : arrivés en fin de tableau, les indices premier
et dernier repassent à 0. Lorsque premier et dernier sont égaux, la file n’a qu’un seul élément.
Si cet élément est supprimé, l’incrémentation de premier aura pour conséquence que l’indice
premier sera d’une unité supérieur à l’indice dernier (en tenant compte de la rotation des
valeurs), et ce sera donc la condition correspondant à une file vide. Le tableau ne sera jamais
rempli au maximum pour pouvoir distinguer le cas d’une file vide et le cas d’une file pleine.
Nous placerons donc dans le tableau au maximum nbMaxÉlément éléments (en laissant un
élément « vide » entre les indices dernier et premier).
Exercice 3 Le monte-charge
Un monte-charge de chantier assure le transport de personnes et de matériel entre deux niveaux.
Lorsque le monte-charge arrive à un étage, tous ses passagers en sortent. La charge maximale
admise a la valeur MAX (donnée en paramètre). Étant donné les risques liés à l’utilisation du
monte-charge en surcharge, le poids de chacun des passagers et des charges qu’ils transportent
(outils, brouette de sable, ...) est vérifié avant l’entrée dans le monte-charge.
Pour gérer l’embarquement dans le monte-charge, on souhaite faire appel à un algorithme
« embarquement » qui détermine combien de personnes qui se trouvent actuellement en file
devant le monte-charge peuvent y entrer.
Cet algorithme respectera l’ordre d’arrivée des personnes et mettra à jour la file des personnes
en attente qu’il aura reçue en paramètre.
1. Choisissez une représentation de données adaptée à la solution du problème et justifiez

votre choix.
2. Écrivez l’algorithme « embarquement »
3. Écrivez l’algorithme « arrivée » qui ajoute à la file une personne d’un poids donné en
paramètre.
4. Quels cas doit-on envisager ?
Exercice 4 À l’envers
Écrire un algorithme recevant en paramètre une file d’entiers. À l’issue de cet algorithme, les
valeurs de la file seront en ordre inverse et débarrassées des éléments pairs.
Exemple : Si le contenu de la file est le suivant :
1 → 0 → 4 → 25 → 20 → 11 → 3 → 7 → 8 → 73 → 2 → 4
son contenu sera après traitement :
73 → 7 → 3 → 11 → 25 → 1
67
Chapitre
7 La récursivité
« Pour comprendre le principe de récursivité,

il faut d’abord comprendre le principe de récursivité »
7.1 Introduction
Une procédure est dite récursive lorsque dans sa description, une des étapes de cette procédure
est la procédure elle-même. Des termes synonymes de la récursivité sont la récurrence ou
l’auto-référence.
La récursivité est une démarche qui consiste à faire référence à ce qui fait l’objet de la démarche,
ainsi c’est le fait de décrire un processus dépendant de données en faisant appel à ce même
processus sur d’autres données plus « simples », de montrer une image contenant des images
similaires, de définir un concept en invoquant le même concept. (Wikipédia, août 2013)
Les illustrations ci-dessous sont des exemples célèbres de dessins récursifs :
La vache qui rit qui orne la fameuse boite de fromage porte des boucles d’oreilles en forme
de boites de fromage identiques au dessin entier. Il en est de même pour le dessin de la boite
de cacao Droste : sur le plateau porté par la dame apparait en plus petit la même boite de
cacao. Dans le troisième dessin, chaque carré contient un carré plus petit inscrit dans le carré
précédent de telle sorte que l’image formée à partir du 3e carré est identique au carré de départ,
mais réduite de 50%. Chacun de ces dessins s’auto-contient donc à une échelle plus petite. Il
en est de même pour le dessin fractal en haut de ce chapitre, il s’agit du triangle de Sierpinski
formé dans chaque coin de triangles plus petits mais pareils au triangle entier.
69
7.2. DÉFINITIONS RÉCURSIVES
7.2 Définitions récursives

Les dessins ci-dessus offrent des exemples de récursivité infinie. En mathématique et en infor-
matique, la récursivité définit plutôt un processus dont la description se décompose en un (ou
plusieurs) cas de base, et un ensemble de règles réduisant les autres cas aux cas de base par
l’exécution d’un nombre fini d’étapes.
Certains concepts peuvent se définir récursivement, à condition que la définition contienne une
clause d’évaluation immédiate sans appel récursif.
. Prenons par exemple la formule récursive de la factorielle :
n! = n ∗ (n − 1)!
Cette formule est incomplète si on ne définit pas le cas initial
0! = 1
À partir du cas de base et de la formule récursive, on peut calculer la factorielle de

n’importe quel nombre naturel.
. Parmi les autres exemples rencontrés au cours de mathématique, citons la formule récur-
sive des coefficients binomiaux :
p−1 p
Cnp = Cn−1 + Cn−1 si 0 < p < n
avec les cas de base :
Cn0 = 1 et Cnn = 1
Cette définition permet de reconstruire facilement le triangle de Pascal (où n est l’indice
de ligne (on démarre avec n = 0) et p l’indice de l’élément à calculer dans cette ligne, le
premier élément de la ligne est d’indice p = 0). :
Noter que le calcul récursif est plus commode d’utilisation que la formule « directe »
faisant intervenir les factorielles :
n!
Cnp = (n−p)!p!
. Un troisième exemple est la formule récursive pour calculer les nombres de Fibonacci :
Fn = Fn−1 + Fn−2
avec les cas initiaux

F0 = 0 et F1 = 1
70
7.3. ALGORITHME RÉCURSIF
Cette formule récursive est bien plus maniable que la formule donnant « directement » le
nombre d’indice n de la suite de Fibonnacci (avec l’indice n = 0 pour le premier élément) :
√ √
Fn = √1 ( 1+ 5 )n − √1 ( 1− 5 )n
5 2 5 2
. On peut aussi définir de façon récursive certaines structures courantes en informatique,

comme le montre par exemple cette définition récursive de la liste chainée :
une liste chainée est un ensemble soit vide, soit composé d’un élément auquel est attaché
une liste chainée.
Cette définition est intelligible par le fait qu’on sous-entend que la liste chainée à laquelle
la définition fait référence n’est plus identique à la première, mais plus petite d’un élément,
et éventuellement qu’elle peut se terminer (ensemble vide).
On peut, de façon semblable, définir une chaine de caractères :
une chaine de caractères est un ensemble soit vide, soit composé d’un caractère concaténé
à une chaine de caractères.
7.3 Algorithme récursif

En informatique, un algorithme récursif est un algorithme qui, lors de son exécution, fait
appel une ou plusieurs fois à lui-même. Ainsi, dans un algorithme récursif, nous pourrons écrire
parmi les instructions l’appel à cet algorithme lui-même :
void récursif(...)
// instructions
récursif(...)
// instructions
Si cette situation peut surprendre au premier abord, elle n’est pourtant pas très différente de
la situation suivante, appelée récursivité croisée :
void premier(...)
// instructions
second(...)
// instructions
void second(...)
// instructions
premier(...)
// instructions
Chaque algorithme fait appel à l’autre, et si on recopie le code de l’algorithme second à la

place de son appel dans premier, on obtient la même situation que dans l’algorithme récursif
qui précède. Néanmoins, en absence de paramètres, ces deux situations génèrent un processus
infini, et pire, une saturation de la mémoire lorsqu’on les implémente et les exécute sur une
machine ! En effet, pour pouvoir fonctionner, chaque appel de l’algorithme se traduira par
un nouvel appel de fonction qui, en plus de générer un nouvel ensemble de variables locales,
nécessitera aussi notamment de mémoriser pour chaque appel récursif l’adresse de retour de la
prochaine instruction à exécuter dans le code appelant (après exécution de la fonction appelée
récursivement) 1 . La situation est donc très différente d’une boucle infinie du type tant que ou
faire jusqu’à ce que.
1. et ce même si cette exécution de fonction ne se termine a priori jamais
71
7.4. UN GRAND EXEMPLE CLASSIQUE DE PROGRAMMATION RÉCURSIVE : LA
FACTORIELLE
Pour ne pas tomber dans ce processus sans fond, un algorithme récursif bien écrit doit forcément
posséder un (ou plusieurs) paramètre(s), et contenir une structure alternative qui conduit à une
clause d’évaluation immédiate de l’appel récursif pour une (ou plusieurs) valeur(s) initiale(s)
du(des) paramètre(s).
La forme générale est la suivante :
void récursif(paramètre)
if paramètre == valeur initiale
// il peut y avoir plusieurs cas initiaux
// instructions sans appel récursif.
else
// instructions menant à des valeurs différentes du paramètre,
// et après un nombre fini d’appels récursifs aux valeurs initiales.
7.4 Un grand exemple classique de programmation récursive : la

factorielle
L’algorithme récursif calculant la factorielle d’un entier positif est issu directement de la défi-
nition récursive rappelée ci-dessus :
int factorielle(int n)
if n == 0
return 1
else
return n * factorielle(n - 1)
Comment cela fonctionne-t-il ?

Par exemple, si l’algorithme est appelé avec la valeur 3 du paramètre, il doit multiplier par 3 le
résultat de la factorielle de 2. Le calcul est donc mis en attente jusqu’à ce que la factorielle de
2 soit connue ; et il en est de même pour le calcul de factorielle de 2, qui appelle la factorielle
de 1 qui à son tour appelle la factorielle de 0. À ce moment, la valeur 1 est retournée, et les
renvois se font en cascade jusqu’au premier appel qui peut enfin retourner la valeur 6.
7.5 Exercices
Dans les exercices suivants, il faudra parfois écrire un « algorithme façade », c’est-à-dire
un algorithme initial non récursif dans lequel les paramètres sont initialisés et qui appelle la
première fois l’algorithme récursif. Il est intéressant aussi de comparer chaque problème avec
sa solution itérative – lorsqu’elle existe – et de s’interroger sur la solution la plus efficace.
Exercice 1 La somme des premiers entiers positifs

Adaptez l’algorithme de la factorielle récursive (présenté ci-dessus) pour calculer la somme des
n premiers entiers strictement positifs.
72
7.5. EXERCICES
Exercice 2 affichage des n+1 premiers entiers positifs

Écrivez une algorithme récursif (pas de boucle) reçevant l’entier positif n en paramètre et qui
affiche tous les nombres entiers de n à 0 (inclus) puis tous les nombres entiers positifs de 0 à
n (inclus).
Exercice 3 Y a-t-il un zéro ?

Écrivez un algorithme récursif (pas de boucle) pour vérifier si un nombre entier (strictement
positif) donné en paramètre contient un chiffre 0. Votre algorithme retournera T rue s’il y a
un 0 dans le nombre et F alse sinon.
Exercice 4 Le plus grand commun diviseur

L’algorithme d’Euclide permet de calculer rapidement le PGCD de 2 nombres. Il peut se définir
de la façon suivante :
. PGCD(a, 0) = a
. PGCD(a, b) = PGCD(b, a MOD b) si b 6= 0
Écrire un algorithme récursif pour le calcul du PGCD. Cet algorithme générera une erreur si
un des 2 nombres est négatif.
Exercice 5 Taille d’une liste chainée

Écrire un algorithme récursif qui calcule la taille d’une liste chainée. Comparez la version
procédurale et la version orientée objet de cet algorithme.
Exercice 6 Le tableau symétrique

Écrire l’algorithme qui vérifie si le contenu d’un tableau est symétrique (c’est-à-dire si le
premier élément est égal au dernier , le second à l’avant-dernier, et ainsi de suite).
Exercice 7 Les nombres de Fibonacci

Écrire l’algorithme récursif permettant de calculer le n-ième nombre de Fibonacci, issu de la
définition récursive donnée dans ce chapitre. Combien de fois l’algorithme est-il exécuté pour
le calcul de F5 ? de F6 ?
Adapter l’algorithme pour que le nombre total d’appels récursifs s’affiche à l’issue du calcul.
Exercice 8 Division entière

Écrire un algorithme qui calcule la division entière de 2 entiers positifs de manière récursive ;
les seuls opérateurs arithmétiques autorisés sont l’addition et la soustraction.
Exercice 9 Recherche dichotomique

Écrire une version récursive de l’algorithme de recherche dichotomique dans un tableau ordonné
d’éléments de type T. Cet algorithme reçoit en paramètre le tableau, la valeur recherchée, et
retourne un booléen indiquant si la valeur se trouve dans le tableau. Dans l’affirmative, la
position de la valeur recherchée est renvoyée dans un paramètre en sortie (paramètre modifié
par effet de bord et identifié par une flèche ↑ dans la signature).
73
Chapitre
8 Mises en pratique
Nous voici arrivés au terme de ce cours d’algorithmique. Ce chapitre apporte une synthèse des
différentes notions vues tout au long de vos cours d’algorithmiques de 1re année et propose
quelques pistes de réflexion quant au choix d’une bonne représentation des données qui se pose
lors de la résolution de problèmes de programmation avancés.
Pour la plupart de ces exercices, la difficulté tient en partie dans le bon choix d’une repré-
sentation des données et de la démarche algorithmique la plus adéquate à mettre en œuvre
pour agir sur ces données en vue d’obtenir le résultat escompté. Noter que l’efficacité d’un
algorithme est liée étroitement au choix de la représentation.
8.1 Se poser les bonnes questions

Revenons à la case départ : nous avons commencé le cours d’algorithmique d’ALG1 en situant
les notions de problème et de résolution. Nous avons vu qu’un problème bien spécifié s’inscrit
dans le schéma :
étant donné [la situation de départ] on demande [l’objectif]
Une fois le problème correctement posé, on peut partir à la recherche d’une méthode de
résolution, c’est-à-dire d’un algorithme en ce qui concerne les problèmes à résoudre par les
moyens informatiques.
Tout au long de l’année, nous avons vu divers modèles et techniques algorithmiques adaptés
à des structures particulières (les nombres, les chaines, les tableaux, les objets, les listes. . .).
La plupart des exercices portaient directement sur ces structures (par ex. calculer la somme
des nombres d’un tableau, extraire une sous-liste à partir d’une liste donnée). Ces exercices
d’entrainement et de formation quelque peu théoriques constituent en fait des démarches al-
gorithmiques de base qui trouvent toutes une place dans des problèmes plus complexes.
Mais la plupart des problèmes issus des situations de la vie courante auxquels se confronte le
programmeur s’expriment généralement de manière plus floue : par ex. dresser la comptabilité
des dépenses mensuelles d’une firme, faire un tableau récapitulatif du résultat des élections
par cantons électoraux, faire une version informatique d’un jeu télévisé. . . Les exemples sont
infinis !
C’est dans le cadre de ce genre de problème plus complexe que se pose le problème de la
représentation de données. Une fois le problème bien spécifié (par les données et l’objectif)
apparaissent naturellement les questions suivantes : quelles données du problème sont réelle-
ment utiles à sa résolution ? (Il est fréquent que l’énoncé d’un problème contienne des données
superflues ou inutiles). Y a-t-il des données plus importantes que d’autres ? (données princi-
pales ou secondaires). Les données doivent-elles être consultées plusieurs fois ? Quelles données
faut-il conserver en mémoire ? Sous quelle forme ? Faut-il utiliser un tableau ? Une liste ? Faut-
il créer une nouvelle classe ? Les données doivent-elles être classées suivant un critère précis ?
Ou la présentation brute des données suffit-elle pour solutionner le problème posé ?
Les réponses ne sont pas directes, et les différents outils qui sont à notre disposition peuvent
être ou ne pas être utilisés. Il n’y a pas de règles précises pour répondre à ces questions, c’est le
75
8.2. LES STRUCTURES DE DONNÉES
flair et le savoir-faire développés patiemment par le programmeur au fil de ses expériences et

de son apprentissage qui le guideront vers la solution la plus efficace. Parfois plusieurs solutions
peuvent fonctionner sans pouvoir départager la meilleure d’entre elles.
Ce type de questionnement est peut-être l’aspect le plus délicat et le plus difficile de l’activité
de programmation, car d’une réponse appropriée dépendra toute l’efficacité du code développé.
Un mauvais choix de représentation des données peut mener à un code lourd et maladroit. En
vous accompagnant dans la résolution des exercices qui suivent, nous vous donnerons quelques
indices et pistes de réflexion, qui seront consolidées par l’expérience acquise lors des laboratoires
de langages informatiques ainsi que par les techniques de modélisation vues au cours d’analyse.
8.2 Les structures de données

Rappelons brièvement les différentes structures étudiées dans ce cours :
. les données « simples » (variables isolées : entiers, réels, chaines, caractères, booléens) ;
. le tableau, qui contient un nombre déterminé de variables de même type, accessibles via
un indice ou plusieurs pour les tableaux multidimensionnels ;
. les objets, combinant une série d’attributs et des méthodes agissant sur ces attributs ;
. la liste, qui peut contenir un nombre indéfini d’éléments de même type.
Chacune de ces structures possède ses spécificités propres quant à la façon d’accéder aux
valeurs, de les parcourir, de les modifier, d’ajouter ou de supprimer des éléments à la collection.
D’autres structures particulières s’ajouteront dans le cours d’algorithmique d’ALG3 : les listes
chainées, les piles, les files, les arbres, les associations et les graphes.
8.3 Exercices
Exercice 1 La course à la case 64 à 4 joueurs

Commençons par un petit jeu très simple de course avec un dé, dont voici les règles.
« Ce jeu se joue à 4 joueurs qui doivent parcourir un chemin de 64 cases. Ils

commencent tous sur la case 1 et jouent à tour de rôle (en commençant par le
premier joueur). À son tour, le joueur lance un dé à 6 faces et avance du nombre
de cases indiqué par le dé. Le premier joueur à atteindre ou dépasser la case 64
a gagné. Seule contrainte, un joueur ne peut pas terminer son tour sur une case
occupée. Si c’est le cas, il avance jusqu’à la case libre suivante. »
Voici 3 propositions de représentation de données. On vous demande pour chaque proposition

de vérifier, sans écrire l’algorithme, si elle permet la programmation du jeu. On vous conseille
vivement de « dessiner » 1 les propositions pour mieux les comprendre.
1. Un tableau de 64 entiers. La case k contient i si le joueur i s’y trouve ou 0 si la case est

libre. Mais aussi un entier joueurCourant donnant le numéro du joueur courant.
2. Un tableau de 4 entiers. La case i contient la position du joueur i. Mais aussi un entier
joueurCourant donnant le numéro du joueur courant.
3. On combine les deux premières propositions (on a donc deux tableaux).
Après ces vérifications vous choisirez une des représentations pour écrire la solution (non OO
à ce stade) du jeu. Pensez à découper votre solution.
Exercice 2 La course à la case 64 à n joueurs

1. Par là, on veut dire : imaginer une situation de jeu (positions des joueurs sur le chemin par exemple)
et voir quelles valeurs doivent avoir les variables introduites dans la représentation pour correspondre à cette
situation de jeu.
76
8.3. EXERCICES
Modifiez l’exercice précédent afin que le jeu puisse se jouer à n joueurs, où n est un entier
supérieur ou égal à 2, choisi au début du jeu.
Exercice 3 La course à la case 64 à n joueurs - variantes

Reprenons la course à la case 64 de l’exercice précédent. Voici quelques propositions de modifi-
cation des règles. Pour chaque proposition, indiquez si la représentation choisie dans l’exercice
précédent est toujours valable et pertinente.
1. Si un joueur arrive sur une case occupée, le joueur qui s’y trouvait retourne à la première
case.
2. Si un joueur termine sa course sur une case qui est un multiple de 5, il rejoue directement.
3. Un joueur rejoue directement s’il termine sa course sur les cases 1, 2, 7, 11, 17, 31, 42 ou
53.
Exercice 4 Un jeu de poursuite

Deux joueurs A et B se poursuivent sur un circuit de 50 cases. Au départ, A se trouve sur la
case 1 et B est placé sur la case 26. C’est A qui commence. Chaque joueur joue à son tour
en lançant un dé dont la valeur donne le nombre de cases duquel il doit avancer sur le jeu.
Lorsqu’un joueur arrive sur la case 50 et qu’il doit encore avancer, il continue son parcours à
partir de la case 1. Le jeu se termine lorsqu’un joueur rattrape ou dépasse l’autre.
Écrire un algorithme (non OO pour le moment) de simulation de ce jeu qui se terminera par
l’affichage du vainqueur ainsi que le nombre de tours complets parcourus par ce vainqueur.
Il est important de bien découper votre algorithme. On vous suggère d’écrire les algorithmes
suivant :
. un algorithme initialiser() qui initialise le jeu (placement des joueurs. . .) ;
. un algorithme « jouerCoup » qui joue pour un joueur et indique s’il a rattrapé l’autre
joueur ;
. un algorithme « joueurSuivant » qui permet de passer au joueur suivant.
À nouveau, on vous fait plusieurs propositions pour la représentation de l’état du jeu. On vous
demande pour chacune d’elles de vérifier, sans écrire les méthodes de la classe, si elles per-
mettent la programmation du jeu. Après ces vérifications vous choisirez une des représentations
pour écrire la classe complète.
1. Dans cette proposition, nous avons deux variables.

. circuit : un tableau de 1 à 50 chaines de caractères. Les chaines de caractères re-
présenteront la position des joueurs (au départ, "A" en 1 et "B" en 26, " " dans les
autres positions).
. joueurCourant : un entier donnant la position du joueur courant.
2. Cette proposition introduit une classe Joueur et le nombre de tours.
. circuit : un tableau de 1 à 50 éléments de Joueur :
class Joueur
private :
string nom // Le nom du joueur à cette position ("A", "B" ou " " si la case est vide)
int nbTours // Nb de tours qu’a fait le joueur qui est à cette position (0 si case vide)
public :
// Constructeurs et accesseurs
Un joueur a fait un tour complet quand il est de nouveau sur sa position de départ
ou la dépasse.
3. Dans cette proposition, le tableau change de signification.
77
8.3. EXERCICES
. circuit : un tableau de 2 éléments Joueur, une classe différente.
class Joueur
private :
int position // Donne la position du joueur sur le circuit (entier entre 1 et 50)
int nbTours // Le nombre de tours qu’a fait ce joueur
public :

4. Cette proposition est identique à la précédente sauf sur un point :
. On ne retient plus le nombre de tours effectués mais simplement le nombre de cases
parcourues. Par exemple, si un joueur a fait exactement deux tours complets, le
nombre de cases parcourues sera de 100.
class Joueur
private :
int position // Donne la position du joueur sur le circuit (entier entre 1 et 50)
int nbCasesParcourues // Nb de cases parcourues par le joueur depuis le départ
public :
Exercice 5 Un jeu de poursuite - variante

Dans cette variante, chaque case contient une valeur vrai ou faux indiquant si le joueur pourra
rejouer. Si la case sur laquelle tombe le joueur contient la valeur vrai il avance encore une fois
du même nombre de cases (et de même s’il tombe encore sur vrai).
Qu’est-ce que cela change au niveau des données ? Modifiez votre solution en conséquence.
Pour adapter le code, il faudra adapter les paramètres fournis à l’algorithme d’initialisation et à
l’algorithme qui joue un coup. Nous vous conseillons également de ne pas modifier l’algorithme
jouerCoup mais d’introduire un nouvel algorithme (par ex. jouerTour) qui y fait appel plusieurs
fois si nécessaire.
Exercice 6 Le Jeu du Millionnaire

Un questionnaire de quinze questions à choix multiples de difficulté croissante est soumis à
un candidat. Quatre possibilités de réponses (dont une seule est correcte) sont proposées à
chaque fois. Au plus le candidat avance dans les bonnes réponses, au plus son gain est grand.
S’il répond correctement aux quinze questions, il empoche la somme rondelette de 500.000 €.
Par contre, si le candidat donne une mauvaise réponse, il risque de perdre une partie du gain
déjà acquis. Cependant, certains montants intermédiaires constituent des paliers, c’est-à-dire
une somme acquise que le candidat est sûr d’empocher, quoiqu’il arrive dans la suite du jeu.
À chaque question, le candidat a donc trois possibilités :
. il donne la réponse correcte : dans ce cas il augmente son gain, et peut passer à la question
suivante
. il ne connait pas la réponse, et choisit de s’abstenir : dans ce cas, le jeu s’arrête et le
candidat empoche le gain acquis à la question précédente
. il donne une réponse incorrecte : le jeu s’arrête également, mais le candidat ne recevra que
le montant du dernier palier qu’il a atteint et réussi lors de son parcours. En particulier,
si le candidat se trompe avant d’avoir atteint le premier palier, il ne gagne pas un seul
euro !
78
8.3. EXERCICES
1 25 € faux Exemple : Le tableau ci-contre contient les gains associés à chaque

2 50 € faux question et une indication booléenne mise à vrai lorsque la question
3 125 € faux constitue un palier. Un concurrent qui se trompe à la question 3
4 250 € faux
5 500 € vrai
ne gagnera rien ; un concurrent qui se trompe à la question 6
6 1000 € faux gagnera 500 € (palier de la question 5) et de même s’il se trompe
7 2000 € faux à la question 10 ; un concurrent qui se trompe à la question 13
8 3750 € faux gagnera 12500 € (palier de la question 10) ; s’il décide de ne pas
9 7500 € faux répondre à la question 13, il garde le montant acquis à la question
10 12500 € vrai
11 25000 € faux
12, soit 50000 €.
12 50000 € faux
13 100000 € vrai
14 250000 € faux
15 500000 € vrai
Il y aurait de nombreuses façons de coder ce problème ; en voici une :

La classe Question
Une question est composée du libellé de la question, des 4 libellés pour les réponses et d’une
indication de la bonne réponse (un entier de 1 à 4).
La classe Gain
Représente un niveau de gain. Elle contient les attributs : montant (entier) et palier (un booléen
à vrai si cette somme est assurée, faux sinon).
La classe Millionnaire
Cette classe code le moteur du jeu. On y retrouve :
. questionnaire : un tableau de Question
. gains : un tableau de Gain
. autres attributs à déterminer (cf. méthodes)
ainsi que les méthodes pour :
. initialiser le jeu à partir d’un questionnaire et du tableau de gains
. connaitre la question en cours
. donner la réponse du candidat à la question en cours
. savoir si le jeu est fini ou pas
. arrêter le jeu en repartant avec les gains
. les accesseurs nécessaires pour connaitre l’état du jeu.
Le jeu proprement dit
L’algorithme jeuMillionaireConsole() reçoit le questionnaire et les gains et simule le jeu :
. Il propose les questions au candidat
. Il lit ses réponses (chiffre 1 à 4 ou 0 pour arrêter) et fait évoluer le jeu en fonction.
. lorsque le jeu est terminé, il indique au candidat le montant de ses gains.
. Attention ! Cet algorithme devrait être le plus petit possible. Imaginez que vous devez
également coder une version graphique. Tout code commun doit se trouver dans la classe
Millionnaire !
Exercice 7 Chambre avec vue

Un grand hôtel a décidé d’informatiser sa gestion administrative. Il a confié ce travail à la
société ESI_INFO dans laquelle vous êtes un informaticien chevronné. On vous a confié la
tâche particulière de la gestion des réservations pour ses 100 chambres. Pour ce faire, on vous
demande d’écrire une classe Hôtel qui offre notamment une méthode qui permet d’enregistrer
une réservation.
79
8.3. EXERCICES
Pour représenter l’occupation des chambres un jour donné, nous allons utiliser un tableau de
100 entiers. Un 0 indique que la chambre est libre, une autre valeur (positive) indique le numéro
du client qui occupe cette chambre ce jour-là.
Nous utiliserons une Liste de tels tableaux pour représenter l’occupation des chambres sur une
longue période ; les éléments se suivant correspondant à des jours successifs.
Nous vous imposons les attributs de la classe, à savoir :
. occupations : une Liste de tableaux de 100 entiers comme expliqué ci-dessus.
. premierJour : donne le jour concerné par le premier élément de la liste. Ainsi s’il vaut
10/9/2015 cela signifie que le premier élément de la liste « occupations » renseigne sur
l’occupation des chambres ce 10/9/2015 ; que le deuxième élément de la liste concerne le
11/9/2015 et ainsi de suite...
Écrire la méthode suivante :
int effectuerRéservation(demande : DemandeRéservation)
. Elle retourne le numéro de la chambre qui a été choisie ou −1 si la réservation n’a pas
pu se faire.
. Si plusieurs chambres sont libres, on choisit celle avec le plus petit numéro.
. La demande de réservation peut couvrir une période qui n’est pas encore reprise dans la
liste ; il faudra alors l’agrandir.
. Vous pouvez supposer qu’il existe une méthode donnant le nombre de jours séparant deux
dates données.
La classe de demande de réservation est définie ainsi :
class DemandeRéservation
private :
int numéroClient
Date débutRéservation
int nbNuitées
public :
Exercice 8 L’ensemble
La notion d’ensemble fini est une notion qui vous est déjà familière pour l’avoir rencontrée
dans plusieurs cours. Nous rappelons certaines de ses propriétés et opérations.
Étant donnés deux ensembles finis S et T ainsi qu’un élément x :
. x ∈ S signifie que l’élément x est un élément de l’ensemble S.
. L’ensemble vide, noté ∅ est l’ensemble qui n’a pas d’élément (x ∈ ∅ est faux quel que soit
x ).
. L’ordre des éléments dans un ensemble n’a aucune signification, l’ensemble {1,2} est
identique à {2,1}.
. Un élément x ne peut pas être plus d’une fois élément d’un même ensemble (pas de
répétition).
. L’union S ∪ T est l’ensemble contenant les éléments qui sont dans S ou (non exclusif)
dans T.
. L’intersection S ∩ T est l’ensemble des éléments qui sont à la fois dans S et dans T.
. La différence S \ T est l’ensemble des éléments qui sont dans S mais pas dans T.
Créer la classe Ensemble décrite ci-dessous (où E est le type des éléments de l’ensemble).
80
8.3. EXERCICES
class Ensemble de E
public :
void Ensemble de E() // construit un ensemble vide
void ajouter(E élt) // ajoute l’élément à l’ensemble
void enlever(E élt)) // enlève un élément de l’ensemble
boolean contient(E élt) // dit si l’élément est présent
boolean estVide() // dit si l’ensemble est vide
int taille() // donne la taille de l’ensemble
Ensemble de E union(Ensemble de E autreEnsemble)
Ensemble de E intersection(Ensemble de E autreEnsemble)
Ensemble de E moins(Ensemble de E autreEnsemble)
List of E éléments() // conversion en liste
Quelques remarques :
. La méthode d’ajout (resp. de suppression) n’a pas d’effet si l’élément est déjà (resp. n’est
pas) dans l’ensemble.
. Les méthodes union(), intersection() et moins() retournent un troisième ensemble, résultat
des 2 premiers sans toucher à ces 2 ensembles. On aurait pu envisager des méthodes
modifiant l’ensemble sur lequel on les appelle.
. La méthode éléments() est nécessaire si on veut parcourir les éléments de l’ensemble (par
exemple pour les afficher).
Exercice 9 La course à la case 64 en version OO

Reprenez la solution que vous avez écrite pour l’exercice 2 (La course à la case 64 à n joueurs)
et voyez comment le transformer pour en faire une version OO.
Exercice 10 Un jeu de poursuite en version OO

Reprenez la solution que vous avez écrite pour l’exercice 5 (Un jeu de poursuite - variante) et
voyez comment le transformer pour en faire une version OO.
Exercice 11 Les congés

Les périodes de congés des différents employés d’une firme sont reprises dans un tableau booléen
Congés bidimensionnel à n lignes et 366 colonnes. Chaque ligne du tableau correspond à
un employé et chaque colonne à un jour de l’année. Une case est mise à vrai si l’employé
correspondant est en congé le jour correspondant. La firme en question est opérationnelle 7
jours sur 7, on n’y fait donc pas de distinction entre jours ouvrables, week-end et jours fériés.
Ce tableau permet de visualiser l’ensemble des congés des travailleurs, et d’accorder ou non
une demande de congé, suivant les règles suivantes :
1. une période de congé ne peut excéder 15 jours ;
2. un employé a droit à maximum 40 jours de congé par an ;
3. à tout moment, 50% des employés doivent être présents dans la firme.
Écrire un algorithme qui détermine si cette demande peut être accordée ou non à un employé
dont on connait le nom, ainsi que les dates de début et de fin d’une demande de congé (objets
de la classe Date). Dans l’affirmative, le tableau Congés sera mis à jour.
Pour établir la correspondance entre ce tableau et les noms des employés, vous avez à votre
disposition un tableau Personnel de chaines. L’emplacement du nom d’un employé dans ce
tableau correspond à l’indice ligne du tableau Congés.
Il est permis d’utiliser pour résoudre cet exercice la méthode suivante de la classe Date, sans
devoir détailler son code :
int numéroJour() // la position du jour dans l’année (entre 1 et 366)
81
8.3. EXERCICES
Exercice 12 Casino
Pour cet exercice, on vous demande un petit programme qui simule un jeu de roulette très
simplifié dans un casino.
Dans ce jeu simplifié, vous pourrez miser une certaine somme et gagner ou perdre de l’argent
(telle est la fortune, au casino !). Quand vous n’avez plus d’argent, vous avez perdu.
Notre règle du jeu
Bon, la roulette, c’est très sympathique comme jeu, mais un peu trop compliqué pour un
exercice de première année. Alors, on va simplifier les règles et je vous présente tout de suite
ce que l’on obtient :
. Le joueur mise sur un numéro compris entre 0 et 49 (50 numéros en tout). En choisissant
son numéro, il y dépose la somme qu’il souhaite miser.
. La roulette est constituée de 50 cases allant naturellement de 0 à 49. Les numéros pairs
sont de couleur noire, les numéros impairs sont de couleur rouge. Le croupier lance la
roulette, lâche la bille et quand la roulette s’arrête, relève le numéro de la case dans
laquelle la bille s’est arrêtée. Dans notre programme, nous ne reprendrons pas tous ces
détails « matériels » mais ces explications sont aussi à l’intention de ceux qui ont eu la
chance d’éviter les salles de casino jusqu’ici. Le numéro sur lequel s’est arrêtée la bille
est, naturellement, le numéro gagnant.
. Si le numéro gagnant est celui sur lequel le joueur a misé (probabilité de 1/50, plutôt
faible), le croupier lui remet 3 fois la somme misée.
. Sinon, le croupier regarde si le numéro misé par le joueur est de la même couleur que le
numéro gagnant (s’ils sont tous les deux pairs ou tous les deux impairs). Si c’est le cas, le
croupier lui remet 50% de la somme misée. Si ce n’est pas le cas, le joueur perd sa mise.
Dans les deux scénarios gagnants vus ci-dessus (le numéro misé et le numéro gagnant sont
identiques ou ont la même couleur), le croupier remet au joueur la somme initialement misée
avant d’y ajouter ses gains. Cela veut dire que, dans ces deux scénarios, le joueur récupère de
l’argent. Il n’y a que dans le troisième cas qu’il perd la somme misée.
Comme vous pouvez le constater, on ne vous fait pas de proposition pour la représentation
des données. À vous de jouer !
Exercice 13 Mots croisés

Voici une grille de mots croisés. (on ne s’intéresse pas ici aux définitions). Écrire une classe
Grille offrant les méthodes suivantes :
. placer une lettre à un endroit de la grille (une case non noire bien sûr) ;
. donner le nombre de cases noires sur la grille ;
. donner le nombre total de mots (plus d’une lettre) de la grille (donc y compris ceux que
le joueur n’a pas encore complétés) ;
. donner le nombre de mots déjà complétés par le joueur.
Exemple : dans la grille ci-contre, le

A
nombre de cases noires est 14, le nombre L
total de mots de la grille est 37 (19 ho- L O G I Q U E
rizontaux et 18 verticaux) et le nombre O
de mots déjà complétés par le joueur est R
6. E S I O H
T A B L E A U
H J B
M E
E T
82
8.3. EXERCICES
Exercice 14 Puissance 4
Le jeu de puissance 4 se déroule dans un tableau vertical comportant 6 rangées et 7 colonnes
dans lequel deux joueurs introduisent tour à tour des jetons (rouges pour l’un, jaunes pour
l’autre). Avec l’aide de la gravité, les jetons tombent toujours le plus bas possible dans les
colonnes où on les place. Le jeu s’achève lorsqu’un des joueurs a réussi à aligner 4 de ses jetons
horizontalement, verticalement ou en oblique, ou lorsque les deux joueurs ont disposé chacun
leur 21 jetons sans réaliser d’alignement (match nul).
N.B. : sur ce dessin noir et blanc, les jetons rouges apparaissent

en noir, les jetons jaunes en gris et les cases blanches désignent
l’absence de jetons. Cet exemple montre une situation du jeu où
le joueur « jaune » est gagnant. En introduisant un jeton dans la
4e colonne, il a réalisé un alignement de 4 jetons en oblique.
On demande d’implémenter une classe Puissance4 qui permette de contrôler l’état des diffé-
rentes phases du jeu. Déterminez les attributs de cette classe et décrivez-les brièvement de
manière à justifier votre choix. Dotez ensuite la classe des méthodes permettant de :
. savoir si la grille est pleine

. mettre la grille à jour lorsque le joueur n (1 ou 2) joue dans la colonne j (entre 1 et 7).
Cette méthode renverra la valeur booléenne faux si la colonne en question est déjà pleine
. vérifier si le joueur qui vient de jouer dans la colonne j a gagné la partie
N.B. : pour le contenu du tableau de jetons, vous pouvez adopter la convention suivante : 0
pour l’absence de jeton, 1 pour un jeton du 1er joueur et 2 un jeton du 2e joueur (on peut donc
faire abstraction de la couleur du jeton dans ce problème).
Exercice 15 Mastermind
Revenons sur le jeu Mastermind déjà vu en DEV2. Dans ce jeu, un joueur A doit trouver
une combinaison de k pions de couleur, choisie et tenue secrète par un autre joueur B. Cette
combinaison peut contenir éventuellement des pions de même couleur. À chaque proposition
du joueur A, le joueur B indique le nombre de pions de la proposition qui sont corrects et bien
placés et le nombre de pions corrects mais mal placés.
Exemple
Utilisons des lettres pour représenter les couleurs.
Combinaison secrète Proposition du joueur
R R V B J R V B B V
Il sera indiqué au joueur qu’il a :
. 2 pions bien placés : le R en 1re position et le second B en 4e position ;
. 1 pion mal placé : un des deux V (ils ne peuvent compter tous les deux).
Supposons une énumération Couleur (cf. la description d’une énumération en annexe) avec
toutes les couleurs possibles de pion.
a) Écrire une classe « Combinaison » pour représenter une combinaison de k pions. Elle
possède une méthode pour générer une combinaison aléatoire (que vous ne devez pas
écrire) et une méthode pour comparer une combinaison à la combinaison secrète (que
vous devez écrire)
b) Écrire ensuite une classe « MasterMind » qui représente le jeu et permet d’y jouer. La taille
de la combinaison et le nombre d’essais permis seront des paramètres du constructeur.
83
Compléments
Nous présentons ici quelques éléments qui pourront vous être utiles pour résoudre certains
exercices.
.1 Énumération
Parfois, une variable ne peut prendre qu’un ensemble fixe et fini de valeurs. Par exemple une
variable représentant une saison ne peut prendre que quatre valeurs (HIVER, PRINTEMPS,
ÉTÉ, AUTOMNE). On va l’indiquer grâce à l’énumération qui introduit un nouveau type
de donnée.
enum Saison { HIVER, PRINTEMPS, ÉTÉ, AUTOMNE }
Il y a deux avantages à cela : une indication claire des possibilités de la variable lors de la
déclaration et une lisibilité du code grâce à l’utilisation des valeurs explicites.
Par exemple,
// Lit une saison et affiche sa particularité

void particularitéSaisonnière()
Saison uneSaison
read uneSaison // on lira la valeur HIVER ou PRINTEMPS ou ÉTÉ ou AUTOMNE
if uneSaison = HIVER
print "il neige"
else if uneSaison = PRINTEMPS
print "les fleurs poussent"
else if uneSaison = ÉTÉ
print "le soleil brille"
else
print "les feuilles tombent"
Exercice 16 Autres situations

Pouvez-vous identifier d’autres données qui pourraient avantageusement s’exprimer avec une
énumération ?
Quid des langages de programmation ?

Certains langages (comme Java) proposent un type énuméré complet. D’autres (comme C et
C++) proposent un type énuméré incomplet mais qui permet néanmoins une écriture comme
celle ci-dessus. D’autres langages, enfin, ne proposent rien. Pour ces langages, le truc est de
définir des constantes entières qui vont permettre une écriture proche de celle ci-dessus (mais
sans une déclaration explicite).
Lien avec les entiers

Dans l’exemple ci-dessus, on lit une Saison mais souvent, si on travaille avec les Mois par
exemple, on disposera plutôt d’un entier. Il faut pouvoir convertir les valeurs. Chaque langage
de programmation propose sa propre technique ; nous allons adopter la syntaxe suivante :
85
.2. GESTION DES ERREURS
Saison(3) // donne l’énumération de la saison numéro 3 (on commence à 1) ;

// donne ÉTÉ dans notre exemple.
position(uneSaison) // donne l’entier associé à une saison ;
// si on a lu HIVER comme valeur pour uneSaison, donne la valeur 1.
.2 Gestion des erreurs

Lorsqu’un algorithme se trouve dans un état incorrect, particulièrement lorsqu’un paramètre
est invalide, on peut l’indiquer via la primitive error.
Par exemple :
void racineCarrée(int nb)

if nb<0
error "Le nombre doit être positif"
suite de l’algorithme
Pratiquement, cette primitive stoppe l’algorithme sans aucune possibilité de récupération.

Dans un langage comme Java vous utiliserez le mécanisme des exceptions qui est plus souple.
86
Notre pseudo-code
Dans le cadre de ce cours, nous vous proposons d’écrire un pseudo-code très inspiré du langage
Java : à gauche le pseudo-code de ALG2 à droite celui de ALG1.
. Déclarer une variable se fait comme en Java, avec les types de données du langage Java 2 :
int age
age : entier
float prix prix : réel
nom : chaîne
String nom ok : booléen
ALG1
Boolean ok
. L’assignation et l’égalité :
age = 20 age <— 20
nom = "Dimitri" nom <— "Dimitri"
ok <— age = 20
ok = age == 20 ALG1
. Pour un affichage, on n’écrira pas System.out.println("coucou"); mais simplement
écrire "coucou"
print "coucou"
ALG1
. Pour lire et écrire

read mot lire mot
écrire "coucou"
print "coucou" ALG1
. Déclarer une fonction/algorithme

int lancerDé(int min, max)
algorithme lancerDé(min, max : entier) -> entier
return <entier aléatoire entre min et retourner <un entier aléatoire entre min et max>
fin algorithme
max> ALG1
sans valeur de retour :

void afficher(String mot)
algorithme afficher(mot : chaîne)
écrire mot
fin algorithme
print mot ALG1
ou une méthode :
method T get(int pos) algorithme get(pos : entier) -> T
/* La classe a un attribut tab de type tableau de T */
return tab[pos] retourner tab[pos]
fin algorithme
ALG1
La distinction entre méthode et algorithme est qu’une méthode a accès aux attributs de
classe de l’objet courant en plus des paramètres explicites.
. Déclarer, instancier, initialiser, passer en paramètre un tableau :
tab : tableau de 5 entiers
pour i de 0 à tab.taille - 1
int[] tab = {1,2,3,4,5} tab[i] <— i+1
fin pour
ALG1
compteur : tableau de 10 entiers

int[10] compteurs
ALG1
2. Parfois les types sont écrits en français : entier, chaîne, tableau.
87
.3. EXEMPLE : UN MOT DANS UN MIROIR
int[] resultat resultat : tableau d’entier // resultat est uniquement déclaré

ALG1
void afficher(int[n] tab) algorithme afficher(tab : tableau d’entiers)

n <— tab.taille
...
... fin algorithme
ALG1
tab.length donnera la taille du tableau tab (remplacera tab.taille du cours d’ALG1)

int[n] tab dans le cas d’un paramètre, permet de recevoir le tableau et sa taille (n). C’est
une facilité d’écriture qui économisera l’utilisation de tab.length
En Java :

// int[] tab = {1,2,4,5,6}
int[] tab = {1,2,4,5,6};
// int[10] compteurs
int[] tab = new int[10];
// int[] resultat
int[] resultat;
// void afficher(int[n] tab)

void afficher(int[] tab) {
int n = tab.length;
}

. Les points-virgules sont généralement omis en fin d’instruction. Par contre l’indentation
revêt une importance capitale !
. Dans un appel dans méthode, les objets (aussi les tableaux) sont passés par référence, et
peuvent donc être modifiés par effet de bord. Les types primitifs sont passés par valeur.
.3 Exemple : un mot dans un miroir

Par exemple, lorsqu’il s’agit de construire le miroir d’un mot donné, l’algorithme peut être
décrit en des termes simples :
pour chaque lettre en partant de la dernière : afficher la lettre courante

langage naturel
Si on veut préciser un peu plus, on pourrait écrire en pseudo-code :
longueur <— <taille du mot>

for i from mot.length-1 to 0 by −1 pour i de longueur - 1 à 0 par -1
print <ième lettre de mot>. écrire <ième lettre de mot>
fin pour
ALG1
Pour ultimement arriver au code java suivant :

static void afficherMiroir(String mot) {
for (int i = mot.length() - 1; i >= 0; i--) {
System.out.print(mot.charAt(i));
}
}

Et au code Python suivant :
def afficherMiroir(mot) :
for i in range(len(mot)-1, -1,-1) :
print(mot[i])
88
.4. EXEMPLE : POSITION DES MINIMUMS.
.4 Exemple : Position des minimums.

L’exercice 22 p.65 du syllabus d’ALG1 demande de retourner un tableau des indices du mini-
mum à partir d’un tableau d’entiers reçu en paramètre. Réécrivons la solution de la version b de
la question où il était demandé de ne parcourir qu’une seule fois le tableau reçu en paramètre
en stockant dans une deuxième tableau les indices des plus petits éléments rencontrés (ce
tableau étant à chaque fois réinitialisé lorsqu’un nouveau minimum est rencontré).
int[] lesIndicesDuMinimum(int[n] monTab)
int[n] indiceMin
int posiMin = 0
int derniereCase = 0
indiceMin[0] = 0
if monTab.length >= 2
indiceMin[1] = -1
for i from 1 to monTab.length - 1
if monTab[i] < monTab[posiMin]
posiMin = i
reinitTab(indiceMin)
indiceMin[0] = i
derniereCase = 0
else if monTab[i] == monTab[posiMin]
derniereCase = derniereCase + 1
indiceMin[derniereCase] = i
return indiceMin
void reinitTab(int[n] tab)
for i from 0 to n-1

tab[i] = -1
void principal()
int[] tabEntier = {7,2,9,2,3,2,1,5,1,8}

int[] tabIndices = lesIndicesDuMinimum (tabEntier)
int i = 0
while i < tabIndices.length and tabIndices[i] != -1
print tabIndice[i]
i=i+1
89
Aide mémoire
Cet aide-mémoire peut vous accompagner lors d’une interrogation ou d’un examen. Il vous est
permis d’utiliser ces méthodes sans les développer. Par contre, si vous sentez le besoin d’utiliser
une méthode qui n’apparait pas ici, il faudra en écrire explicitement le contenu.
.5 Manipuler le hasard
double random() // Donne un nombre réel entre 0 inclus et 1 exclu.

double random(int n) // Donne un nombre entre 0 inclus et n exclu.
int random(int min, int max) // Donne un entier entre min et max inclus.
.6 La liste

interface List<T>
public :
void List<T>() // construit une liste vide (choisir ArrayList ou SinglyLinkedList)
T get(int pos) // donne un élément en position pos
void set(int pos, T value) // modifie un élément en position pos
void add(T value) // ajoute un élément en fin de liste
void add(int pos, T value) // insère un élément en position pos
void removePos(int pos) // supprime l’élément en position pos
boolean remove(T value) // supprime l’élément de valeur donnée
boolean contains(T value) // indique si un élément est présent
int indexOf(T value) // donne la position d’un élément
.7 ArrayList
class ArrayList<T>
private :
T[] tab // Le tableau contenant les données.
int size // La taille logique du tableau.
91
.8. SINGLYLINKEDLIST
.8 SinglyLinkedList
class SinglyLinkedList<T>
private :
Node head // Référence à la tête de liste.
// Node est une classe privée dans SinglyLinkedList

class Node
private :
T value // La valeur du noeud
Node next // Référence à l’élément suivant. null sinon
92

Syllabus 2023-2024

Transféré par

Droits d'auteur :

Formats disponibles

Syllabus 2023-2024

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Syllabus 2023-2024

Transféré par

Droits d'auteur :

Formats disponibles

Haute École Bruxelles-Brabant

École Supérieure d’Informatique

G. Cuvelier(CUV), A. Hallal(HAL), C. Leignel(CLG),

1 Algorithmes d’insertions et de recherches 1

3 Les tableaux à 2 dimensions 27

7.3 Algorithme récursif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

. inscrire un ou une étudiant·e ;

. registered : le tableau des numéros d’étudiants

Nous allons envisager deux cas :

1.1 Insertion dans un tableau non trié

L’algorithme est assez simple :

int register(int[n] registered, int nRegistered, int number)

1.1.2 Vérifier une inscription

int check(int[n] registered, int nRegistered, int number)

La désinscription de l’étudiant numéro 41390 donnerait ce qui suit.

int unsubscribe(int[n] registered, int nRegistered, int number)

1.2 Gestion des tableaux non triés

void initialiser(int[n] tab, int val)

int indexValue(int[n] is,int nValues, int value)

if nValues < taille du tableau AND indexValue = -1

void add(int[n] is, int nValues, int value)

index = l’index de la valeur à supprimer

void delete( int[n] is,int nValues,int value )

1.3 Insertion dans un tableau trié

— Qu’est-ce que ça change au niveau des algorithmes ?

1.3.1 Rechercher la position d’une inscription

int find(int[n] registered, int nRegistered, int number)

int findPosition(int[n] registered, int nRegistered, int number)

1.3.2 Inscrire un étudiant

int subscribe(int[n] registered, int nRegistered, int number)

int unsubscribe(int[n] registered, int nRegistered, int number)

1.4 Gestion des tableaux triés

index int findIndex( int[] is, int nValues, int value )

1. vérifier que la valeur n’est pas déjà présente ;

En décomposant le problème, voici une solution :

int add( int[] is, int nValues, int value )

int delete( int[] is, int nValues, int value )

public static void shiftLeft(int[] is, int begin, int end){

for (int i=begin; i <= end; i++){

1.4.4 Intérêt de trier les valeurs ?

1.5 La recherche dichotomique

Première étape : medianIndex = (0 + 19) DIV 2, c’est-à-dire 9.

Deuxième étape : medianIndex = (10 + 19) DIV 2, c’est-à-dire 14.

Quatrième étape : medianIndex = (12 + 13) DIV 2, c’est-à-dire 12 où se trouve la valeur

1 public static int binarySearch(int[] myArray, int value){

1.6 Introduction à la complexité

// Déclare un tableau et donne les 4 premières valeurs.

On peut compter 5 instructions élémentaires : une instanciation de tableau, et quatre assigna-

void initialiser(int[n] tab, int valeur)

le nombre d’instructions élémentaires dépend de la taille n du tableau. Il y aura au total n

void peutÊtreInitialisé(int[n] tab, int valeur)

le nombre d’instructions élémentaires dépend de la valeur donnée en paramètre. Si la valeur

Complexité dans le pire des cas

De manière générale, un algorithme a une complexité en O(f (n)) si le nombre d’instructions

L’arithmétique des grands O

Concaténation Lorsque l’on réalise l’algorithme A1 suivi de l’algorithme A2 , l’algorithme

Alternative Un algorithme tel que

a une complexité en O(max(g(n), f (n)) + h(n)).

a une complexité O(K × (h(n) + f (n))) où K est le nombre de tours de boucle.

Exercice 1 Calcul de complexités