Chapitre 5

Traitement  des  Tableaux

Rappel

Pourquoi les tableaux ?

1) Calculer  la  moyenne de 30  élèves  

2) Effectuer leur classement

*   Réponse

pour i de 1 à 30

faire

Ecrire (" Donner la moyenne de l'étudiant N°",i)

Lire (moyenne)

Fin faire

*   Conclusion : On ne peut pas effectuer le classement

Pourquoi ? Parce qu'on ne garde pas les moyennes précédentes et la variable moyenne contient uniquement la dernière valeur.

Utilisation des tableaux

Intérêt Gain de temps, rétrécissement du volume de l'algorithme et possibilité de réutilisation de toutes les valeurs ultérieurement dans l'algorithme.

Il est plus convenable, alors, de définir un espace mémoire qu'on appelle MOY qui sera  divisé en 30 parties équitables, indicées de 1 à 30.

MOY

Contenu	15	12	5	10	4	50	….
Indice	1	2	3	4	5	6	7	8	9	10	11	12	13

On définit un tableau de 30 cases à une seule dimension qu'on appelle VECTEUR.

ALGORITHME MOYENNE

CONST Bi=1

             Bs=30

VAR T : Tableau [bi..bs] de réel

            i : entier

1.1.1. Les vecteurs

Un vecteur est une partie de mémoire contenant n zones variables référencées par le même nom de variable pour accéder à un élément particulier de ce vecteur.

On indice le nom de variable. L'indice peut être une constante, une variable ou une expression arithmétique.

MOY[i]

   indice d'un élément du vecteur

   variable qui indique le nom du vecteur

MOY[i] : représente l'élément du vecteur MOY occupant le rang " i ".

L'indice peut être :

• Une constante  :    MOY[5]
• Une variable    :     MOY[i]
• Une expression :    MOY[i*2]

ATTENTION

Avant d'utiliser un tableau, il faut déclarer sa taille pour que le système réserve la place en mémoire, nécessaire pour stocker tous les éléments de ce tableau.

Les éléments d'un même tableau doivent être de même type.

1.2. Rappel de Déclaration d'un vecteur

Dans la partie CONST, on peut définir la taille du tableau. Ensuite, on peut déclarer le nombre d'éléments à saisir dans le tableau.

Remarque : Le nombre d'éléments à saisir ne doit pas dépasser la taille du tableau pour ne pas déborder sa capacité.

On appelle dimension d'un vecteur le nombre d'éléments qui constituent ce vecteur.

1.3.Chargement d'un Vecteur                                    

Le chargement d'un vecteur consiste à saisir les données des éléments du vecteur. (remplir des cases successives du tableau). On doit utiliser une boucle qui permet de saisir à chaque entrée dans la boucle la i^ième  case.

ALGORITHME            Vecteur

CONST          N = 30

VAR

            MOY : Tableau[1..N] de réels

Début

{ chargement du tableau }

Pour i de 1 à N

Faire

Ecrire (" donner la moyenne de l'étudiant N° " , i )

Lire ( MOY [i])

Fin Faire

{ fin chargement }

{Calcul de la somme des moyennes}

SMOY ← 0

Pour i de 1 à N

Faire

SMOY ← SMOY+MOY[i]

Fin Faire

SMOY ← SMOY / 30

Ecrire (" la moyenne du groupe est ", SMOY )

{ calcul de la différence entre la moyenne de groupe et celle  de l'étudiant }

Pour i de 1 à N

Faire

Ecrire (" la différence de la moyenne du groupe et celle de l'étudiant ",i ,  " est= ", SMOY-MOY[i])

Fin Faire

Fin

$ On peut écrire les deux premières boucle en une seule. Simplifier alors cet algorithme.

Remarque

La taille d'un tableau est fixe et ne peut être donc changée dans un programme : il en résulte deux défauts :

•   Si on limite trop la taille d'un tableau on risque le dépassement de capacité.
•   La place mémoire réservée est insuffisante pour recevoir toutes les données.

Application

1)      Charger un vecteur de 10 éléments par les 10 premiers entiers naturels positifs.

2)      Charger un vecteur de 10 éléments par les 10 premiers multiples de 7.

1-a)   Recherche dans un vecteur

Recherche séquentielle

On peut chercher le nombre d'apparition d'un élément dans un vecteur, sa ou bien ses positions. Pour cela, on doit parcourir tout le vecteur élément par élément et le comparer avec la valeur de l'élément à chercher.

Applications

1.      Chercher la position de la première occurrence d'un élément e dans un vecteur V contenant N éléments. (On suppose que le vecteur est définit)

2.      Chercher le nombre d'apparition d'un élément e dans un vecteur V contenant N éléments, ainsi que les positions des occurrences de  cet élément.

Réponse 1

i ← 1

Trouv ← vrai

Tant que ((i <= N) et (Trouv = vrai))

            Faire

                        Si V[i] = e Alors

                                   Trouv ← Faux

                        Sinon

                                   i ← i +1

                        Fin Si

            Fin Faire

Si (Trouv = vrai) Alors

            Ecrire(e, "se trouve à la position" , i)

Sinon

            Ecrire(e, "ne se trouve pas dans V")

Fin Si

Recherche dichotomique

Ce type de recherche s'effectue dans un tableau ordonné.

Principe

1.      On divise le tableau en deux parties sensiblement égales,

2.      On compare la valeur à chercher avec l'élément du milieu,

3.      Si elles ne sont pas égales, on s'intéresse uniquement la partie contenant les éléments voulus et on délaisse l'autre partie.

4.      On recommence ces 3 étapes jusqu'à avoir un seul élément à comparer.

Application

On suppose qu'on dispose d'un vecteur V de N éléments. On veut chercher la valeur Val.

ALGORITHME DICHOTHOMIE

...

Inf ← 1

Sup ← N

Trouv  ← vrai

Tant que ((Inf <= Sup) et (Trouv = vrai))

Faire

Mil ← (Inf+Sup)DIV 2

Si (V[Mil] = Val) Alors

            Trouv ← faux

Sinon

            Si (V[Mil] < Val) Alors

                        Inf ← Mil + 1

            Sinon

                        Sup ← Mil -1

            Fin Si

Fin Si

Fin Faire

Si (Trouv = faux) Alors

            Ecrire(Val, "existe à la position" , Mil)

Sinon

Ecrire(Val, "n'existe pas dans V)

Fin Si

1.4.2. Les matrices

Les matrices sont les tableaux à deux dimensions.             

5 LIGNES	4 COLONNES
	1	2	3	4	5
	1	2	5	3	6
	2	4	-5	-1	3
	3	7	-6	-3	0
	4	5	-2	2	2
	5	8	4	10	-9

L'élément d'indice [i,j] est celui du croisement de la ligne i avec la colonne j

M[3,2] est -6