Algorithmique

5. Les tableaux
Sommaire
I. Tableaux statiques

II. Tableaux dynamiques

III. Tri dans un tableau

IV. Recherche dans un tableau

2 Algorithmique ESI 2021-2022

Rappel
Rappel

 Algorithme informatique

 Suite d'instructions ordonnée qui décrit de façon

exhaustive les différentes étapes à suivre par un

processeur pour résoudre un problème donné en un

temps fini

4 Algorithmique ESI 2021-2022

Rappel

 Pseudo-code algorithmique

ALGORITHME nom_de_l’algorithme
<partie des déclarations>
DEBUT
<partie des instructions>
//commentaire
FIN

5 Algorithmique ESI 2021-2022

Rappel
 Un programme n’est pas purement séquentiel 
nécessité d’avoir des structures de contrôle

1. Les structures alternatives (tests)

2. Les structures itératives (boucles)

6 Algorithmique ESI 2021-2022

Rappel
 Un programme n’est pas purement séquentiel 
nécessité d’avoir des structures de contrôle

1. Les structures alternatives (tests)

2. Les structures itératives (boucles)

7 Algorithmique ESI 2021-2022

Rappel

ALGORITHME nom_de_l’algorithme
<partie des déclarations>
DEBUT
séquence1
SI condition1 ALORS
séquence2
FINSI
séquence3
FIN

8 Algorithmique ESI 2021-2022

Rappel
ALGORITHME nom_de_l’algorithme
<partie des déclarations>
DEBUT
séquence1
SI condition1 ALORS
séquence2
SINON
séquence3
FINSI
séquence4
FIN
9 Algorithmique ESI 2021-2022
Rappel
 Un test imbriqué est exprimé comme suit
SI condition1 ALORS
séquence1
SINON
SI condition2 ALORS
séquence2
SINON
séquence3
FINSI
FINSI

10 Algorithmique ESI 2021-2022

Rappel
 Pour alléger l’écriture et améliorer la lisibilité, on peut
fusionner SINON et SI en SINONSI  un seul bloc
de test
SI condition1 ALORS
séquence1
SINONSI condition2 ALORS
séquence2
SINON
séquence3
FINSI
11 Algorithmique ESI 2021-2022
Rappel
 Test « SUIVANT … CAS »
SUIVANT variable FAIRE
CAS valeur_1 : sequence_1
CAS valeur_2 : sequence_2
…
CAS valeur_n : sequence_n
AUTRES CAS : sequence_autre
FINSUIVANT

12 Algorithmique ESI 2021-2022

Rappel
 Test « SELONQUE … CAS … »
SELONQUE
condition_1 : sequence_1
condition_2 : sequence_2
…
condition_n : sequence_n
SINON: sequence_sinon
FINSELONQUE

13 Algorithmique ESI 2021-2022

Rappel
 Un programme n’est pas purement séquentiel 
nécessité d’avoir des structures de contrôle

1. Les structures alternatives (tests)

2. Les structures itératives (boucles)

14 Algorithmique ESI 2021-2022

Rappel
 Une boucle est une structure de contrôle de type
itératif (ou répétitif)

 Elle permet de répéter, plusieurs fois, une instruction ou

un ensemble d’instructions

 La répétition est soumise à une condition

15 Algorithmique ESI 2021-2022

Rappel
 On utilise trois types de boucles

 TANTQUE … FAIRE

 POUR

 RÉPÉTER … JUSQU’À

16 Algorithmique ESI 2021-2022

Rappel
 Boucle « TANTQUE … FAIRE »

 Permet de répéter une instruction tant qu’une condition

est vraie

TANTQUE condition FAIRE

instructions
FINTANTQUE

17 Algorithmique ESI 2021-2022

Rappel
 Boucle « POUR »

 Permet de répéter une instruction un nombre déterminé

de fois

 i.e. le nombre d’itérations est connu à l’avance

 Utilise un compteur qui est incrémenté après chaque

exécution du bloc d’instructions de la boucle

18 Algorithmique ESI 2021-2022

Rappel
 Boucle « POUR »

