Algorithmique

5. Les tableaux
Sommaire

I. Rappel

II. Tableaux statiques

III. Tableaux dynamiques

IV. Tri dans un tableau

V. Recherche dans un tableau

2 Algorithmique ESI 2020-2021
 Rappel

3 Algorithmique ESI 2020-2021

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 2020-2021

Rappel

 Pseudo-code algorithmique

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

5 Algorithmique ESI 2020-2021

Rappel
 Une instruction est une action à accomplir par
l’algorithme

 On compte quatre instructions de base

 Déclaration (mémoire)

 Affectation (calcul)

 Lecture (entrées)

 Écriture (sorties)
6 Algorithmique ESI 2020-2021
Rappel
 Un programme n’est pas purement séquentiel 
nécessité d’avoir des structures de contrôle

1. Les tests

2. Les boucles

7 Algorithmique ESI 2020-2021

Rappel
 Structure d’un test

 SI … ALORS …
SI condition ALORS
séquence
FINSI

 SI … ALORS … SINON …
SI condition ALORS
séquence1
SINON
séquence2
FINSI

8 Algorithmique ESI 2020-2021

Rappel
 Structure d’un test imbriqué

SI condition1 ALORS
séquence1
SINONSI condition2 ALORS
séquence2
SINON
séquence3
FINSI

9 Algorithmique ESI 2020-2021

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

10 Algorithmique ESI 2020-2021

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

11 Algorithmique ESI 2020-2021

Rappel
 Il est parfois nécessaire de répéter des instructions
un certain nombre de fois

 Exemple : calculer le prix TTC pour une liste de produits

 La répétition est réalisée en utilisant une boucle

12 Algorithmique ESI 2020-2021

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

 On utilise trois types de boucles

 TANTQUE … FAIRE

 POUR

 RÉPÉTER … JUSQU’À

13 Algorithmique ESI 2020-2021

Rappel
 Boucle TANTQUE … FAIRE

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

est vraie

 Le nombre d’itérations n’est pas (forcément) connu à

l’avance
TANTQUE condition FAIRE
instructions
FINTANTQUE
14 Algorithmique ESI 2020-2021
Exercices
 Écrire un algorithme qui demande à l’utilisateur de
saisir un nombre compris entre 0 et 10 et répète
jusqu’à ce que la saisie soit correcte

15 Algorithmique ESI 2020-2021

Exercices

ALGORITHME boucle_saisie_nb
VAR n : réel
DEBUT
Afficher("Saisir un nombre compris entre 0 et 10")
Lire(n)
TANTQUE n < 0 OU n > 10 FAIRE
Afficher("Saisir un nombre compris entre 0 et 10")
Lire(n)
FINTANTQUE
Afficher("Saisie terminée. Merci. ")
FIN

16 Algorithmique ESI 2020-2021

ALGORITHME boucle_saisie_nb
Exercices
VAR n : réel
DEBUT
n  −1
Afficher("Saisir un nombre compris entre 0 et 10")
TANTQUE n < 0 OU n > 10 FAIRE
Lire(n)
SI n < 0 OU n > 10 ALORS
Afficher("Saisie erroné[Link] recommencer. ")
Lire(n)
FINSI
FINTANTQUE
Afficher("Saisie terminée. Merci. ")
FIN
17 Algorithmique ESI 2020-2021
Exercices
 Écrire un algorithme qui demande à l’utilisateur de
saisir un nombre compris entre 0 et 10 et répète
jusqu’à ce que la saisie soit correcte
 Si le nombre est inférieur à 0, afficher un message
demandant un nombre plus grand

 Si le nombre est supérieur à 10, afficher un message

demandant un nombre plus petit

18 Algorithmique ESI 2020-2021

ALGORITHME boucle_saisie_nb
VAR n : réel
Exercices
DEBUT
Afficher("Saisir un nombre compris entre 0 et 10")
Lire(n)
TANTQUE n < 0 OU n > 10 FAIRE
SI n < 0 ALORS
Afficher("Donner un nombre plus grand. ")
Lire(n)
SINONSI n > 10 ALORS
Afficher("Donner un nombre plus petit. ")
Lire(n)
FINSI
FINTANTQUE
Afficher("Saisie terminée. Merci. ")
FIN19 Algorithmique ESI 2020-2021
Exercices
 Écrire un algorithme qui demande à l’utilisateur de
