INFORMATIQUE

ALGORITHMIQUE
DR. YAHAYA COULIBALY
LES TABLEAUX
 Définition

 Un tableau est une suite de N données de même type,

rangées consécutivement, indicée par un ensemble non
vide d'indices, permettant un accès direct à chaque
donnée.

 N est la taille du tableau et que les données sont ses

éléments. Chaque élément est repère dans le tableau par
son indice. Un indice correspond à un numéro d'ordre
dans le tableau, les éléments étant rangés par ordre
d'indices consécutifs croissants.
 Déclaration d’un tableau

Une variable de type tableau est déclarée selon la syntaxe suivante

:
 Syntaxe

Var nom_du_tableau : TABLEAU[min_indice..max_indice] DE

<type_predefini>;
 ce qui signifie que les éléments ont pour type le
<type_predefini>;
 les indices des éléments vont de min_indice à max_indice ;
 avec min_indice < max_indice ;
 Déclaration d’un tableau

NB: on peut déclarer un tableau de N valeurs comme ceci:

Var nom_tableau: TABLEAU[ N ] DE <type_predefini> ;

Remarque :

 min_indice est facultatif ;

 Si min_indice n’est pas indiqué, le tableau est indicé de 0

à max_indice.
 Utilité des Tableaux
Imaginons que dans un programme, nous souhaiton calculer la
moyenne de 10 valeurs (par exemple, des notes).
La seule solution dont nous disposons à l’heure actuelle consiste à
déclarer dix variables, appelées par exemple Notea, Noteb, Notec,
etc ou nous pouvons utliser une notation un peu simplifiée, par
exemple N1, N2, N3, etc. Mais cela ne change pas
fondamentalement notre problème, car arrivé au calcul, et après une
succession de dix instructions « Lire » distinctes, cela donnera
obligatoirement ce qui suit:
 Moy ← (N1+N2+N3+N4+N5+N6+N7+N8+N9+N10)/10
 Utilité des Tableaux
La programmation nous permet de rassembler toutes ces
variables en une seule appelé Tableau, au sein de laquelle
chaque valeur sera désignée par un numéro.
 Notation et utilisation
algorithmique
Dans notre exemple, nous créerons donc un tableau appelé
Note. Chaque élément du tableau Note sera donc désignée
Note(0), Note(1), etc.

Les indices des tableaux commencent généralement à 0, et

non à 1.
 Notation et utilisation
algorithmique
Un tableau doit être déclaré comme tel, en précisant le
nombre et le type de valeurs qu’il contiendra.

La déclaration des tableaux est susceptible de varier d'un

langage à l'autre. Certains langages réclament le nombre
d'éléments, d'autre le plus grand indice... C'est donc une
affaire de conventions.
 Notation et utilisation
algorithmique
En nous référant sur les choix les plus fréquents dans les langages
de programmations, nous déciderons ce qui suit:
1. Le plus petit indice est (0) zéro.
2. lors de la déclaration d'un tableau, on précise la plus grande
valeur de l'indice différente, donc, du nombre de cases du tableau.
Si on veut 12 emplacements, le plus grand indice sera 11)
Exemple:

Tableau Note(11) en Entier

 Notation et utilisation
algorithmique
On peut créer des tableaux contenant des variables de tous
types : tableaux de numériques, tableaux de caractères,
tableaux de booléens, tableaux de tout ce qui existe dans un
langage donné comme type de variables.

Par contre, hormis dans quelques rares langages, on ne peut

pas faire un mixage de types différents de valeurs au sein
d’un même tableau.
 Remarque générale
l’indice qui sert à désigner les éléments d’un tableau peut
être exprimé directement comme un nombre en clair, mais il
peut être aussi une variable, ou une expression calculée.
 Remarque générale
Dans un tableau, la valeur d’un indice doit toujours :
1. Etre égale au moins à 0 (dans quelques rares langages, le
premier élément d’un tableau porte l’indice 1).
2. Etre un nombre entier Quel que soit le langage.
3. Etre inférieure ou égale au nombre d’éléments du
tableau (moins 1, si l’on commence la numérotation à zéro).
Si le tableau NomEtud a été déclaré comme ayant 25
éléments, la présence dans une ligne, sous une forme ou sous
une autre, de NomEtud(32) déclenchera automatiquement
une erreur.
 A Noter
Il ne faut pas confondre, dans ta tête et / ou dans un
algorithme, l’indice d’un élément d’un tableau avec
le contenu de cet élément.

La cinquième maison de la rue n’a pas forcément cinq