POUR compteur  valeur_initiale à valeur_finale pas valeur_pas

instructions
compteur SUIVANT

19 Algorithmique ESI 2021-2022

Rappel
 Boucle « RÉPÉTER … JUSQU’À »

 Permet de répéter une instruction jusqu’à ce que la

condition d’arrêt soit vraie

RÉPÉTER
instructions
JUSQU’À condition_arrêt

20 Algorithmique ESI 2021-2022

Problématique
 Les boucles permettent à l’utilisateur de saisir n
nombres  on déclare une seule variable mais on
écrase sa valeur à chaque nouvelle saisie

 Si on veut garder les n nombres pour les utiliser par

la suite  on déclare n variables différentes

 Quand n est petit  Lourd mais gérable

 Quand n est grand ?

21 Algorithmique ESI 2021-2022

Problématique
 Les boucles permettent à l’utilisateur de saisir n
nombres  on déclare une seule variable mais on
écrase sa valeur à chaque nouvelle saisie

 Si on veut garder les n nombres pour les utiliser par

la suite  on déclare n variables différentes

 Idéalement, tout stocker dans une seule variable 

tableau

22 Algorithmique ESI 2021-2022

Tableaux statiques
Définition
 Tableau statique

 Séquence de données de même type, chacune

référencée par un nombre appelé indice (ou index)

 Désigné par

 Son nom

 Le type de ses éléments

 Sa taille (i.e. le nombre de ses éléments)

24 Algorithmique ESI 2021-2022

Déclaration de tableaux statiques
 Syntaxe

VAR nomTableau[N] :Type

 N : taille du tableau

 Premier indice : 0

 Dernier indice : N – 1

25 Algorithmique ESI 2021-2022

Déclaration de tableaux statiques
 Syntaxe

VAR nomTableau[N] :Type

 Exemple :
VAR nombres[5] : entier
VAR lettres[26] : caractère
VAR mots[100] : chaîne
VAR absents[107] : booléen

26 Algorithmique ESI 2021-2022

Utilisation de tableaux statiques
 Pour désigner un élément du tableau, on utilise son
nom avec, entre parenthèses, l’indice de l’élément
concerné

 Exemple :
nombres[0]
nombres[1]
nombres[2]
nombres[3]
nombres[4]
27 Algorithmique ESI 2021-2022
Utilisation de tableaux statiques
 Pour affecter une valeur à une case du tableau, on
utilise son nom avec, entre parenthèses, l’indice
concerné puis le signe d’affectation et la valeur

 Exemple :
nombres[0]  5
nombres[1]  60
nombres[2]  10
nombres[3]  0
nombres[4]  90
28 Algorithmique ESI 2021-2022
Utilisation de tableaux statiques
nombres[0]  5
nombres[1]  60
nombres[2]  10
nombres[3]  0
nombres[4]  90
0 1 2 3 4

5 60 10 0 90

29 Algorithmique ESI 2021-2022

Utilisation de tableaux statiques
 L’indice peut être un nombre, une variable ou une
expression calculée

 Exemple

nombres[0]
nombres[i]
nombres[2*i+5]

30 Algorithmique ESI 2021-2022

Utilisation de tableaux statiques
 Exemple : demander à l’utilisateur de saisir 10
nombres réels

31 Algorithmique ESI 2021-2022

Utilisation de tableaux statiques
 Exemple : demander à l’utilisateur de saisir 10
nombres réels
ALGORITHME tableau_réels
VAR nombres[10] : réel
DEBUT
POUR i  0 à 10
Afficher(" Saisir le nombre numéro ", i+1)
Lire(nombres[i])
i SUIVANT
FIN

32 Algorithmique ESI 2021-2022

Exercice
 Que fait cet algorithme ?

ALGORITHME exemple_tableau
VAR tableau[10] , i : entier
DEBUT
POUR i  0 à 10
tableau[i]  i
i SUIVANT
POUR i  0 à 10
Afficher(tableau[i])
i SUIVANT
FIN

33 Algorithmique ESI 2021-2022

Exercice
 Que fait cet algorithme ?
