Université Moulay Ismail Année universitaire :2023/2024
Faculté des sciences de Meknès Filière : MIP/Digitalisation
Département d’Informatique Module : INFO2
TD N°3 : Les algorithmes de tri et de recherche
(Corrigé)
Exercices 1 : Gestion des notes d’une classe
On considère un tableau de taille Nmax = 100. Ce tableau contient les notes des étudiants.
Écrivez un algorithme où vous déclarez ce tableau, demandez un entier N qui représente le
nombre des étudiants puis réalise les traitements suivants :
1. Ecrire une procédure qui calcule et affiche la moyenne des notes.
2. Ecrire une procédure qui calcule et affiche la note minimale.
3. Ecrire une procédure qui calcule et affiche la note maximale
4. Ecrire une procédure qui cherche si une note donnée existe dans le tableau ou pas et
affiche le nombre d’occurrence ;
5. Ecrire une procédure qui modifie une note donnée du tableau T connaissant son indice,
et afficher le tableau après modification ;
6. Ecrire une procédure qui inverse l’ordre des éléments d’un tableau préalablement saisi
7. Ecrire le programme principal qui saisit les N notes dans un tableau, et invoque les
différentes procédures.
Solution :
1. Ecrire une procédure qui calcule et affiche la moyenne des notes.
Procédure Moy_Tableau (T[] : Réel, N : Entier)
Variables i : Entier
S, Moy : Réel
Début
Pour i ←0 à N-1 faire
S ← S+T[i]
FinPour
Moy ← S/N ;
Ecrire("la moyenne des notes est Moy =", Moy)
Fin
2. Ecrire une procédure qui calcule et affiche la note minimale.
Procédure Min_Tableau (T[] : Réel, N : Entier)
Variables i : Entier
Min : Réel
Début
Min ← T[0]
Pour i ← 1 à N-1 faire
Si(T[i]<Min) alors
Min ←T[i]
Finsi
FinPour
Ecrire ("la note minimale est ", Min)
Fin
3. Ecrire une procédure qui calcule et affiche la note maximale.
Procédure Max_Tableau (T[] : Réel, N : Entier)
Variables i : Entier
Max : Réel
Début
Max ← T[0]
Pour i ← 1 à N-1 faire
Si(T[i]>Max) alors
Max ←T[i]
Finsi
FinPour
Ecrire ("la note maximale est ", Max)
Fin
4. Ecrire une fonction qui cherche si une note donnée existe dans le tableau ou pas et
retourne le nombre d’occurrence ;
2
Procédure Occurrence_Tableau (T[] : Réel, N : Entier)
Variables i, c : Entier
X, a : Réel
Début
Ecrire("donner l'élément que vous voulez chercher dans le tableau ")
Lire(X);
a←0
c←0
Pour i ←0 à N-1 faire
Si(T[i]=X)
a←1
c←c+1
Finsi
FinPour
Si(a=1)
Ecrire("la note" ,X, " se trouve dans le tableau ")
Ecrire("le nombre d'occurrence de la note" ,X, " est =",c)
Sinon
Ecrire("la note ",X," ne se trouve pas dans le tableau")
FinSi
Fin
5. Ecrire une procédure qui modifie une note donnée du tableau T connaissant son indice,
et afficher le tableau après modification ;
Procédure Modification_Tableau (T[] : Réel, N : Entier)
Variables i, p : Entier
X : Réel
Début
Ecrire("Entrer l’indice de l’élément à modifier " )
Lire (p)
Si (p<0) ou (p>=N) alors
Ecrire("Position hors limites du tableau " )
Sinon
Ecrire("L’ancienne valeur dans cette position est : " , T[p])
Ecrire("Entrer la nouvelle valeur: " )
3
Lire(X)
T[p] ← X
Finsi
// affichage des éléments du tableau après la modification
Pour i←0 à N-1 faire
Ecrire (T[i])
FinPour
Fin
6. Ecrire une procédure qui inverse l’ordre des éléments d’un tableau préalablement saisi
Procédure Inverse_ordre (T[] : Réel, N : Entier)
Variables i, Temp : Entier
Début
Pour i ← 0 à (N-1)/2 faire
Temp ← T(i)
T(i) ← T(N-1-i)
T(N-1-i) ← Temp
FinPour
// affichage des éléments du tableau après la modification
Pour i←0 à N-1 faire
Ecrire (T[i])
FinPour
Fin
7. Ecrire le programme principal qui saisit les N notes dans un tableau, et invoque les
différentes procédures.
Algorithme notesEtudiants
Variables
Tableau T[1...100] : réel
Début
4
Répeter
Ecrire ("Entrer le nombre de notes à saisir")
Lire(N)
Jusqu’à (N>=0 ET N<100)
Pour i ←1 à N faire
Ecrire ("Entrer la note N° ", i)
Lire(T[i])
FinPour
Moy_Tableau (T[], N)
Min_Tableau (T[],N)
Max_Tableau (T[], N)
Occurrence_Tableau (T[], N)
Modification_Tableau (T[], N)
Inverse_ordre (T[], N)
Exercice 2 : tri d’un tableau (par insertion)
Ecrire une procédure qui effectue le tri d'un tableau envoyé en argument (on considère que le
programme appelant devra également fournir le nombre d'éléments du tableau).
5
Exercice 3 : Tableau trié ou non
Ecrire une procédure qui informe si un tableau envoyé en argument est formé d'éléments tous
rangés en ordre croissant ou non.
6
Exercice 4 : Tri croissant ou décroissant
Ecrire une procédure qui effectue le tri d'un tableau (La procédure prendra un paramètre
booléen: Vrai - le tri devra être effectué dans l'ordre croissant, FAUX - dans l'ordre décroissant).
7
Exercice 5 : Tableau de deux dimensions
Soit un tableau T à deux dimensions (N et M) de valeurs numériques.
1. Écrire une procédure qui saisit les éléments de la matrice
2. Écrire une procédure qui affiche la matrice
3. Écrire une fonction qui retourne la plus grande valeur au sein de ce tableau.
4. Écrire le programme principal
Solution :
1. Écrire une procédure qui saisit les éléments de la matrice
Procédure SaisieMatrice(n, m: entier, tableau A)
Variable i, j : Entier
Début
Pour i=0 à N-1 faire
Pour j=0 à M-1 faire
Ecrire ("Entrer les éléments de la ligne", i+1,"et la colonne", j+1)
Lire(A[i][j])
Fin pour
Fin pour
Fin
8
2. Écrire une procédure qui affiche la matrice
Procédure AfficheMatrice (N, M : Entier, A [] [] : Entier)
Variable i, j : Entier
Début
Pour i=0 à N-1 faire
Pour j=0 à M-1 faire
Ecrire(A[i][j], " ")
FinPour
Ecrire ("/n")
Fin pour
Fin
3. Écrire une fonction qui retourne la plus grande valeur au sein de ce tableau.
Procédure MaxMatrice (N, M : Entier, A [] [] : Entier)
Variable i, j ,i_Max, j_Max, Max : Entier
Début
Max=A[i][j]
i_Max=0
j_Max=0
Pour i=0 à N-1 faire
Pour j=0 à M-1 faire
Si (A[i][j]>Max) alors
Max A[i][j]
i_Max= i
j_Max=j
Finsi
FinPour
Fin pour
Ecrire ("La plus grande valeur du tableau est :", Max, "et sa position est :",
i_Max+1, j_Max+1)
Fin
9
4. Écrire le programme principal
Algorithme Matrice
Variable tableau A[20][20] : réel
N,M,P;entier
Début
Ecrire("Entrer le nombre de ligne de la matrice A")
lire(N)
Ecrire("Entrer le nombre de colonne de la matrice A")
lire(P)
SaisieMatrice (N,P,A)
Ecrire ("La matrice A est : ")
AfficheMatrice(N,P,A)
MaxMatrice(N,P,A)
Fin
10