habitants, et la vingtième vingt habitants. En notation
algorithmique, il n’y a aucun rapport entre i et truc(i).
 Accès à un élément du
tableau
 On accède à un élément dans un tableau à partir de son
indice. La valeur de cet indice devant être comprise entre
les indices de début et de fin du tableau.

 Par exemple, tab1[8] désigne l'élément d'indice 8 dans le

tableau tabl, autrement dit le 9ème élément du tableau ;
tandis que tab2[14] désigne l'élément d'indice 14 dans le
tableau tab2, autrement dit le 15ème élément du tableau.
 Accès à un élément du
tableau
 Pour lire un élément ou le modifier, on indiquera la
valeur de l'indice :

a tab1[1] ; // a prend la valeur de l'élément n°1

tab1[5] 3456 ; // l'élément n°5 prend la valeur 3456

 b 3;

 a tab1[b] ; // a prend la valeur de la cellule n° 3

 Parcours des éléments
d'un tableau
Dans de nombreux algorithmes, on doit parcourir le tableau
pour faire un traitement sur chaque élément du tableau.
Parmi les traitements opérant sur des tableaux, on peut:

 remplir (Saisir) des valeurs dans un tableau ;

 récupérer, consulter des valeurs rangées dans un tableau

;

 rechercher si une valeur est dans un tableau ;

 mettre à jour des valeurs dans un tableau ;

 Parcours des éléments
d'un tableau
 modifier la façon dont les valeurs sont rangées dans un
tableau (par exemple : les trier de différentes manières) ;

 effectuer des opérations entre tableaux : comparaison

de tableaux, addition multiplication,...
 Remplir un tableau
 Le remplissage d’un tableau consiste à saisir les valeurs des
éléments du tableau.
 Exemple

 Algorithme remplissage_tableau
 VAR i: entier ;
 T : Tableau[10] DE entier ;
 DEBUT
POUR i DE 1 A 10 FAIRE
lire(T[i]) ;
FINPOUR
 FIN
 Afficher un tableau

L’affichage d’un tableau consiste à afficher les valeurs des

éléments du tableau.
 Exemple

Algorithme affichage_tableau

VAR i: entier ;

T : Tableau[10] DE entier ;

DEBUT

//On suppose que le tableau est déjà rempli

// On affiche les valeurs du tableau

POUR i DE 1 A 10 FAIRE

ecrire(T[i]) ;

FINPOUR

FIN
 Exemple
Tableau Note(9) en Numérique
Variables Moyenne, Som en Numérique
Début
Pour i ← 0 à 9
Ecrire "Entrez la note n°", i
Lire Note(i)
i Suivant
Som ← 0
Pour i ← 0 à 9
Som ← Som + Note(i)
i Suivant
Moy ← Som / 10
Fin
 Tri d’un tableau
Il existe plusieurs stratégies possibles pour trier les éléments
d’un tableau ; nous en verrons deux :

1. Le tri par sélection, et

2. Le tri à bulles.
 Le tri par sélection.

Admettons que le but de la manœuvre soit de trier un

tableau de 10 éléments dans l’ordre croissant.

La technique du tri par sélection est la suivante : on met en

bonne position l’élément numéro 1, c’est-à-dire le plus petit.
Puis en met en bonne position l’élément suivant. Et ainsi de
suite jusqu’au dernier
 Exemple 2

3 122 12 45 21 78 64 53 89 46
 Algo Tri par Selection
//Boucle principale : le point de départ se décale à chaque tour
Pour i ← 0 à 8
//on considère provisoirement que t(i) est le plus petit élément

posmini ← i

//on examine tous les éléments suivants

Pour j ← i + 1 à 9
Si t(j) < t(posmini) Alors
posmini ← j
Finsi
j suivant
/* A cet endroit, on sait maintenant où est le plus petit élément. Il ne reste
plus qu'à effectuer la permutation.*/

temp ← t(posmini)
t(posmini) ← t(i)
t(i) ← temp
//On a placé correctement l'élément numéro i, on passe à présent au suivant.
i suivant
 La recherche dans un
tableau: Technique Flag
Le flag, en anglais, est un petit drapeau, qui va
rester baissé aussi longtemps que l’événement
attendu ne se produit pas. Et, aussitôt que cet
événement a lieu, le petit drapeau se lève (la
variable booléenne change de valeur).
Ainsi, la valeur finale de la variable booléenne
permet au programmeur de savoir si l’événement a
eu lieu ou non.
 Illustration
Soit un tableau comportant, disons, 20 valeurs. L’on doit
écrire un algorithme saisissant un nombre au clavier, et qui
informe l’utilisateur de la présence ou de l’absence de la
valeur saisie dans le tableau.