ALGORITHME exemple_tableau
VAR tableau[10] , i, j : entier
DEBUT
tableau[0]  0
POUR i  1 à 10
tableau[i]  tableau[i − 1] + 1
i SUIVANT
POUR i  0 à 10
Afficher(tableau[i])
i SUIVANT
FIN
34 Algorithmique ESI 2021-2022
Exercice
 Écrire un algorithme qui demande à l’utilisateur de
saisir 20 nombres et puis qui les affiche

35 Algorithmique ESI 2021-2022

Exercice

ALGORITHME moyenne
VAR nombres[20] : réel
DEBUT
somme  0
POUR i  0 à 20
Afficher("Saisir le nombre numéro ", i+1)
Lire(notes[i])
i SUIVANT
POUR i  0 à 20
Afficher("Le ", i, "ème nombre est : ", nombres[i])
i SUIVANT
FIN

36 Algorithmique ESI 2021-2022

Exercice
 Écrire un algorithme qui demande à l’utilisateur de
saisir 20 nombres et puis qui les affiche à partir du
dernier saisi

37 Algorithmique ESI 2021-2022

Exercice

ALGORITHME moyenne
VAR nombres[20] : réel
DEBUT
somme  0
POUR i  0 à 20
Afficher("Saisir le nombre numéro ", i+1)
Lire(notes[i])
i SUIVANT
POUR i  20 à – 1 pas – 1
Afficher("Le ", i, "ème nombre est : ", nombres[i – 1])
i SUIVANT
FIN

38 Algorithmique ESI 2021-2022

Exercice
 Écrire un algorithme qui demande à l’utilisateur de
saisir 20 notes et lui affiche leur moyenne

39 Algorithmique ESI 2021-2022

Exercice
ALGORITHME moyenne
VAR notes[20], somme : réel
DEBUT
somme  0
POUR i  0 à 20
Afficher(" Saisir la note numéro ", i)
Lire(notes[i])
somme  somme + notes[i]
i SUIVANT
Afficher("La moyenne est : ", somme/20)
FIN

40 Algorithmique ESI 2021-2022

Exercice
 Écrire un algorithme qui demande à l’utilisateur de
saisir 20 notes et lui affiche leur moyenne, la note
minimale et la note maximale

41 Algorithmique ESI 2021-2022

ALGORITHME moyenne_min_max
VARExercice
notes[20], somme, min, max : réel
DEBUT
Afficher("Saisir la 1ère note")
Lire(notes[0])
somme, max, min  notes[0]
POUR i  1 à 20
Afficher(" Saisir la note numéro ", i)
Lire(notes[i])
somme  somme + notes[i]
SI notes[i] < min ALORS
min  notes[i]
SINONSI notes[i] > max ALORS
max  notes[i]
FINSI
i SUIVANT
Afficher("Moyenne = ", somme/20, "Min = ", min, "Max = ", max)
FIN
42 Algorithmique ESI 2021-2022
Problématique
 Écrire un algorithme qui demande à l’utilisateur de
saisir des notes et lui affiche leur moyenne, la note
minimale et la note maximale

 Le nombre de notes à saisir n’est pas connu à l’avance

43 Algorithmique ESI 2021-2022

Problématique
 Écrire un algorithme qui demande à l’utilisateur de
saisir des notes et lui affiche leur moyenne, la note
minimale et la note maximale

 Le nombre de notes à saisir n’est pas connu à l’avance

 Tableau dynamique

44 Algorithmique ESI 2021-2022

Tableaux dynamiques
Définition
 Tableau dynamique

 Séquence de données de même type, chacune

référencée par un nombre appelé indice (ou index), dont
la taille est variable et peut changer lors de l’exécution

46 Algorithmique ESI 2021-2022

Déclaration de tableaux dynamiques
 Syntaxe

VAR nomTableau[ ] :Type

 Exemple :
VAR nombres[ ] : entier
VAR lettres[ ] : caractère
VAR mots[ ] : chaîne
VAR absents[ ] : booléen

47 Algorithmique ESI 2021-2022

Redimensionnement
 L’opération de redimensionnement permet de fixer la