saisir un nombre puis qui décrémente ce nombre de
1 jusqu’à atteindre 0 en affichant la valeur de chaque
décrémentation

20 Algorithmique ESI 2020-2021

Exercices

ALGORITHME boucle_décrémentation
VAR n : réel
DEBUT
Afficher("Saisir un nombre")
Lire(n)
TANTQUE n <> 0 FAIRE
nn−1
Afficher(n)
FINTANTQUE
FIN

21 Algorithmique ESI 2020-2021

Exercices
 Écrire un algorithme qui demande à l’utilisateur de
saisir un nombre puis qui affiche les 10 nombres
suivants

22 Algorithmique ESI 2020-2021

Exercices

ALGORITHME boucle_dix_nb_suivants
VAR n, max : réel
DEBUT
Afficher("Saisir un nombre")
Lire(n)
max  n + 10
Afficher("Les dix nombres suivants sont :")
TANTQUE n <= max FAIRE
nn+1
Afficher(n)
FINTANTQUE
FIN

23 Algorithmique ESI 2020-2021

Exercices
ALGORITHME boucle_dix_nb_suivants
VAR n, i : réel
DEBUT
Afficher("Saisir un nombre")
Lire(n)
i1
Afficher("Les dix nombres suivants sont :")
TANTQUE i <= 10 FAIRE
nn+i
Afficher(n)
ii+1
FINTANTQUE
FIN
24 Algorithmique ESI 2020-2021
Rappel
 Boucle POUR

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

de fois

 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

 Le programmeur n’a pas à géré l’incrémentation du compteur

25 Algorithmique ESI 2020-2021

Rappel
 Boucle POUR

 Le compteur a une valeur minimale = condition d’entrée

dans la boucle

 Le compteur a une valeur maximale = condition de sortie

de la boucle ([Link] compteur < valeur maximale)

 L’incrémentation du compteur se fait selon un pas

26 Algorithmique ESI 2020-2021

Rappel
 Structure de la boucle POUR

POUR compteur  initial à final pas valeur_pas

instructions
compteur SUIVANT

27 Algorithmique ESI 2020-2021

Boucle POUR
 Exemple de la boucle POUR

ALGORITHME exemple_boucle_pour
VAR n,i : entier
DEBUT
Lire(n)
POUR i  1 à 11 pas 1
nn+1
Afficher(n)
i SUIVANT
FIN

Afficher les nombres de n+1 à n+10

28 Algorithmique ESI 2020-2021

Exercices
 Écrire un algorithme qui demande à l’utilisateur de
saisir un nombre puis qui affiche les 10 nombres
suivants

29 Algorithmique ESI 2020-2021

Exercices

ALGORITHME boucle_dix_nb_suivants
VAR n, i : entier
DEBUT
Afficher("Saisir un nombre")
Lire(n)
Afficher("Les dix nombres suivants sont :")
POUR i  1 à 11 pas 1
nn+1
Afficher(n)
i SUIVANT
FIN

30 Algorithmique ESI 2020-2021

Exercices

ALGORITHME boucle_dix_nb_suivants
VAR n, i : entier
DEBUT
Afficher("Saisir un nombre")
Lire(n)
Afficher("Les dix nombres suivants sont :")
POUR i  1 à 11 pas 1
Afficher(n + i)
i SUIVANT
FIN

31 Algorithmique ESI 2020-2021

Exercices
 Écrire un algorithme qui affiche la table de
multiplication du chiffre 9
 De 9 x 1 à 9 x 10

32 Algorithmique ESI 2020-2021

Exercices

ALGORITHME boucle_table_neuf
VAR i: entier
DEBUT
POUR i  1 à 11
Afficher("9 *" , i , " = " , 9*i)
i SUIVANT
FIN

33 Algorithmique ESI 2020-2021

Exercices
 Écrire un algorithme qui demande à l’utilisateur de
saisir un nombre puis affiche la table de multiplication
de ce nombre
 De n x 1 à n x 10

34 Algorithmique ESI 2020-2021

