Chapitre 7 : Les tableaux
I. Tableau à n dimension
On nomme le tableau ci dessous T :
Numéro 0 1 2 3 4
case
Valeur -6 0 12 7 24
En générale on les écrit
T=[-6, 0, 12, 7, 24]
Attention : En C, les cases sont numérotées à partir de 0
Formellement, un tableau représente un produit cartésien
A*A...*A= A^k de taille fixée( ici k ) et homogène ( que des A, pas A*B*C)
Par contre A peut-être ce qu'on veut
→ tableau de réels
→ tableau d'entiers
→ tableau de booléens
→ tableau de rationnels
Type abstrait :
ex : les tableaux de réels
Types importés : entier_tan (pour le numéro de cases)
réel (pour le contenu des cases)
Opérateurs
nouveau_tableau : entier_nat (taille du tableau) → tableau
ecrire_tableau : entier_nat*réel*tableau → tableau
lire_tableau : entier_nat*tableau → réel
Attention : nouveau tableau crée un tableau « vide »
→ dans un algo, si on lit le contenu d'une case « vide », on a une erreur
→ en C si on lit le contenu d'une case non initialisée, on récupère n'importe
quoi ( ce qu'il y avait avant dans cette case mémoire de l'ordinateur)
Notations
lire_tableau (i, T) s'écrit T[i]
T:= ecrire_tableau (i, x, T) s'écrit T[i]:=x
t:=nouveau_tableau(n) s'écrit T:= nouveau tableau de n réels
Application :
Écrire un algo itératif qui étant donné un tableau T de n entiers, et un entier a
et renvoie
→ le plus petit numéro de case i tel que T[i] = a s'il existe
,→ -1 si aucune case ne contient la valeur a
Recherche dans un tableau
→ si le tableau est déjà trié
Une méthode efficace : la dichotomie
On a un tableau T à m cases et on cherche la valeur x, on va à la case m/2
• Si T[m/2] >x [2,3,8,12,15,22]
On va chercher x dans la première moitié du tableau
• Si T[m/2] =x on a trouvé
→ Pour chercher dans une moitié de tableau, on ré applique la méthode
→ Si on a coupé le tableau assez de fois, on arrive à un tableau vide et on
conclut que la valeur n'y est pas.
Exemple : T=[2 3 8 12 15 22]
n=6
On regarde T[n/2]=T[3]=12, on a 12<15. Donc on cherche x
On cherche x=15
dans [15 22] ou 22 est une valeur supérieur a x. Donc on
cherche dans [15]
valeur=x=trouvé
T=[2 3 8 12 15 22]
n=6
On cherche x=5
Valeur de la case n/2=12 ( donc 3ème case)
On a 12>x donc on cherche dans
[ 2 3 8]
Valeur de la case milieu =3<x
Donc on cherche x dans [8]
Valeur de la case milieu=8>x
Donc on cherche x dans []
→ x n'est pas dans le tableau
Algorithme itératif de la recherche dans le tableau.
Fonction_recherche(m : entier_nat, T : Tableau, x:entier) : entier
Var :i,j : entier_nat /*i et j délimitent le sous-tableau dans lequel on cherche x
*/
m : entier_nat /* numéro de la case « milieu »*/
|Début|
i:=0
j:=n-1
Tant que i <=j faire
m:=(j+i)/2 /* fait la division entière*/
Si T[m]<x alors
i:=m+1
Sinon
Si T[m]>x alors
, j:=m-1
Sinon
retourner m /* cas ou T[m]=x */
Finsi
Finsi
Fintantque
retourner -1
|Fin|
Quand un algorithme est correct , il fait ce qu'on lui a demandé dans la
spécification, on s’intéresse alors à son efficacité. On parle alors de notion de
complexité (en temps)
= nb d'opérations élémentaires effectuées par l'algorithme en fonction de la
table des donnés.
Pour les algo sur les tableaux, la taille de la donnée est n=nb de cases.
Notations : O(f(x)) environ plus petit que k*f(n) quand on est grand( k=cte).
Par exemple : O(n)=ne grandit pas plus vite que k*n
Pour un tableau non trié, combien fait-on de comparaison en fonction de n
→ meilleur cas : O(1)
→ pire cas : O(n)
→ en moyenne : O(n) (pire cas/2)
Avec la dichotomie
→ meilleur cas O(1)
→ pire cas O(log2(n))
Spécification :
Étant donné un tableau T à n cases contenant deux entiers, je veux modifier T
pour trier les valeurs des cases par ordre croissant.
Fonction max_tab(T : Tableau, n:entier) : entier
var : i:entier_nat
max : entier_nat
|Début|
max:=T[0]
Pour i allant de 1 à n-1 faire
Si T[i]>max
alors T[i]=max
Finsi
Finpour
retourner max
|Fin|
Exemple : T= [ 2 26 3 24 3 6 5]
doit retourner T= [2 3 3 5 6 24 26]
fonction_selection(T : Tableau, n: entier_nat) : Tableau
I. Tableau à n dimension
On nomme le tableau ci dessous T :
Numéro 0 1 2 3 4
case
Valeur -6 0 12 7 24
En générale on les écrit
T=[-6, 0, 12, 7, 24]
Attention : En C, les cases sont numérotées à partir de 0
Formellement, un tableau représente un produit cartésien
A*A...*A= A^k de taille fixée( ici k ) et homogène ( que des A, pas A*B*C)
Par contre A peut-être ce qu'on veut
→ tableau de réels
→ tableau d'entiers
→ tableau de booléens
→ tableau de rationnels
Type abstrait :
ex : les tableaux de réels
Types importés : entier_tan (pour le numéro de cases)
réel (pour le contenu des cases)
Opérateurs
nouveau_tableau : entier_nat (taille du tableau) → tableau
ecrire_tableau : entier_nat*réel*tableau → tableau
lire_tableau : entier_nat*tableau → réel
Attention : nouveau tableau crée un tableau « vide »
→ dans un algo, si on lit le contenu d'une case « vide », on a une erreur
→ en C si on lit le contenu d'une case non initialisée, on récupère n'importe
quoi ( ce qu'il y avait avant dans cette case mémoire de l'ordinateur)
Notations
lire_tableau (i, T) s'écrit T[i]
T:= ecrire_tableau (i, x, T) s'écrit T[i]:=x
t:=nouveau_tableau(n) s'écrit T:= nouveau tableau de n réels
Application :
Écrire un algo itératif qui étant donné un tableau T de n entiers, et un entier a
et renvoie
→ le plus petit numéro de case i tel que T[i] = a s'il existe
,→ -1 si aucune case ne contient la valeur a
Recherche dans un tableau
→ si le tableau est déjà trié
Une méthode efficace : la dichotomie
On a un tableau T à m cases et on cherche la valeur x, on va à la case m/2
• Si T[m/2] >x [2,3,8,12,15,22]
On va chercher x dans la première moitié du tableau
• Si T[m/2] =x on a trouvé
→ Pour chercher dans une moitié de tableau, on ré applique la méthode
→ Si on a coupé le tableau assez de fois, on arrive à un tableau vide et on
conclut que la valeur n'y est pas.
Exemple : T=[2 3 8 12 15 22]
n=6
On regarde T[n/2]=T[3]=12, on a 12<15. Donc on cherche x
On cherche x=15
dans [15 22] ou 22 est une valeur supérieur a x. Donc on
cherche dans [15]
valeur=x=trouvé
T=[2 3 8 12 15 22]
n=6
On cherche x=5
Valeur de la case n/2=12 ( donc 3ème case)
On a 12>x donc on cherche dans
[ 2 3 8]
Valeur de la case milieu =3<x
Donc on cherche x dans [8]
Valeur de la case milieu=8>x
Donc on cherche x dans []
→ x n'est pas dans le tableau
Algorithme itératif de la recherche dans le tableau.
Fonction_recherche(m : entier_nat, T : Tableau, x:entier) : entier
Var :i,j : entier_nat /*i et j délimitent le sous-tableau dans lequel on cherche x
*/
m : entier_nat /* numéro de la case « milieu »*/
|Début|
i:=0
j:=n-1
Tant que i <=j faire
m:=(j+i)/2 /* fait la division entière*/
Si T[m]<x alors
i:=m+1
Sinon
Si T[m]>x alors
, j:=m-1
Sinon
retourner m /* cas ou T[m]=x */
Finsi
Finsi
Fintantque
retourner -1
|Fin|
Quand un algorithme est correct , il fait ce qu'on lui a demandé dans la
spécification, on s’intéresse alors à son efficacité. On parle alors de notion de
complexité (en temps)
= nb d'opérations élémentaires effectuées par l'algorithme en fonction de la
table des donnés.
Pour les algo sur les tableaux, la taille de la donnée est n=nb de cases.
Notations : O(f(x)) environ plus petit que k*f(n) quand on est grand( k=cte).
Par exemple : O(n)=ne grandit pas plus vite que k*n
Pour un tableau non trié, combien fait-on de comparaison en fonction de n
→ meilleur cas : O(1)
→ pire cas : O(n)
→ en moyenne : O(n) (pire cas/2)
Avec la dichotomie
→ meilleur cas O(1)
→ pire cas O(log2(n))
Spécification :
Étant donné un tableau T à n cases contenant deux entiers, je veux modifier T
pour trier les valeurs des cases par ordre croissant.
Fonction max_tab(T : Tableau, n:entier) : entier
var : i:entier_nat
max : entier_nat
|Début|
max:=T[0]
Pour i allant de 1 à n-1 faire
Si T[i]>max
alors T[i]=max
Finsi
Finpour
retourner max
|Fin|
Exemple : T= [ 2 26 3 24 3 6 5]
doit retourner T= [2 3 3 5 6 24 26]
fonction_selection(T : Tableau, n: entier_nat) : Tableau