taille du tableau dynamique

 Elle intervient dans le corps de l’algorithme

 Elle est effectuée par l’instruction Redim

48 Algorithmique ESI 2021-2022

Redimensionnement
ALGORITHME tableau_dynamique
VAR notes[ ] : réel
VAR n : entier
DEBUT
Afficher("Quelle est le nombre de notes à saisir ?")
Lire(n)
Redim notes[n]
POUR i  0 à n
Afficher(" Saisir la note numéro ", i + 1)
Lire(notes[i])
i SUIVANT
FIN
49 Algorithmique ESI 2021-2022
Redimensionnement
 L’opération de redimensionnement permet de fixer la
taille du tableau dynamique

 Elle intervient dans le corps de l’algorithme

 Elle est effectuée par l’instruction Redim

 À tout moment, on peut ajouter / supprimer des cases

50 Algorithmique ESI 2021-2022

Exercice
 Écrire un algorithme qui demande à l’utilisateur de
saisir des notes et lui affiche leur moyenne, la note
minimale et la note maximale

 Demander à l’utilisateur combien de notes il veut saisir

51 Algorithmique ESI 2021-2022

ALGORITHME moyenne
VAR notes[ ], somme, min, max : réel
Exercice
VAR n : entier
DEBUT
somme  0
Afficher("Combien de notes voulez-vous saisir ?")
Lire(n)
Redim notes[n]
Afficher("Saisir la 1ère note")
Lire(notes[0])
somme, max, min  notes[0]
POUR i  1 à n
Afficher(" Saisir la note numéro ", i)
Lire(notes[i])
somme  somme + notes[i]
SI notes[i] < min ALORS
min  notes[i]
SINONSI notes[i] > max ALORS
max  notes[i]
FINSI
i SUIVANT
Afficher("Moyenne = ", somme/20, "Min = ", min, "Max = ", max)
FIN 52 Algorithmique ESI 2021-2022
Exercice
 Écrire un algorithme qui demande à l’utilisateur de
saisir des nombres réels puis qui lui affiche le nombre
des positifs, le nombre des négatifs, le nombre
minimal et le nombre maximal

 Demander à l’utilisateur combien de nombres il veut

saisir

53 Algorithmique ESI 2021-2022

ALGORITHME exercice_tableau_dynamique

Exercice
VAR nombres[ ], min, max : réel
VAR n, nbPositifs : entier
DEBUT
nbPositifs  0
Afficher("Combien de nombre voulez-vous saisir ?")
Lire(n)
Redim nombres[n]
POUR i  0 à n
Afficher("Saisir le nombre numéro ", i)
Lire(nombres[i])
SI i = 0 ALORS
min  nombres[i]
max  nombres[i]
SINONSI nombres[i] < min ALORS
min  nombres[i]
SINONSI nombres[i] > max ALORS
max  nombres[i]
FINSI
SI nombres[i] >= 0 ALORS
nbPositifs  nbPositifs + 1
FINSI
i SUIVANT
Afficher("Min = ", min, "Max = ", max, "Nb + = ", nbPositifs, "Nb − ", n − nbPositifs)
FIN
54 Algorithmique ESI 2021-2022
Exercice
 Écrire un algorithme qui demande à l’utilisateur de
remplir deux tableaux (de même taille) puis qui
affiche le tableau contenant le produit des éléments
des deux

 Demander à l’utilisateur la taille des tableaux

Tableau 1 5 2 10 15 1

Tableau 2 5 60 10 0 90

Tableau 3 25 120 100 0 90

55 Algorithmique ESI 2021-2022

ALGORITHME exercice_tableau_dynamique
VAR tab1[ ], tab2[ ], tab3[ ] : réel
Exercice
VAR n : entier
DEBUT
Afficher("Combien de nombre voulez-vous saisir ?")
Lire(n)
Redim tab1[n]
Redim tab2[n]
Redim tab3[n]
Afficher("Remplissage du 1er tableau")
POUR i  0 à n
Afficher("Saisir le nombre numéro ", i)
Lire(tab1[i])
i SUIVANT
Afficher("Remplissage du 2e tableau")
POUR i  0 à n
Afficher("Saisir le nombre numéro ", i)
Lire(tab2[i])
i SUIVANT
POUR i  0 à n
tab3[i]  tab1[i]*tab2[i]
Afficher(tab1[i], "*", tab2[i], "=", tab3[i])
i SUIVANT
FIN 56 Algorithmique ESI 2021-2022
Problématique
 Besoin : pour une classe de 10 étudiants, nous