La première étape, évidente, consiste à écrire les instructions

de lecture / écriture, et la boucle – car il y en a
manifestement une – de parcours du tableau
 Algo de base
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Pour i ← 0 à 19
???
i suivant
Fin
 Algo de base amélioré 1
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Pour i ← 0 à 19
Si N = Tab(i) Alors
Ecrire ”N fait partie du tableau"
Sinon
Ecrire ”N ne fait pas partie du tableau"
FinSi
i suivant
Fin
 Remarque
L'algorithme ne doit produire qu'une seule
réponse, quel que soit le nombre d'éléments que
compte le tableau.
Or, l'algorithme précedent envoie à l'écran autant
de messages qu'il y a de valeurs dans le tableau, en
l'occurrence pas moins de 20! dans notre exemple.
 Algo de base amélioré 2
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Pour i ← 0 à 19
???
i suivant
Si Trouvé Alors
Ecrire "N fait partie du tableau"
Sinon
Ecrire "N ne fait pas partie du tableau"
FinSi
Fin
 A noter
Il ne nous reste plus qu'à gérer la variable Trouvé. Ceci se
fait en deux étapes.

1. un test figurant dans la boucle, indiquant lorsque la

variable Trouvé doit devenir vraie (à savoir, lorsque la
valeur N est rencontrée dans le tableau). Et attention : le
test est asymétrique. Il ne comporte pas de "sinon".

2. L'affectation par défaut de la variable Trouvé, dont la

valeur de départ doit être évidemment Faux
 Algo de base amélioré 3
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Trouvé ← Faux
Pour i ← 0 à 19
Si N = Tab(i) Alors
Trouvé ← Vrai
FinSi
i suivant
Si Trouvé Alors
Ecrire "N fait partie du tableau"
Sinon
Ecrire "N ne fait pas partie du tableau"
FinSi
Fin
 Tri à bulles
L’idée de départ du tri à bulles consiste à se dire qu’un
tableau trié en ordre croissant, c’est un tableau dans
lequel tout élément est plus petit que celui qui le suit.

En effet, prenons chaque élément d’un tableau, et

comparons-le avec l’élément qui le suit. Si l’ordre n’est pas
bon, on permute ces deux éléments. Et on recommence
jusqu’à ce que l’on n’ait plus aucune permutation à effectuer.
Les éléments les plus grands « remontent » ainsi peu à peu
vers les dernières places
 Algo: Tri à bulles
Variable Yapermute en Booléen
Début
…
TantQue Yapermute
Pour i ← 0 à 8
Si t(i) > t(i+1) Alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Finsi
i suivant
Fin
Algo: Tri à bulles amélioré
 Variable Yapermute en Booléen
Début
…
Yapermut ← Vrai
TantQue Yapermut
Yapermut ← Faux
Pour i ← 0 à 8
Si t(i) > t(i+1) alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Yapermut ← Vrai
Finsi
i suivant
FinTantQue
Fin
 TABLEAUX
MULTIDIMENSIONNELS
 Tableaux à deux
dimensions
L’informatique nous offre la possibilité de déclarer des
tableaux dans lesquels les valeurs ne sont pas repérées par
une seule, mais par deux coordonnées.

Un tel tableau se déclare ainsi :

Tableau Cases(7, 7) en Numérique

 REMARQUE
ESSENTIELLE
Il n’y a aucune différence qualitative entre un tableau à deux
dimensions ( i, j ) et un tableau à une dimension ( i * j ).

Tout problème qui peut être modélisé d’une manière peut

aussi être modélisé de l’autre. Simplement, l’une ou l’autre
de ces techniques correspond plus spontanément à tel ou tel
problème, et facilite donc (ou complique, si on a choisi la
mauvaise option) l’écriture et la lisibilité de l’algorithme.
 Tableaux à n dimensions
Il n’y a aucun problème à passer au maniement de tableaux
à trois, quatre, ou pourquoi pas neuf dimensions. C’est
exactement la même chose.

Si vous déclarez un tableau Titi(2, 4, 3, 3), il s’agit d’un

espace mémoire contenant 2 x 4 x 3 x 3 = 72 valeurs.
Chaque valeur y est repérée par quatre coordonnées.
 A Noter
Pour des raisons uniquement pratiques, les tableaux à plus
de trois dimensions sont rarement utilisés par des
programmeurs non matheux (car les matheux, de par leur
formation, ont une fâcheuse propension à manier des
espaces à n dimensions comme qui rigole, mais ce sont bien
les seuls, et laissons les dans leur coin, c’est pas des gens
comme nous).