Les Tableaux

Introduction
❑Problème : Déterminer à partir de 30 notes fournies en entrée, le nombre d’étudiants qui ont
une note supérieure à la moyenne de la classe.

❑Pour parvenir à un tel résultat, nous devons :

❑Lire les 30 notes
❑Déterminer la moyenne de la classe : m
❑Compter combien parmi les 30 notes qui sont supérieures à la moyenne m.

➔ conserver toutes les notes en mémoires

Introduction
❑Solution 1 : Utiliser 30 variables réelles nommées x1, x2, …, x30

❑Solution 2 : Utiliser la notion de tableau

Définition
• Un tableau est une structure de données homogène qui sert à stocker, dans une même variable, un
nombre fini d'éléments de même type.

•Chaque élément ou composant du tableau est accessible en lecture ou écriture.

4
 Tableaux unidimensionnels
❑Déclaration d’un tableau: il faut préciser
❑le nom
❑l’indice
❑le type des éléments
❑Syntaxe
var
Nom_Tab: Tableau [PremInd…DernInd ] de Type_éléments
❑PremInd: est le premier indice (généralement 1)
❑DernInd est le dernier indice (qui indique la taille réelle du tableau).

❑Exemple
Tnote : Tableau [1..30] de Réel
Tableaux unidimensionnels
❑Il est également possible de définir un type tableau comme suit:

Type
Tab=Tableau[1..N] de type
Var
T : Tab
 Tableaux unidimensionnels
❑Affectation et accès aux composants :
❑Un élément dans un tableau est identifié par son indice de position :

NomTab [position de l’élément]

❑Remplissage d’un tableau :

❑Un tableau peut être rempli élément par élément à l’aide d’une série d’affectations :
❑T[1] <- Valeur 1
❑T[2] <- Valeur 2
❑….
❑T[n] <- Valeur n {n est la taille effective du tableau}

❑Il est également possible de lire les éléments du tableau à partir du clavier
 Tableaux unidimensionnels
a) Remplissage du tableau ( à partir du clavier) Algorithme

T:tableau de [1..5]d’entier Memoire algorithme saisieTab

variables:
T 10 99 7 18 6 i: entier
T: tableau de [1..5] d’entier
1 2 3 4 5 Debut
Pour i de 1 à 5 faire
PC
écrire(‘’Donner T[‘’,i, ‘’] :’’)
Donner T[1] : 10 lire (T[i])
Donner T[2] : 99 Fin Pour
Fin saisieTab
Donner T[3] : 7
Donner T[4] :18
Donner T[5] :6
 Tableaux unidimensionnels
a) Affichage d’un tableau ( à partir du clavier) Algorithme

T:tableau de [1..5]d’entier algorithme saisieTab

variables:
Memoire
i: entier
99 7 18 6 T: tableau [1..5] d’entier
T 10

3
Debut
1 2 4 5
Pour i de 1 à 5 faire

PC écrire(‘’T[‘’,i, ‘’] :’’, T[i])

10 99 7 18 6 Fin Pour
Fin saisieTab
Tableaux unidimensionnels
Exercice
Ecrire un algorithme qui permet de :
➢Demander à l’utilisateur la taille d’un tableau
➢Remplir le tableau par des entiers paires lus au clavier
➢Afficher le tableau
Tableaux unidimensionnels
La taille du tableau est inconnue à l’avance , comment
le déclarer ?

1.Déclarer un tableau de taille maximale

2.Travailler sur le nombre de cases
effectives
 Tableaux unidimensionnels
Un tableau possède généralement deux tailles :

- La taille avec laquelle il a été déclaré. C'est la taille maximale puisque elle permet de faire
la réservation mémoire nécessaire. Cette taille est:
◦ soit donnée dans l'énoncé
◦ soit estimé d'après les données de la vie courante ou d'un cas de problème similaire

-La taille réelle, inférieure ou égale à la taille de déclaration

Tableaux unidimensionnels
La manière plus adéquate (professionnelle) de déclarer un tableau est la suivante :