voulons stocker, pour chaque étudiant, ses notes dans
2 matières
 Un tableau de 10 éléments pour la note de la première matière;
et un autre tableau pour la note de la deuxième

57 Algorithmique ESI 2021-2022

Problématique
 Besoin : pour une classe de 10 étudiants, nous
voulons stocker, pour chaque étudiant, ses notes dans
2 matières
 Un tableau de 10 éléments pour la note de la première matière;
et un autre tableau pour la note de la deuxième

 Matrice de 10 x 2 avec, dans chaque ligne i, les deux notes de

l’étudiant numéro i

58 Algorithmique ESI 2021-2022

Problématique
 Besoin : pour une classe de 10 étudiants, nous
voulons stocker, pour chaque étudiant, ses notes dans
2 matières
 Un tableau de 10 éléments pour la note de la première matière;
et un autre tableau pour la note de la deuxième

 Matrice de 10 x 2 avec, dans chaque ligne i, les deux notes de

l’étudiant numéro i  tableau multidimensionnel

59 Algorithmique ESI 2021-2022

Tableaux multidimensionnels
Définition
 Tableau à 2 dimensions

 Séquence de données de même type, chacune

référencée par deux indices

 Désigné par

 Son nom

 Le type de ses éléments

 Sa taille n x m
 Peut être assimilé à une matrice de n lignes et m colonnes
61 Algorithmique ESI 2021-2022
Déclaration de tableaux à 2 dimensions
 Syntaxe

VAR nomTableau[N][M] :Type

 Exemple :
VAR nombres[5][5] : entier
VAR lettres[26][2] : caractère
VAR mots[1][10] : chaîne
VAR absents[107][30] : booléen

62 Algorithmique ESI 2021-2022

Exemple de tableaux à 2 dimensions

ALGORITHME tableau_2d
VAR notes[20][2] : réel
DEBUT
POUR i  0 à 20
Afficher("Saisir la 1ère note de l’étudiant N° ", i+ 1)
Lire(notes[i][0])
Afficher("Saisir la 2e note de l’étudiant N° ", i+ 1)
Lire(notes[i][1])
i SUIVANT
FIN

63 Algorithmique ESI 2021-2022

Exercice
 Que font les algorithmes suivants ?

64 Algorithmique ESI 2021-2022

ALGORITHME exemple_tab
Exercice
VAR tab[5][10] : entier
 Que
VAR i, j, k:fait l’algorithme
entier suivant ?
DEBUT
k1
POUR i  0 à 5
POUR j  0 à 10
tab[i][j]  k
kk+1
j SUIVANT
i SUIVANT
FIN
65 Algorithmique ESI 2021-2022
 Exercice
ALGORITHME exemple_tab
 Que
VAR fait l’algorithme
tab[5][10] : entier suivant ?
VAR i, j : entier
DEBUT
POUR i  0 à 5
POUR j  0 à 10
tab[i][j]  i + j
j SUIVANT
i SUIVANT
FIN

66 Algorithmique ESI 2021-2022

Exercice
 Écrire un algorithme qui génère un tableau de
booléens de 5 x 10 où toutes les cases contiennent la
valeur VRAI

67 Algorithmique ESI 2021-2022

Exercice

ALGORITHME tab_bool
VAR tab[5][10] : booléen
DEBUT
POUR i  0 à 5
POUR j  0 à 10
tab[i][j]  VRAI
j SUIVANT
i SUIVANT
FIN

68 Algorithmique ESI 2021-2022

Exercice
 Écrire un algorithme qui demande à l’utilisateur de
remplir une matrice de 10 x 10 et vérifie si elle est
symétrique ou non

