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
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.
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.
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 iiè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