CONST
NbMax= TailleMax
Var
T : Tableau [1..NbMax] de type_element
Par la suite, on va saisir la taille réelle avec une boucle de saisie :
Répéter
Ecrire ("donnez la taille du tableau ≤ ",NbMax)
Lire ( n)
Jusqu'à (n≤ NbMax) et (n>0)
 Algorithme

algorithme saisieTab
CONST
max=100
variables:
i,n: entier
T: tableau de [1..max] d’entier
Debut
Répéter
ecrire(«taille:»)
lire (n)
jusqu’à (n<=max) ET (n>0)
Pour i de 1 à n faire
écrire(«Donner T[»,i, «] : »)
Répéter
lire (T[i])
jusqu’à (T[i]mod 2=0)
Fin Pour
Fin saisieTab
Algorithmes de recherche
❑But: chercher dans un tableau la position d’un élément donné

❑Cas particuliers:
❑le cas où l’élément recherché n’est pas dans le tableau
❑le cas d’éléments identiques (doit-il donner le premier, le dernier, tous)

❑Il existe deux types de recherche :

❑Recherche séquentielle
❑Recherche dichotomique
Algorithmes de recherche
❑Recherche séquentielle: lire le tableau progressivement du début vers la fin.

❑Si le tableau n’est pas trié, l’arrivée à la fin du tableau signifie que l’élément n’existe pas

❑Dans un tableau trié, le premier élément trouvé supérieur à l’élément recherché permet
d’arrêter la recherche
Algorithmes de recherche
❑Soit T un tableau contenant n éléments de type entier, on veut écrire une procédure dont
l’entête sera:
Procédure recherche(T : tab, n : entier, x : entier)

❑Cette procédure affiche :

❑l’indice de la première occurrence de x dans T si x est dans T
❑le message « élément introuvable… » si x n’est pas dans T.

❑Principe : comparer x aux différents éléments du tableau jusqu’à trouver x ou atteindre la fin
du tableau.
Algorithmes de recherche
Procédure recherche(T : tab, n:entier, x : Entier)
Var
i : entier
Trouve : booléen
Début
i <- 1
Trouve <- Faux
Tantque (i<= n) et (Trouve=Faux) faire
Si T[i] = x Alors
Trouve <- Vrai
Sinon
i <- i+1
Finsi
FinTantque
Si (Trouve=Vrai) Alors Ecrire(i)
Sinon
Ecrire ("Elément introuvable")
FinSi
Fin
Algorithmes de recherche
❑Recherche dichotomique: Dans le cas d’un tableau trié, on
peut limiter le nombre de lectures, en cherchant à limiter
l’espace de recherche.

❑On compare la valeur recherchée à l’élément central du tableau.

❑Si ce n’est pas la bonne, un test permet de trouver dans quelle moitié du tableau on
trouvera la valeur.
❑On continue récursivement jusqu’à un sous tableau de taille 1.
Algorithmes de recherche
❑Soit T un tableau contenant n éléments triés dans le sens croissants, On veut écrire une
procédure dont l’entête est de la forme

Procédure Rechdicho (T : tab, n : entier, x : entier)

Algorithmes de recherche
❑Principe : Le but de la recherche dichotomique est de diviser l’intervalle de recherche par 2 à
chaque itération. Pour cela, on procède de la façon suivante :
❑Soient premier et dernier les extrémités gauche et droite de l’intervalle dans lequel on cherche la valeur
x, on calcule m, l’indice de l’élément médian :
m=(premier+dernier) div 2
❑Il y a 3 cas possibles:
❑x<T[m] : l’élément x, s’il existe, se trouve dans l’intervalle [premier..m-1]
❑x>T[m] : l’élément x, s’il existe, se trouve dans l’intervalle [m+1..dernier].
❑x=T[m] : l’élément de valeur x est trouvé, la recherche est terminée.

❑La recherche dichotomique consiste à itérer ce processus jusqu’à ce que l’on trouve x ou que
l’intervalle de recherche soit vide (min > max).
Algorithmes de recherche
Recherche dichotomique
 Algorithmes de recherche
