Royaume du Maroc
Université Cadi Ayyad
Faculté des Sciences Semlalia
Marrakech
Algorithmique II
Pr. Ilyass OUAZZANI TAYBI
E-mail : [Link]@[Link]
Département : Informatique FSSM
Université Cadi Ayyad
Filière TC-INFO S2
1
Année universitaire : 2024/2025
Plan du cours
❑ Rappel (Algorithmique I)
❑ Tableaux
❑ Fonctions et procédures
❑ Récursivité
❑ Algorithmes de tri
❑ Pointeurs et Enregistrements
❑ Fichiers
❑ Complexité algorithmique
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 2
Plan du cours
CHAPITRE 1 : TABLEAUX
[Link]
[Link] à une dimension
[Link] à deux dimensions
4. Recherche dans un tableau
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 3
I. Tableaux
1. Introduction
➢ Supposons que l'on veut conserver les notes de 40 étudiants pour en extraire quelques
informations. Par exemple, calculer le nombre d'étudiants ayant une moyenne >= 10.
➢ Jusqu’à présent, le seul moyen dont nous disposons consiste à déclarer 40 variables, par
exemple N1, …, N40. Après 40 instructions de Lecture, nous devons écrire 40 instructions
de test (Si) pour extraire le nombre de notes >=10.
nbr ← 0;
Si (N1 >= 10) alors
nbr ← nbr+1;
FinSi
….
Si (N40 >= 10) alors
nbr ← nbr+1;
FinSi
Cette méthode n’est pas pratique 4
I. Tableaux
1. Introduction
➢ Lorsque les données sont nombreuses et de même
nature, pour éviter de multiplier le nombre des Identificateur
Notes
variables, il est plus pratique de ranger ces données du tableau
0 12,50
dans une seule structure de donnée appelée tableau;
1 15,00
➢ Un tableau est un ensemble d'éléments de même type 2 18,25
désignés par un identificateur unique; 3 11,50 Cette case du
Indices tableau représente
4 18,75
➢ Chaque valeur du tableau est repérée par un indice (de la variable Notes[4]
5 10,00 dont la valeur est
type entier) indiquant sa position dans le tableau; 18,75.
6 15,50
➢ On peut créer des tableaux à 1, ou N dimensions. 7 13,00
5
I. Tableaux
1. Introduction
La déclaration d'un tableau s'effectue en précisant 3 éléments fondamentaux :
➢ Nom_du_tableau : Identificateur respectant les règles classiques d’identificateur d’une
donnée;
➢ Le type : Correspond au type des valeurs qu’il contiendra;
➢ La taille : Le nombre de ses valeurs. Ce nombre se nomme également la taille maximale du
tableau;
6
I. Tableaux
2. Tableaux à une dimension – Déclaration –
Les tableaux à une dimension (ou tableaux à une entrée ou bien encore vecteurs) peuvent être
déclarer selon la syntaxe suivante :
Variable Tableau NomDuTableau[taille] : Type;
Exemple :
Algorithme exemple;
Variable Tableau Notes[8] : Réel;
Début
…
Fin.
7
I. Tableaux
2. Tableaux à une dimension – Représentation –
➢ Un tableau peut être vu comme un ensemble de « cases » où chaque case stocke une valeur.
Soit la définition suivante :
Variable Tableau Notes[8] : Réel;
➢ Cette déclaration crée un tableau appelé Notes qui stocke au maximum huit réels dans huit
cases différentes. Aucune de ces cases n’est initialisée, ce qui est indiqué par un « ? ».
➢ Soit i un indice (i est donc de type entier puisqu’il s’agit d’un numéro de case). La valeur
stockée dans la case d’indice i du tableau Notes se nomme Notes[i].
0 1 2 3 4 5 6 7
? ? ? ? ? ? ? ?
Notes[0] Notes[1] Notes[2] Notes[3] Notes[4] Notes[5] Notes[6] Notes[7]
8
I. Tableaux
2. Tableaux à une dimension – Remarques –
➢ La taille correspond au nombre maximum de cases composant le tableau, elle doit être une
constante numérique;
➢ On peut définir des tableaux de tous types : tableaux d'entiers, de réels, de caractères, de
booléens ou de chaînes de caractères, …
➢ L'accès à un élément du tableau se fait au moyen de l’indice;
➢ Selon les langages, le premier indice du tableau est soit 0, soit 1. Le plus souvent c'est 0
(c'est ce qu'on va adopter en pseudo-code). Dans ce cas, Notes[i] désigne l'élément i+1 du
tableau Notes;
9
I. Tableaux
2. Tableaux à une dimension – Remarques –
➢ Il ne faut pas confondre la valeur notée entre crochets lors de la définition du tableau (la
taille maximale) et la valeur notée entre crochets lors des instructions (l’indice).
➢ Toute expression qui donne une valeur entière peut jouer le rôle d’indice lors de l’accès aux
valeurs stockées dans un tableau.
➢ La notation Notes[i] est équivalente à une variable et peut être utilisée comme telle dans un
algorithme. Elle est considérée comme ayant le type des éléments stockés dans le tableau.
➢ Les données stockées dans un tableau peuvent être manipulées en utilisant les boucles.
➢ L’accès et la modification de l’élément numéro i est en temps constant, indépendant de i et
du nombre d’éléments dans le tableau.
10
I. Tableaux
2. Tableaux à une dimension – Affectation, lecture et écriture –
Les instructions de lecture, écriture et affectation s'appliquent aux tableaux comme aux variables.
Exemples :
➢ Notes[0] ← 13;
Cette instruction affecte 13 au 1er élément du tableau Notes.
➢ note ← Notes[0];
La variable note prend la valeur du premier élément du tableau Notes (13 selon l’instruction
précédente).
➢ Lire(Notes[1]);
Cette instruction permet de lire une valeur à partir du clavier et de l’assigner au 2ème élément du
tableau Notes.
➢ Ecrire(Notes[2]);
Cette instruction permet d’afficher la valeur du 3ème élément du tableau Notes.
11
I. Tableaux
2. Tableaux à une dimension – Taille utile –
➢ Le fait de fournir la taille maximale d’un tableau sous la forme d’une constante est une
contrainte lourde (Cette valeur est fixée lors de l’écriture de l’algorithme).
➢ En pratique un tableau ne stockera pas toujours autant d’éléments que sa taille maximale.
➢ Il est donc nécessaire de savoir la taille utile du tableau (par opposition à la taille maximale
donnée à la définition du tableau).
➢ Dans un tableau dont la taille utile est P et dont la taille maximale est N, les valeurs
intéressantes seront rangées aux indices compris entre 0 et P–1.
➢ Les cases dont les indices vont de P à N–1 stockent des valeurs (car une case n’est jamais
vide) mais elles ne seront pas concernées par les traitements effectués.
12
I. Tableaux
2. Tableaux à une dimension – Relation entre tableaux et boucles –
➢ Les boucles sont extrêmement utiles pour les algorithmes associés aux tableaux.
➢ Pour parcourir les éléments du tableau selon l’ordre croissant (ou décroissant) des indices, on
utilise des boucles.
➢ Le traitement de chacun des éléments étant souvent le même, seule la valeur de l’indice est
amenée à changer.
➢ Une boucle est donc parfaitement adaptée à ce genre de traitements.
13
I. Tableaux
2. Tableaux à une dimension
Exemple 1:
Un algorithme qui déclare un tableau de 100 entiers et qui l’initialise par des entiers de 1 à 100.
Algorithme exe1;
Variables i : entier;
tableau T[100] : entier;
Début
Pour i de 0 à 99 faire
T[i] ← i+1;
FinPour
Fin
14
I. Tableaux
2. Tableaux à une dimension
Exemple 2 :
Un algorithme qui demande à l’utilisateur de saisir 10 notes et qui affiche leur moyenne.
Algorithme moyenne;
Variables Moy, Som : réel; Som ← 0;
tableau Notes[10] : réel; Pour i de 0 à 9 faire
i : entier; Som ← Som + Notes[i];
Début FinPour
Pour i de 0 à 9 faire Moy ← Som / 10;
Ecrire ("Entrez la note N°", i+1); Ecrire(“la moyenne est : ”, Moy);
Lire(Notes[i]); Fin
FinPour
15
I. Tableaux
2. Tableaux à une dimension
Exercice 1 :
Ecrire un algorithme qui demande les notes de N étudiants, et qui calcule le nombre d'étudiants
ayant une note >= 10.
16
I. Tableaux
2. Tableaux à une dimension
Algorithme exe3;
Exercice 1 - Solution - : Variables i, nbr, t_utile : entier;
tableau notes[100] : réel;
Début
Ecrire(“Veuillez saisir le nombre d’étudiants de la classe : ”);
Lire(t_utile);
nbr ← 0;
Pour i de 0 à t_utile-1 faire
Ecrire(“Veuillez saisir la note d’étudiant N°: ”, i+1);
Lire(notes[i]);
FinPour
Pour i de 0 à t_utile-1 faire
Si (notes[i] >= 10) alors
nbr ←nbr+1;
FinSi
FinPour
Ecrire ("le nombre d’étudiants ayant la moyenne est :", nbr);
Fin 17
I. Tableaux
3. Tableaux à deux dimensions
➢ Quand les données sont nombreuses et de même nature, mais dépendent de deux critères,
elles sont rangées dans un tableau à deux dimensions (ou tableau à deux entrées, ou bien
encore matrice). Avant d’en donner une définition générale, en voici un exemple :
Tableau des Notes des étudiants de INFO (notesINFO)
❖ Ce tableau a 100 lignes et 6 colonnes. Un 0 1 2 3 4 5
élément de tableau est repéré par le numéro 0
de sa ligne et le numéro de sa colonne, qui
1
sont les deux indices du tableau.
2
❖ Si notesINFO est l’identificateur du tableau ci-
…
contre, l’élément noté notesINFO[2][3] est
celui de la 3ème ligne et de la 4ème colonne : il 97
représente la note du 3ème étudiant au 4ème 98
module. 99
18
I. Tableaux
3. Tableaux à deux dimensions
➢ En pseudo-code, un tableau à deux dimensions se déclare ainsi :
Variable tableau nomDuTableau[taille_n][taille_m] : Type;
Exemple :
➢ Une matrice A de 3 lignes et 4 colonnes dont les éléments sont entiers:
Variable tableau A[3][5] : entier;
➢ A[i][j] permet d'accéder à l’élément de la matrice qui se trouve à l’intersection de la ligne i+1
et de la colonne j+1;
19
I. Tableaux
3. Tableaux à deux dimensions
➢ La matrice A dans la déclaration suivante :
Variable tableau A[3][5] : entiers;
peut être explicitée comme suit : les éléments sont rangées dans un tableau à deux entrées.
0 1 2 3 4
0 15 45 17 36 98
1 52 47 56 58 23
2 15 46 87 95 66
➢ Ce tableau a 3 lignes et 5 colonnes. Les éléments du tableau sont repérés par leur numéro de
ligne et leur numéro de colonne. Par exemple A[1][2] vaut 56.
20
I. Tableaux
3. Tableaux à deux dimensions
Exemple : lecture d'une matrice
Algorithme lectureMatrice;
Variable i, j, m, n : entier;
tableau A[100][100] : réel;
Début
Ecrire(“Entrer le nombre de lignes et le nombre de colonnes :") ;
lire(m, n);
Pour i de 0 à m-1 faire
Ecrire (“Saisie de la ligne ", i+1);
Pour j de 0 à n-1 faire
Ecrire ("Entrer l'élément : A[", i+1, “][", j+1, “]”);
Lire (A[i][j]);
FinPour
FinPour
Fin 21
I. Tableaux
3. Tableaux à deux dimensions
Exemple : affichage d'une matrice
Algorithme affichageMatrice;
Variables i, j, m, n : Entier;
tableau A[100][100]: Réel;
Début
Ecrire(“Entrer le nombre de lignes et le nombre de colonnes : ");
Lire(m, n);
//Lecture de la matrice
…
//Affichage de la matrice
Pour i de 0 à m-1 faire
Pour j de 0 à n-1 faire
Ecrire ("A[",i, "] [",j,"]=", A[i][j]);
FinPour
FinPour
Fin 22
I. Tableaux
3. Tableaux à deux dimensions
Exercice 2 :
Ecrire un algorithme qui déclare et remplit une matrice carrée de taille 10 en mettant toutes ces
valeurs à zéro.
23
I. Tableaux
3. Tableaux à deux dimensions
Exercice 2 - Solution - :
Algorithme tab2d;
Variables tableau M[10][10] : entier;
i, j : entier;
Début
Pour i de 0 à 9 faire
Pour j de 0 à 9 faire
M[i][j]←0;
FinPour
FinPour
Fin
24
I. Tableaux
3. Tableaux à deux dimensions
Exercice 3 :
Ecrire un algorithme qui calcule et affiche la somme de deux matrices de taille (3,4).
25
I. Tableaux
3. Tableaux à deux dimensions
Exercice 2 - Solution - :
Algorithme Somme2Matrices; //Calcul de la somme de la matrice A et B
Variables tableau A[3][4], B[3][4], C[3][4], : Entier; Pour i de 0 à 2 faire
i, j : Entier; Pour j de 0 à 3 faire
C[i][j] A[i][j]+B[i][j];
Début FinPour
//Lecture de la matrice A et B FinPour
Pour i de 0 à 2 faire //Affichage de la matrice C (Somme de A et B)
Pour j de 0 à 3 faire Ecrire (“La somme des deux matrices est : ”);
Ecrire ("Entrer l'élément : A[", i+1, “][", j+1, “]”); Pour i de 0 à 2 faire
Lire (A[i][j]); Pour j de 0 à 3 faire
Ecrire ("Entrer l'élément : B[", i+1, “][", j+1, “]”); Ecrire (C[i][j]);
Lire (B[i][j]); FinPour
FinPour FinPour
FinPour Fin
26
I. Tableaux
4. Recherche dans un tableau
Pour effectuer la recherche d’un élément dans un tableau, deux méthodes de recherche
sont considérées selon que le tableau est trié ou non :
➢ La recherche séquentielle pour un tableau non trié;
➢ La recherche dichotomique pour un tableau trié;
27
I. Tableaux
4. Recherche dans un tableau – Recherche séquentielle –
➢ La recherche séquentielle consiste à parcourir un tableau à partir du début et s’arrêter
dés qu’une première occurrence de l’élément sera trouvée.
➢ Si l'élément recherché n'est pas trouvé dans le tableau ou s'il se trouve à la dernière
position, alors le tableau sera parcouru intégralement, du début à la fin.
28
I. Tableaux
4. Recherche dans un tableau – Recherche séquentielle –
Recherche de la valeur x dans un tableau T de N éléments :
…
i←0 ;
Existe← Faux;
TantQue (i < N) ET (Existe = Faux) faire
Si (T[i] = x) alors //x est l’élément recherché
Existe ← Vrai;
Sinon
i←i+1;
FinSi
FinTantQue
Si Existe alors // c'est équivalent à écrire Si Existe=Vrai alors
Ecrire (x, " est situé dans la ”,i+1, "eme position du tableau ");
Sinon
Ecrire (x, " n'appartient pas au tableau");
FinSi
29
I. Tableaux
4. Recherche dans un tableau – Recherche séquentielle –
Exercice 1 :
Soit T un tableau de N caractères (N≤20). Ecrire un algorithme qui recherche une lettre dans le
tableau.
30
I. Tableaux
4. Recherche dans un tableau – Recherche séquentielle –
Exercice 1 - Solution - :
Algorithme rechercheLettre; Ecrire(“Donner la valeur recherchée) ;
Variables I, N: Entier ; Lire(Val) ;
Existe : Booléen ; Existe←Faux ;
Val : Caractère; I←0 ;
Tableau A[20]: Caractère; Tantque I < N et Existe = Faux Faire
Début Si T[I]=Val Alors
Répéter Existe←Vrai;
Ecrire(“Donner la taille du tableau N≤20”); Finsi ;
Lire(N) ; I←I+1 ;
Jusqu’à N>0 et N <= 20 ; FinTantQue;
//Lecture du tableau Si Existe Alors Ecrire(Val,’ existe.’);
Pour i de 0 à N-1 faire Sinon
Ecrire ("Entrer l'élément : T[", i+1, “]”); Ecrire(Val,’ non trouvée !!’);
Lire (T[i]); FinSi
FinPour Fin. 31
I. Tableaux
4. Recherche dans un tableau – Recherche dichotomique –
➢ Dans le cas où le tableau est ordonné, on peut améliorer l'efficacité de la recherche en
utilisant la méthode de recherche dichotomique.
Principe :
Nous réduisons de moitié le nombre d'éléments dans lesquels nous cherchons la valeur x à
chaque étape de la recherche. Pour ce faire, nous comparons x avec T[milieu] :
➢ Si x = T[milieu], nous avons trouvé l’élément recherché.
➢ Si x < T[milieu], il suffit de chercher x dans la première moitié du tableau entre T[0] et
T[milieu-1].
➢ Si x > T[milieu], il suffit de chercher x dans la deuxième moitié du tableau entre T[milieu+1] et
T[N-1].
32
I. Tableaux
4. Recherche dans un tableau – Recherche dichotomique –
Recherche de la valeur x dans un tableau T trié de N éléments :
…
inf←0; sup←N-1; Existe← Faux;
TantQue (inf <=sup) ET (Existe = Faux) faire
milieu←(inf+sup) div 2;
Si (x=T[milieu]) alors
Existe ← Vrai;
SinonSi (x>T[milieu]) alors
inf←milieu+1;
Sinon
sup←milieu-1;
FinSi
FinTantQue
Si Existe alors Ecrire (x, “ appartient au tableau”);
Sinon Ecrire (x, “ n'appartient pas au tableau”);
FinSi 33
I. Tableaux
4. Recherche dans un tableau – Recherche dichotomique –
Exercice 2 :
Soit T un tableau trié de N caractères (N≤20). Ecrire un algorithme qui recherche une lettre dans
le tableau.
34
I. Tableaux
4. Recherche dans un tableau – Recherche dichotomique –
Exercice 2 - Solution - :
Algorithme rechercheLettre; Ecrire(“Donner la valeur recherchée) ; Lire(x) ;
Variables I, N, inf, sup, milieu : Entier ; inf←0; sup←N-1; Existe ← Faux;
x : Caractère; TantQue (inf <=sup) ET (Existe = Faux) faire
Existe : Booléen ; milieu←(inf+sup) div 2;
Tableau A[20]: Caractère; Si (x=T[milieu]) alors
Début Existe ← Vrai;
Répéter SinonSi (x>T[milieu]) alors
Ecrire(“Donner la taille du tableau N≤20”); inf←milieu+1;
Lire(N) ; Sinon sup←milieu-1;
Jusqu’à N>0 et N <= 20 ; FinSi
//Lecture du tableau FinTantQue
Pour i de 0 à N-1 faire Si Existe alors Ecrire (x, “ appartient au tableau”);
Ecrire ("Entrer l'élément : T[", i+1, “]”); Sinon Ecrire (x, “ n'appartient pas au tableau”);
Lire (T[i]); FinSi
FinPour Fin.
35
Merci de votre
attention
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 36
Royaume du Maroc
Université Cadi Ayyad
Faculté des Sciences Semlalia
Marrakech
Informatique 2 : Algorithmique I
Pr. Ilyass OUAZZANI TAYBI
E-mail : [Link]@[Link]
Département : Informatique FSSM
Université Cadi Ayyad
Filière TC-INFO S2
Année universitaire : 2024/2025