ALGORITHME
Exercices boucle_table
VAR n: réel
VAR i: entier
DEBUT
Afficher("Saisir un nombre")
Lire(n)
POUR i  1 à 11
Afficher(n, " * " , i , " = " , n*i)
i SUIVANT
FIN

35 Algorithmique ESI 2020-2021

Exercices
 Écrire un algorithme qui demande à l’utilisateur de
saisir un nombre entier n puis qui affiche la somme
de tous les entiers jusqu’à n (1 + 2 + … + n)

36 Algorithmique ESI 2020-2021

ALGORITHME boucle_somme
Exercices
VAR n, i, somme: entier
DEBUT
Afficher("Saisir un nombre")
Lire(n)
somme  0
POUR i  1 à n+1
somme  somme + i
i SUIVANT
Afficher(" La somme de 1 à " , n , " est " , somme)
FIN
37 Algorithmique ESI 2020-2021
Exercices
 Écrire un algorithme qui demande à l’utilisateur de
saisir un nombre entier n puis qui calcule son produit
factoriel n! (2 * … * n)

38 Algorithmique ESI 2020-2021

ALGORITHME boucle_produit_factoriel
Exercices
VAR n, i, produit: entier
DEBUT
Afficher("Saisir un nombre")
Lire(n)
produit 1
POUR i  2 à n+1
produit produit* i
i SUIVANT
Afficher(" Le produit factoriel de " , n , " est " , produit)
FIN
39 Algorithmique ESI 2020-2021
Exercices
 Écrire un algorithme qui demande à l’utilisateur de
saisir dix nombres positifs puis qui retourne le
nombre le plus grand

40 Algorithmique ESI 2020-2021

ALGORITHME boucle_pgn
Exercices
VAR n, i, pgn: réel
DEBUT
pgn  0
POUR i  1 à 11
Afficher(" Saisir le nombre numéro ", i)
Lire(n)
SI n > pgn ALORS
pgn  n
FINSI
i SUIVANT
Afficher(" Le nombre le plus grand est " , pgn)
FIN
41 Algorithmique ESI 2020-2021
Exercices
 Écrire un algorithme qui demande à l’utilisateur de
saisir dix nombres positifs puis qui retourne le
nombre le plus grand et sa position

42 Algorithmique ESI 2020-2021

ALGORITHME boucle_pgn
Exercices
VAR n, i, pgn, pos: réel
DEBUT
pgn, pos  0
POUR i  1 à 11
Afficher(" Saisir le nombre numéro ", i)
Lire(n)
SI n > pgn ALORS
pgn  n
pos  i
FINSI
i SUIVANT
Afficher(" Le nombre le plus grand est " , pgn, " et sa position est ", pos)
FIN
43 Algorithmique ESI 2020-2021
Rappel
 Boucle RÉPÉTER … JUSQU’À

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

condition soit vraie

 Le nombre d’itérations n’est pas (forcément) connu à

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

44 Algorithmique ESI 2020-2021

Rappel
 Exemple

ALGORITHME exemple_boucle_répéter
VAR n, i : entier
DEBUT
n0
RÉPÉTER
nn+1
JUSQU’À n=10
FIN

45 Algorithmique ESI 2020-2021

Rappel
 Écrire un algorithme qui demande à l’utilisateur de
saisir des nombres positifs puis qui retourne le
nombre le plus grand
 Le nombre des nombres à saisir n’est pas connu à l’avance

 La saisie s’arrête quand l’utilisateur saisit le nombre −1

46 Algorithmique ESI 2020-2021

ALGORITHME boucle_pgn
VAR n, i, pgn, pos : réel
Exercices
DEBUT
pgn , i  0 , 1
RÉPÉTER
Afficher(" Saisir le nombre numéro ", i)
Lire(n)
SI n > pgn ALORS
pgn  n
pos  i
FINSI
i  i +1
JUSQU’À n = −1
Afficher(" Le nombre le plus grand est " , pgn, " et sa position est ", pos)
FIN
47 Algorithmique ESI 2020-2021
Problématique
 Dans les derniers exemples, on demande à
l’utilisateur de saisir 10 nombres  on déclare une
seule variable mais on écrase sa valeur à chaque
nouvelle saisie

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

la suite  on décalre10 variables différentes

 Lourd mais gérable

48 Algorithmique ESI 2020-2021

Problématique
 Si on demandait 100 nombres ? 200 ? 1000 ?

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