Procédure Rechdicho (T : tab, n : entier, x :entier)
Var
Trouve : Booléen
g,m,d : entier {gauche, milieu, droite}
Début
g <-1, d <- n, Trouve <- Faux
Tantque (g<=d) et (Trouve=Faux) faire
m <- (g+d) div 2
Si (x < T[m]) Alors d <- m-1
Sinon Si (x > T[m]) Alors g <- m+1
Sinon Trouve <- Vrai
Finsi
FinTantque
Si (Trouve = vrai) Alors Ecrire(m)
Sinon Ecrire("Elément introuvable")
FinSi
Fin
Algorithme de tri
❑Problème: La recherche d’un élément dans un tableau non ordonné est
difficile et très lente.

❑Trier un tableau : ordonner, classer ses éléments

❑Ordre croissant
❑Ordre décroissant
Algorithme de tri
❑Exemple d’algorithme de tri:
❑Tri à bulles
❑Tri par insertion
❑Tri par sélection
❑….
Algorithme de tri
❑Tri à bulles:
❑On parcourt le tableau en échangeant deux éléments consécutifs s'ils sont dans le mauvais
ordre
❑Le plus grand élément de la liste est donc repoussé à la fin.
Algorithme de tri
Tri à bulles
1 2 3 4
Algorithme de tri
Procédure Tri_Bulles (var T:Tab, n:entier)
Var
i,aux : entier
test: booléen
Début
Répéter
test <-vrai
Pour i de 1 à n-1 faire
Si (T[i] > T[i+1]) Alors
test <- faux
aux <- T[i]
T[i] <- T[i+1]
T[i+1] <- aux
FinSi
FinPour
jusqu’à (test=vrai)
Fin
Les Matrcies
 Les Matrices
❑Problèmes: Soit une classe de 5 étudiants qui prennent des cours dans 10 modules.
Quelle est la structure de données qui nous permet de sauvegarder les notes des 5 étudiants?
❑Nous avons donc 50 notes (5*10 =50)
❑Solution: un tableau Notes à deux dimensions (une matrice) de 5 lignes (les étudiants) et 10 colonnes (les
modules)

❑Une cellule repérée par la ligne i et la colonnes j définit la note de l’étudiant i dans le module j Notes[i,j]

Colonne 10
Colonne 1

Colonne 2

… … … … … … …

Ligne 1 10 12 9 15 8.5 13 17 7.5 19 20

Notes[1,10]
Ligne 2
Ligne 3
Ligne 4
Ligne 5
Les Matrices
❑Déclaration:
Var
Notes: tableau[1..5,1..10] de réels

❑ Opérations Simple:
❑ Lire la valeur de l’élément Notes[5,9]: lire(Notes[5,9])
❑ Afficher la valeur de l’élément Notes[5,9]: écrire(Notes[5,9])
❑ Modifier la valeur de l’élément Notes[5,9]: Notes[5,9]  12.5
Les Matrices
Soit M une matrice de taille n*m tel que n<=20 et m<=30

Taille réelle Taille maximale

Déclaration de la matrice M:

M: tableau[1..20,1..30] d’entiers
Les Matrices
j
1 m
Deux indices de parcours:
1
• Ligne: i=1 à n
i
• Colonne: j=1 à m
n
Affichage par ligne

Pour i de 1 à n Faire
Pour j de 1 à m Faire
Ecrire(T[i,j])
FinPour
FinPour
Affichage par colonne

Pour j de 1 à m Faire
Pour i de 1 à n Faire
Ecrire(T[i,j])
FinPour
FinPour
 Pour i de 1 à n Faire
Pour j de 1 à m Faire
Lecture Ecrire(‘’donner un élément :’’)
Lire (T[i,j])
Par Ligne FinPour
FinPour

