Examen Final : Algorithmique Enseignants : Pr. N. ZRIRA & Pr. H.

TOULNI
Session : Normale Durée de l’épreuve : 1h30
Nombre de pages : 5 Barème indicatif : 20/20
Documents autorisés : OUI NON Calculatrice autorisée : OUI NON

Exercice 1 : (8 points)
Soit A(n,n) une matrice triangulaire inférieure.
1. Ecrire un algorithme qui vérifie si la matrice A saisie par l’utilisateur est triangulaire inférieure.
Soit B(n,n) une matrice quelconque.
2. Écrire un algorithme qui calcule le produit des deux matrices P=AxB sans effectuer les multiplications par
zéro.

1-
Algorithme : Vérifie si une matrice est triangulaire inférieure
Tableaux A[100][100]en Réel
Variables i, j, n en Entier
Variable inf en Booléen
Début
Faire
Ecrire (" Donnez la dimension de la matrice carrée A :")
Lire (n)
Tant que (n < 1) OU (n > 100)
Pour i  0 à n-1 faire
Pour j  0 à n-1 faire
Ecrire ("Entrez l'élément A[", i, "][", j, "] : ")
Lire (A[i][j])
FinPour
FinPour
inf  VRAI
i1
Tant que (i < n ET inf ) faire
ji+1
Tant que (j < n ET inf) faire
Si A[i][j] < > 0 alors
inf  FAUX
FinSi
j  j+1
FinTantque
i  i+1
FinTantque
Si (inf ) alors
Ecrire ("La matrice A est triangulaire inférieure ")
Sinon
Ecrire ("La matrice A n’est pas triangulaire inférieure ")
FinSi
Fin

1
 2-
Tableaux A[100][100], B[100][100], P[100][100] en Réel
Variables i, j, k, n en Entier
Début
Faire
Ecrire (" Donnez la dimension des matrices carrée :")
Lire (n)
Tant que (n < 1) OU (n > 100)
Pour i  0 à n-1 faire
Pour j  0 à n-1 faire
Ecrire ("Entrez l'élément A[", i, "][", j, "] : ")
Lire (A[i][j])
FinPour
FinPour
Pour i  0 à n-1 faire
Pour j  0 à n-1 faire
Ecrire ("Entrez l'élément B[", i, "][", j, "] : ")
Lire (B[i][j])
FinPour
FinPour
Pour i  0 à n-1 faire
Pour j  0 à n-1 faire
P[i][j]  0
Pour k  0 à i faire
P[i][j]  P[i][j] +A[i][k]*B[k][j]
FinPour
FinPour
FinPour
Ecrire ("Le produit des matrices A et B est :")
Pour i  0 à n-1 faire
Pour j  0 à n-1 faire
Ecrire (P[i][j])
FinPour
FinPour
Fin

Exercice 2 : (8 points)
Soit T un tableau de n entiers :
1. Ecrire une fonction TRIE() qui permet d’indiquer à l’utilisateur si le tableau T est trié dans un ordre
décroissant.
2. Ecrire une fonction TRI_SELECTION() qui permet de trier les éléments du tableau T dans un ordre
décroissant en utilisant le principe du tri par sélection.

2
3. Ecrire un algorithme, de complexité optimale, qui teste si le tableau T est trié en utilisant la fonction
TRIE(). Si ce n’est pas le cas, il doit utiliser la fonction TRI_SELECTION()pour le trier. Ensuite,
il cherche si un élément x existe dans le tableau.

1-
Fonction TRIE (Tableau T en Entier, n en Entier) en Booléen
Début
Variables i en Entier
Pour i  0 à n-2 faire
Si (T[i] < T[i+1]) alors
Retourner FAUX
FinSi
FinPour
Retourner VRAI
Fin
2-
Fonction TRI_SELECTION (Tableau T en Entier, n en Entier)
Début
Variables i, j, tmp en Entier
Pour i  0 à n-2 faire
Pour j  i+1 à n-1 faire
Si (T[i] < T[j]) alors
tmp  T[j]
T[j]  T[i]
T[i]  tmp
FinSi
FinPour
FinPour
Fin
3-
Algorithme : Chercher si un élément existe dans un tableau trié
Tableaux T[100]en Entier
Variables i, n, x, g, d, m en Entier
Début
Faire
Ecrire (" Donnez la taille n :")
Lire (n)
Tant que (n < 1) OU (n > 100)
Pour i  0 à n-1 faire
Ecrire ("Entrez l'élément T[", i, "] : ")
Lire (T[i])
FinPour
Si NON(TRIE (T[], n ) ) alors

3
 TRI_SELECTION (T[], n)
FinSi

Ecrire (" Donnez l’élément à chercher :")

d  n-1
g0
Tant que (d < > g) faire
m  (d+g)/2
Si (T[m]<=x) alors
d m
Sinon
g m+1
FinSi
FinTantque
Si T[d]=x alors
Ecrire ("L'élément", x, "est présent dans le tableau")
Sinon
Ecrire ("L'élément", x, "n'est pas présent dans le tableau")
FinSi
Fin

Exercice 3 : (4 points)
Ecrire une fonction qui permet de calculer la suite Un définie par :
U1 = 1, U2 = 2 pour n < 3
Un= 3Un-1 + 2Un-2 pour n >= 3
1. de façon itérative.
2. de façon récursive.
Remarque : Le nombre n doit être passé en argument.
1-
Fonction CalcSuiteIte(n en Entier) en Entier
Début
Variables U1, U2, Un, i en Entier
U1  1
U2  2
Si (n =1) alors
Un  U1
Sinon
Si (n =2) alors
Un  U2
Sinon
Pour i  3 à n faire

4
 Un  3*U2+2*U1
U1  U2
U2  Un
FinPour
FinSi
FinSi
Retourner (Un)
Fin
2-
Fonction CalcSuiteRec (n en Entier) en Entier
Début
Si (n < 3) alors
Retourner (n)
Sinon
Retourner (3*CalcSuiteRec(n-1)+2* CalcSuiteRec(n-2))
FinSi
Fin