tableau

49 Algorithmique ESI 2020-2021

 Tableaux statiques

50 Algorithmique ESI 2020-2021

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)

51 Algorithmique ESI 2020-2021

Déclaration de tableaux statiques
 Syntaxe

VAR nomTableau[N] :Type

 N : taille du tableau

 Premier indice : 0

 Dernier indice : N – 1

52 Algorithmique ESI 2020-2021

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

53 Algorithmique ESI 2020-2021

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]
54 Algorithmique ESI 2020-2021
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
55 Algorithmique ESI 2020-2021
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

56 Algorithmique ESI 2020-2021

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]

57 Algorithmique ESI 2020-2021

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

58 Algorithmique ESI 2020-2021

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

59 Algorithmique ESI 2020-2021

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

60 Algorithmique ESI 2020-2021

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
61 Algorithmique ESI 2020-2021
Exercice
 Écrire un algorithme qui demande à l’utilisateur de
saisir 20 nombres et puis qui les affiche

62 Algorithmique ESI 2020-2021

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

63 Algorithmique ESI 2020-2021

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

64 Algorithmique ESI 2020-2021

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 à 0 pas – 1
Afficher("Le ", i, "ème nombre est : ", nombres[i – 1])
i SUIVANT
FIN

65 Algorithmique ESI 2020-2021

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

66 Algorithmique ESI 2020-2021

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

67 Algorithmique ESI 2020-2021

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

68 Algorithmique ESI 2020-2021

ALGORITHME moyenne
VAR notes[20], somme, min, max : réel
Exercice
DEBUT
somme  0
max  0
min  20
POUR i  0 à 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)
FIN69 Algorithmique ESI 2020-2021
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

70 Algorithmique ESI 2020-2021

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

71 Algorithmique ESI 2020-2021

 Tableaux dynamiques

72 Algorithmique ESI 2020-2021

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

73 Algorithmique ESI 2020-2021

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

74 Algorithmique ESI 2020-2021

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

75 Algorithmique ESI 2020-2021

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
76 Algorithmique ESI 2020-2021
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

77 Algorithmique ESI 2020-2021

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

78 Algorithmique ESI 2020-2021

ALGORITHME moyenne
VAR notes[ ], somme, min, max : réel
VARExercice
n : entier
DEBUT
somme  0
Afficher("Combien de notes voulez-vous saisir ?")
Lire(n)
Redim notes[n]
POUR i  0 à 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/n, "Min = ", min, "Max = ", max)
FIN79 Algorithmique ESI 2020-2021
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

80 Algorithmique ESI 2020-2021

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
81 Algorithmique ESI 2020-2021
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

82 Algorithmique ESI 2020-2021

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 83 Algorithmique ESI 2020-2021
 Tableaux multidimensionnels

84 Algorithmique ESI 2020-2021

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
85 Algorithmique ESI 2020-2021
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

86 Algorithmique ESI 2020-2021

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

87 Algorithmique ESI 2020-2021

Exercice
 Que font les algorithmes suivants ?

88 Algorithmique ESI 2020-2021

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
89 Algorithmique ESI 2020-2021
 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

90 Algorithmique ESI 2020-2021

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

91 Algorithmique ESI 2020-2021

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

92 Algorithmique ESI 2020-2021

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

93 Algorithmique ESI 2020-2021

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

94 Algorithmique ESI 2020-2021

 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
95 FIN
Algorithmique ESI 2020-2021
Exercice
 Écrire un algorithme qui cherche, dans un tableau
d’entiers de 10 x 10, le nombre minimal et le nombre
maximal

96 Algorithmique ESI 2020-2021

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

97 Algorithmique ESI 2020-2021

 Tri dans un tableau

98 Algorithmique ESI 2020-2021

Motivation
 Il est souvent nécessaire de stocker les valeurs d’un
tableau selon un ordre déterminé (ascendant ou
descendant)

 Plusieurs approches possibles

 Tri par sélection

 Tri à bulles

 …
99 Algorithmique ESI 2020-2021
Tri par sélection
 Approche intuitive

 On place le plus petit élément à la position 0

 Pui on place le plus petit des éléments restant à la

position 1

 Puis on place le plus petit des éléments restant à la