Pour j de 1 à m Faire
Pour i de 1 à n Faire
Ecrire(‘’donner un élément :’’)
Par Colonne Lire (T[i,j])
FinPour
FinPour
Parcours de la matrice en ligne
{initialisation du résultat pour tous les éléments}
Pour i de 1 à n faire
[condition sur les lignes] • Tous les
{initialisation du résultat pour chaque ligne} éléments/toutes
Pour j de 1 à m faire les lignes
[Condition sur les éléments]
{Actions pour les éléments T[i,j]
Fin Pour • Pour chaque
{traitement du résultat pour chaque ligne i} ligne
Fin Pour
{traitement du résultat pour tous les éléments}
Exemple1
Calculer et Afficher le nombre d’éléments impairs pour toutes les lignes impairs

{initialisation du résultat pour tous les éléments}

Pour i de 1 à n faire
[condition sur les lignes]
{initialisation du résultat pour chaque ligne} • Tous les éléments/toutes les lignes
Pour j de 1 à m faire
[Condition sur les éléments]
{Actions pour les éléments T[i,j]
• Pour chaque ligne
Fin Pour
{traitement du résultat pour chaque ligne i}
Fin Pour
{traitement du résultat pour tous les éléments}
 Exemple1
Calculer et Afficher le nombre d’éléments impairs pour toutes les lignes impairs

{initialisation du résultat pour tous les Nbre  0

éléments}
Pour i de 1 à n faire
Pour i de 1 à n faire Pour i de 1 à n pas 2 faire
Si (i mod 2 <> 0) alors
[condition sur les lignes] Pour j de 1 à m faire
Pour j de 1 à m faire Si (T[i,j] mod 2 <> 0) alors
[Condition sur les éléments] Nbre<-Nbre+1
{Actions pour les éléments T[i,j]} FinSI
Fin Pour Fin Pour
FinSI
Fin Pour
Fin Pour
{traitement du résultat pour tous les éléments}
Ecrire (Nbre)
Exemple2
Calculer et Afficher la moyenne des éléments pairs pour chaque ligne

{initialisation du résultat pour tous les éléments}

Pour i de 1 à n faire
[condition sur les lignes]
{initialisation du résultat pour chaque ligne} • Tous les éléments/toutes les lignes
Pour j de 1 à m faire
[Condition sur les éléments]
{Actions pour les éléments T[i,j]
• Pour chaque ligne
Fin Pour
{traitement du résultat pour chaque ligne i}
Fin Pour
{traitement du résultat pour tous les éléments}
 Exemple2
Calculer et Afficher la moyenne des éléments pairs pour chaque ligne
Pour i de 1 à n faire
S 0 ; Nb  0
Pour i de 1 à n faire Pour j de 1 à m faire
{initialisation du résultat pour chaque ligne} Si (T[i,j] mod 2 =0) Alors
Pour j de 1 à m faire S S+T[i,j] ; Nb  Nb+1
[Condition sur les éléments]
FinSI
{Actions pour les éléments T[i,j]
Fin Pour Fin Pour
{traitement du résultat pour chaque ligne i} Si (Nb=0) alors écrire(‘’pas des éléments pairs sur la
ligne’’, i )
Fin Pour Sinon écrire (‘’la moyenne des éléments pairs pour la
ligne’’, i, ‘’est’’, S/Nb)
FinSi

Fin Pour
Parcours de la matrice en colonne
{initialisation du résultat pour tous les éléments}
Pour j de 1 à m faire
[condition sur les colonnes] • Tous les
{initialisation du résultat pour chaque colonne j} éléments/toutes
Pour i de 1 à n faire les colonnes
[Condition sur les éléments]
{Actions pour les éléments T[i,j]
Fin Pour • Pour chaque
{traitement du résultat pour chaque colonne j} colonne
Fin Pour
{traitement du résultat pour tous les éléments}
Exemple1
Calculer et afficher le nombre d’éléments >val pour toutes les colonnes de rang pairs

{initialisation du résultat pour tous les éléments}

Pour j de 1 à m faire
[condition sur les colonnes]
{initialisation du résultat pour chaque colonne j} • Tous les éléments/toutes les colonnes
Pour i de 1 à n faire
[Condition sur les éléments]
{Actions pour les éléments T[i,j] • Pour chaque colonne
Fin Pour
{traitement du résultat pour chaque colonne j}

Fin Pour
{traitement du résultat pour tous les éléments}
 Exemple1
Calculer et afficher le nombre d’éléments >val pour toutes les colonnes de rang pairs

{initialisation du résultat pour tous les éléments} Total0

Pour j de 1 à m faire Pour j de 1 à m faire
[condition sur les colonnes] Si (j mod 2 =0) alors
Pour i de 1 à n faire Pour i de 1 à n faire
[Condition sur les éléments] Si (T[i,j]>val) Alors TotalTotal+1
{Actions pour les éléments T[i,j] Finsi
Fin Pour Fin Pour
Finsi
Fin Pour
Fin Pour
{traitement du résultat pour tous les éléments}
Ecrire (Total)
Exemple2
Construire un tableau tel que le 𝑗 è𝑚𝑒 élément de V contient la somme de la 𝑗 è𝑚𝑒 colonne de A

{initialisation du résultat pour tous les éléments}

Pour j de 1 à m faire
[condition sur les colonnes]
{initialisation du résultat pour chaque colonne j} • Tous les éléments/toutes les colonnes
Pour i de 1 à n faire
[Condition sur les éléments]
{Actions pour les éléments T[i,j] • Pour chaque colonne
Fin Pour
{traitement du résultat pour chaque colonne j}

Fin Pour
{traitement du résultat pour tous les éléments}
Exemple2
Construire un vecteur tel que le jème élément de V contient la somme de la jème colonne de A

Pour j de 1 à m faire
{initialisation du résultat pour chaque Pour j de 1 à m faire
colonne j} S<-0
Pour i de 1 à n faire Pour i de 1 à n faire
{Actions pour les éléments T[i,j] S<-S+T[i,j]
Fin Pour Fin Pour
{traitement du résultat pour chaque colonne V[j]<-S
j}
Fin Pour
Fin Pour
 Parcours d’une ligne
Une ligne
{Initialisation du résultat pour une ligne p}
Pour j de 1 à m faire j
{condition sur les éléments}
{Action pour les éléments A[p,j]} 5 12 14 2.3
Finpour 45 28 9.6 66
p 45 55 87 3.2
{traitement du résultat pour une ligne p}
69 7 56 33
Parcours d’une ligne
Soit A une matrice de taille n*m (0<n<=20, 0<m<=30). Ecrire un traitement qui lit le numéro
d’une ligne p, puis calcule et affiche le produit des éléments non nuls de la ligne p

{Initialisation du résultat pour une ligne p} Pr 1

Pour j de 1 à m faire Pour j de 1 à m faire

si A[p,j]<>0 alors
{condition sur les éléments}
PrPr*A[p,j]
{Action pour les éléments A[p,j]} finsi
Finpour Finpour
{traitement du résultat pour une ligne p} Ecrire(Pr)
 Parcours d’une colonne
{Initialisation du résultat pour une colonne q}
Une colonne
Pour i de 1 à n faire q
{condition sur les éléments}
{Action pour les éléments A[i,q]} 5 12 14 2.3
Finpour 45 28 9.6 66
i 45 55 87 3.2
{traitement du résultat pour une colonne q}
69 7 56 33
Parcours d’une colonne
Soit A une matrice de taille n*m (0<n<=20, 0<m<=30). Ecrire un traitement qui lit le numéro
d’une colonne q, puis calcule et affiche la somme des éléments de la colonne q

{Initialisation du résultat pour une colonne q}

S0
Pour i de 1 à n faire
Pour i de 1 à n faire
{condition sur les éléments}
S<- S+ A[i,q]
{Action pour les éléments A[i,q]}
Finpour
Finpour
Ecrire (S)
{traitement du résultat pour une colonne q}
Parcours de la diagonale principale (DP)
A[1,1], A[2,2], ….. , A[n,n] ➔ i=j => une seule boucle A[i,i] ou A[j,j]

{Initialisation du résultat pour la DP}

Pour i de 1 à n faire
{condition sur les éléments}
{Action pour les éléments A[i,i]}
1 2 n=3
Finpour 0.5 8 5
1
{traitement du résultat pour la DP}
1 7 9
2
0 -1 3.4
n=3
Parcours de la diagonale principale (DP)
Calculer et Afficher la somme des éléments de la diagonale principale

{Initialisation du résultat pour la DP} S 0

Pour i de 1 à n faire Pour i de 1 à n faire
{condition sur les éléments} S  S + A[i,i]
{Action pour les éléments A[i,i]} Finpour
Finpour Ecrire (S)
{traitement du résultat pour la DP}
Parcours de la diagonale secondaire (DS)
A[1,n], A[2,n-1], ….. , A[n,1] ➔ i=n-j+1 ; A[i, n-i+1] ou A[n-j+1,j] ➔ une seule boucle

{Initialisation du résultat pour la DS}

Pour i de 1 à n faire
{condition sur les éléments}
{Action pour les éléments A[i,n-i+1]}
1 2 n=3
Finpour 0.5 8 5
1
{traitement du résultat pour la DS}
1 7 9
2
0 -1 3.4
n=3
Parcours de la diagonale secondaire (DS)
Calculer et afficher la moyenne des éléments de la diagonale secondaire

{Initialisation du résultat pour la DS} S 0

Pour i de 1 à n faire Pour i de 1 à n faire
{condition sur les éléments} S  S + A[i,n-i+1]
{Action pour les éléments A[i,n-i+1]} Finpour
Finpour Ecrire (S/n)
{traitement du résultat pour la DS}
La Récursivité
La récursivité
❑Définition:
❑La récursivité est le fait pour une méthode de s'appeler elle-même. On parle alors de méthode
récursive.

❑Exemple : Le calcul de la factorielle de N.

❑N != N*(N-1)*(N-2)*…*2*1,
❑On peut écrire ainsi N != N*(N-1)!
❑La factorielle de N est définie en fonction de la factorielle de N-1
La récursivité

n=1
La récursivité
❑Trace d’exécution
❑Trace de la méthode « factoriel » avec n = 5
La récursivité
❑Comment définir une fonction de façon récursive ?

❑Prévoir les "cas de base", c’est à dire ceux qui ne nécessitent pas d’appel récursif de la fonction.

❑ S’assurer que, dans les appels récursifs, les arguments sont plus "simples" que ceux avec
lesquels la fonction a été appelée (ce qui signifie essentiellement qu’ils « évoluent vers le cas de
base »)
La récursivité
❑Structure d’un sous-programme récursif :
❑Le corps d’un sous-programme récursif est composé essentiellement de :

❑une condition d’arrêt

❑un ou plusieurs appels récursifs, intégrés dans une structure conditionnelle de la forme (si ...
alors...sinon... Finsi)
La récursivité
❑Syntaxe
❑Procédure

Procédure nomProcRec (param1:typeParam1…. paramN:typeParamN)

var
{Déclaration des variables locales}
Début
Si (condition d’arrêt) alors
traitement d’arrêt
Sinon
nomProcRec (para1, paraN ) {appel récursif}
FinSi
Fin
La récursivité
❑Syntaxe
❑Fonction
Fonction nomFonctRec (p1:typeParam1, …. pN:typeParamN): type_retour
var
{Déclaration des variables locales}
Début
Si (condition d’arrêt) alors
Retourner(Expression1)
Sinon
Retourner (nomFonctRec (para1, …..,paraN))
FinSi
Fin
Application1
Écrire une fonction récursive qui permet de vérifier l’existence d’un caractère c donné dans une une
chaine de caractères ch

Fonction chercher(ch:chaine de caractères, c:caractère):booléen

Début
Si long(ch)=0 alors
Retourner Faux
Sinon si ch[long(ch)-1]=c alors
retourner Vrai
Sinon
chercher (sous_chaine(ch,0,long(ch)-1), c)
Finsi
Fin
Application2
❑Ecrire un algorithme qui permet de calculer et d'afficher la somme des n premiers entiers, n
saisie au clavier (n>0).
❑Exemple :
❑Pour n = 7
❑Résultat = 28 (1+2+3+4+5+6+7)

Fonction Somme(n:entier):entier
Correction
Application 3
Écrire une fonction récursive permettant de calculer la somme des chiffres d’un entier n positif

Exemple: Si n=528
La somme des chiffres de n est 5+2+8=15

Fonction SomChif(n:entier):entier
Solution
Fonction SomChif(n:entier):entier
Début
Si n<10 alors retourner n
Sinon retourner (n mod 10 + somChif(n div 10))
Finsi

Fin
FIN