69 Algorithmique ESI 2021-2022

Exercice
 Écrire un algorithme qui demande à l’utilisateur de
remplir une matrice de 10 x 10 et vérifie si elle est
symétrique ou non
x a b c

a x d e

b d x f

c e f x

70 Algorithmique ESI 2021-2022

 Exercice
i0
j0
ALGORITHME symétrie_matrice TANTQUE sym ET i < 10
VAR matrice[10][10] : réel TANTQUE j < 10
SI j<>i et matrice[i][j] <> matrice[j][i] ALORS
VAR sym : booléen
sym = FALSE
DEBUT
FINSI
sym  VRAI
jj+1
POUR i  0 à 10 FINTANTQUE
POUR j  0 à 10 ii+1
Lire(matrice[i][j]) FINTANTQUE
j SUIVANT SI sym ALORS
i SUIVANT Afficher("La matrice saisie est symétrique")
SINON
Afficher("La matrice saisie n’est pas symétrique")
FINSI
71 FIN
Algorithmique ESI 2021-2022
Exercice
 Écrire un algorithme qui cherche, dans un tableau
d’entiers de 10 x 10, le nombre minimal et le nombre
maximal

72 Algorithmique ESI 2021-2022

ALGORITHME tab_bool
Exercice
VAR tab[10][10], min, max : réel
VAR i, j : entier
DEBUT
//instructions de remplissage du tableau omises
min, max  tab[0][0]
POUR i  0 à 10
POUR j  0 à 10
SI tab[i][j] < min ALORS
min  tab[i][j]
SINONSI tab[i][j] > max ALORS
max  tab
FINSI
j SUIVANT
i SUIVANT
Afficher("Max = ", max, " et Min = ", min)
FIN

73 Algorithmique ESI 2021-2022

Recherche dans un tableau
Recherche dans un tableau

 Proposition ?

75 Algorithmique ESI 2021-2022

Recherche séquentielle
 Vérifier si une valeur existe dans un tableau 
utiliser un flag

 Parcourir le tableau

 Si élément courant = valeur  flag = VRAI

 Vérifier le flag à la fin de l’exécution

 Si flag = VRAI  l’élément existe

76 Algorithmique ESI 2021-2022

Recherche séquentielle
 Pseudo-code

 Recherche de la valeur val dans le tableau tab[N]

77 Algorithmique ESI 2021-2022

 Recherche séquentielle
 Pseudo-code
existe  FAUX
POUR  Exemple
i  0 à N du tri du tableau tab[N]
SI tab[i] = val ALORS
existe  VRAI
FINSI
SI existe ALORS
Afficher("La valeur recherchée a été trouvée")
SINON
Afficher("La valeur recherchée n’a pas été trouvée")
FINSI
i SUIVANT

78 Algorithmique ESI 2021-2022

Recherche séquentielle
 Pseudo-code

 Recherche de la valeur val dans le tableau tab[N]

 Amélioration possible : ne pas continuer les comparaisons

si l’élément a été trouvé

 Encore mieux : recherche dichotomique

79 Algorithmique ESI 2021-2022

Recherche dichotomique
 Principe

 Comparer la valeur à trouver avec l’élément au milieu du

tableau

 Si inférieure, refaire la même comparaison avec la première

moitié du tableau

 Si supérieure, refaire la même comparaison avec la deuxième

moitié du tableau

 Nécessite que le tableau soit trié

80 Algorithmique ESI 2021-2022
Recherche dichotomique
 Pseudo-code

 Recherche de la valeur val dans le tableau tab[N]

81 Algorithmique ESI 2021-2022

 Recherche dichotomique
existe  FAUX
 Pseudo-code
debut  0
fin  NExemple du tri du tableau tab[N]
TANTQUE existe = FAUX ET debut <= fin
milieu  (debut + fin) DIV 2
SI tab[milieu] = val ALORS
existe  VRAI
SINONSI tab[mileu] < val ALORS
debut  milieu + 1
SINON
fin  milieu – 1
FINSI
FINTANTQUE
82 Algorithmique ESI 2021-2022
Algorithmique

5. Les tableaux