position 2

 Et ainsi de suite jusqu’au dernier élément

100 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive

 On détermine le plus petit élément, noté min, à partir de

l’indice i (à commencer par i = 0, le 1er élément)

 Échanger min et l’élément de la case i

 Refaire la même chose avec i + 1 jusqu’à avoir trié tous

les éléments

101 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

102 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

103 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

104 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

1 2 10 15 5

105 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

1 2 10 15 5

106 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

1 2 10 15 5

1 2 10 15 5

107 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

1 2 10 15 5

1 2 10 15 5

108 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

1 2 10 15 5

1 2 10 15 5

109 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

1 2 10 15 5

1 2 10 15 5

1 2 5 15 10

110 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

1 2 10 15 5

1 2 10 15 5

1 2 5 15 10

111 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

1 2 10 15 5

1 2 10 15 5

1 2 5 15 10

112 Algorithmique ESI 2020-2021

Tri par sélection
 Approche intuitive
5 2 10 15 1

1 2 10 15 5

1 2 10 15 5

1 2 5 15 10

1 2 5 10 15

113 Algorithmique ESI 2020-2021

Tri par sélection
 Pseudo-code

 Exemple du tri par sélection du tableau tab[N]

114 Algorithmique ESI 2020-2021

POUR i  0 à N − 2
Tri parsélection
indice_min i //prendre l’élément tab[i] comme plus petit élément provisoire
//examiner tous les éléments suivants
Pseudo-code
POUR ji+1àN−1
SIExemple du tri du tableau
tab[j] < tab[indice_min] tab[N]
ALORS
indice_min  j //récupérer l’indice de l’élément plus petit que tab[i]
FINSI
j SUIVANT
//permuter tab[i] et l’élément le plus petit, qui est tab[indice_min]
x  tab[i]
tab[i]  tab[indice_min]
tab[indice_min]  x
i SUIVANT //passer à l’élément tab[i+1]

115 Algorithmique ESI 2020-2021

Tri par sélection
 Pseudo-code

 Variante possible : effectuer la permutation au fur et à

mesure

116 Algorithmique ESI 2020-2021

 Tri par sélection
 Pseudo-code
POUR i0àN−2
//examiner tous les
 Exemple duéléments
tri dusuivants
tableau tab[N]
POUR j  i + 1 à N − 1
SI tab[j] < tab[i] ALORS //permuter à ce stade
x  tab[i]
tab[i]  tab[j]
tab[j]  x
FINSI
j SUIVANT
i SUIVANT //passer à l’élément tab[i+1]

117 Algorithmique ESI 2020-2021

Tri à bulles
 Approche

 On initialise un flag à FAUX

 On compare chaque élément à celui qui le suit

 Si non triés, on les permute et on met le flag à VRAI

118 Algorithmique ESI 2020-2021

Tri à bulles
 Approche

 À la sortie de la boucle

 Si flag = FAUX  le tableau est trié

 Si flag =VRAI  au moins une permutation a eu lieu  refaire

une itération pour vérifier s’il reste d’autres permutations à

faire

119 Algorithmique ESI 2020-2021

Tri à bulles
 Pseudo-code

 Exemple du tri à bulles du tableau tab[N]

120 Algorithmique ESI 2020-2021

 Tri à bulles
 Pseudo-code
permutation  VRAI
TANTQUE permutation
 Exemple du tri du tableau tab[N]
permutation  FAUX
POUR i  0 à N – 1
SI tab[i+1] < tab[i] ALORS
x  tab[i]
tab[i]  tab[i+1]
tab[i+1]  x
permutation  VRAI
FINSI
i SUIVANT
FINTANTQUE

121 Algorithmique ESI 2020-2021

 Recherche dans un tableau

122 Algorithmique ESI 2020-2021

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

123 Algorithmique ESI 2020-2021

Recherche séquentielle
 Pseudo-code

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

124 Algorithmique ESI 2020-2021

 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

125 Algorithmique ESI 2020-2021

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

126 Algorithmique ESI 2020-2021

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é

127 Algorithmique ESI 2020-2021
Recherche dichotomique
 Pseudo-code

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

128 Algorithmique ESI 2020-2021

 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
129 Algorithmique ESI 2020-2021
Algorithmique

5. Les tableaux