Exercices avancés sur les tableaux et matrices
Cette section présente des exercices plus avancés sur la manipulation des tableaux et matrices, avec des applications en algorithmique et en mathématiques.
Exercice 1
Partitionnement autour d'une valeur K
On donne une valeur K et un tableau T de N valeurs entières (N < 50) tel que la valeur K ne figure pas dans le tableau T (T[i] != K pour i=1..N).
Ecrire une fonction deplacer(T, K) qui permet de déplacer les éléments du tableau T de manière à regrouper en tête de celui-ci toutes les valeurs inférieures à K et en queue les valeurs supérieures à K (sans utiliser un autre tableau).
Solutions - Exercice 1
Idée — Algorithme de partitionnement
On utilise deux indices : i (début) et d (fin). On avance i tant que T[i] < K. Si T[i] > K, on regarde T[d] :
- Si T[d] < K, on échange T[i] et T[d]
- Sinon, on décrémente d
#include <stdio.h>
void deplacer(int T[], int k, int n)
{
int i = 0, d = n - 1, aux;
while (i < d)
{
if (T[i] < k)
i += 1;
else if (T[d] < k)
{
// échange
aux = T[i];
T[i] = T[d];
T[d] = aux;
}
else
d -= 1;
}
}
void afficher(int T[], int n)
{
for (int i = 0; i < n; i++)
{
printf("%d - ", T[i]);
}
printf("\n");
}
int main(void)
{
int T[] = {3, 5, 8, 13, 19, 2, 6};
int k = 12;
printf("Tableau original : ");
afficher(T, 7);
deplacer(T, k, 7);
printf("Tableau après déplacement : ");
afficher(T, 7);
return 0;
}def deplacer(T, k):
"""
Réorganise le tableau : valeurs < k en tête, valeurs > k en queue
"""
i = 0
d = len(T) - 1
while i < d:
if T[i] < k:
i += 1
else:
if T[d] < k:
T[i], T[d] = T[d], T[i]
else:
d -= 1
T = [3, 5, 8, 13, 19, 2, 6]
k = 12
print(f"Tableau original : {T}")
deplacer(T, k)
print(f"Tableau après déplacement : {T}")Sortie
Tableau original : [3, 5, 8, 13, 19, 2, 6] Tableau après déplacement : [3, 5, 8, 6, 2, 19, 13]
Explication : Les valeurs inférieures à 12 (3,5,8,6,2) sont en début de tableau, et les valeurs supérieures (19,13) en fin.
Exercice 2
Tri décroissant des colonnes d'une matrice
Soit une matrice A(n, m) de valeurs entières (n < 50, m < 100).
Ecrire une fonction trier(A) qui permet de faire un tri décroissant sur toutes les colonnes de la matrice A.
Solutions - Exercice 2
Idée
Pour chaque colonne, appliquer un tri par sélection (ou un autre algorithme de tri) pour trier les éléments de la colonne en ordre décroissant.
#include <stdio.h>
#define TAILLE 3
void Trier(int A[][TAILLE], int n)
{
int nl = n; // nombre de lignes
int nc = TAILLE; // nombre de colonnes
for (int k = 0; k < nc; k++)
{
// tri par sélection sur la colonne k
for (int i = 0; i < nl - 1; i++)
{
int m = i;
for (int j = i + 1; j < nl; j++)
{
if (A[j][k] > A[m][k])
m = j;
}
if (m != i)
{
int aux = A[i][k];
A[i][k] = A[m][k];
A[m][k] = aux;
}
}
}
}
void afficher(int A[][TAILLE], int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < TAILLE; j++)
printf("%d ", A[i][j]);
printf("\n");
}
}
int main(void)
{
int A[TAILLE][TAILLE] = {{3, 2, 1}, {6, 5, 4}, {9, 8, 7}};
printf("Matrice originale :\n");
afficher(A, 3);
Trier(A, 3);
printf("Matrice après tri des colonnes :\n");
afficher(A, 3);
return 0;
}def Trier(A):
"""
Trie chaque colonne de la matrice en ordre décroissant
"""
nl = len(A) # nombre de lignes
nc = len(A[0]) # nombre de colonnes
for k in range(nc):
# tri par sélection sur la colonne k
for i in range(nl - 1):
m = i
for j in range(i + 1, nl):
if A[j][k] > A[m][k]:
m = j
if m != i:
A[i][k], A[m][k] = A[m][k], A[i][k]
A = [[3, 2, 1], [6, 5, 4], [9, 8, 7]]
print("Matrice originale:")
for ligne in A:
print(ligne)
Trier(A)
print("Matrice après tri des colonnes:")
for ligne in A:
print(ligne)Sortie
Matrice originale: [3, 2, 1] [6, 5, 4] [9, 8, 7] Matrice après tri des colonnes: [9, 8, 7] [6, 5, 4] [3, 2, 1]
Exercice 3
Construction d'un tableau de différences entre lignes
Soit une matrice A de n lignes et m colonnes (n < 100, m < 50). Et soit le tableau T défini par rapport à la matrice A comme suit : L'ième élément de T représente le nombre d'éléments de la ligne i de A qui n'existe pas dans la ligne i+1 (la ligne suivante si elle existe).
Ecrire une fonction build(A) qui construit et affiche le tableau T.
Solutions - Exercice 3
#include <stdio.h>
#define TAILLE 3
int find(int T[], int n, int val)
{
for (int i = 0; i < n; i++)
{
if (T[i] == val)
return 1;
}
return 0;
}
void build(int A[][TAILLE], int n)
{
int nl = n; // nombre de lignes
int nc = TAILLE; // nombre de colonnes
int T[nl - 1];
for (int i = 0; i < nl - 1; i++)
{
int nb = 0;
for (int j = 0; j < nc; j++)
{
if (find(A[i + 1], nc, A[i][j]) == 0)
nb += 1;
}
T[i] = nb;
printf("T[%d] = %d\n", i, nb);
}
}
int main(void)
{
int A[TAILLE][TAILLE] = {{3, 5, 1}, {9, 5, 7}, {9, 8, 7}};
printf("Matrice :\n");
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
printf("%d ", A[i][j]);
printf("\n");
}
printf("Tableau des différences :\n");
build(A, 3);
return 0;
}def build(A):
"""
Construit un tableau T où T[i] = nombre d'éléments de la ligne i
qui n'apparaissent pas dans la ligne i+1
"""
nl = len(A) # nombre de lignes
nc = len(A[0]) # nombre de colonnes
T = [0] * (nl - 1)
for i in range(nl - 1):
nb = 0
for j in range(nc):
if A[i][j] not in A[i + 1]:
nb += 1
T[i] = nb
return T
A = [[3, 5, 1], [9, 5, 7], [9, 8, 7]]
print("Matrice A:")
for ligne in A:
print(ligne)
T = build(A)
print(f"Tableau des différences: {T}")Sortie
Matrice A: [3, 5, 1] [9, 5, 7] [9, 8, 7] Tableau des différences: [2, 1]
Explication :
- Ligne 0 (3,5,1) vs Ligne 1 (9,5,7) → 3 et 1 ne sont pas dans la ligne 1 → 2 éléments différents
- Ligne 1 (9,5,7) vs Ligne 2 (9,8,7) → 5 n'est pas dans la ligne 2 → 1 élément différent
Exercice 4
Matrices stochastiques et vecteurs stables
En mathématiques, une matrice stochastique (aussi appelée matrice de Markov) est une matrice carrée dont chaque élément est un réel compris entre 0 et 1 et dont la somme des éléments de chaque ligne vaut 1. Cela correspond, en probabilité, à la matrice de transition d'une chaîne de Markov finie.
Une matrice est dite bistochastique (ou doublement stochastique) si la somme des éléments de chaque ligne et de chaque colonne vaut 1.
Si G est une matrice stochastique, alors on appelle vecteur stable pour G un vecteur h tel que :
Écrire les fonctions suivantes :
- eststochastique(P) : vérifie si la matrice P est stochastique ou non
- estbistochastique(P) : vérifie si la matrice P est bistochastique ou non
- vecteurstable(G, h) : vérifie si h est un vecteur stable de G ou non
Solutions - Exercice 4
#include <stdio.h>
#define TAILLE 3
int eststochastique(double P[][TAILLE], int n)
{
int nl = n;
int nc = TAILLE;
for (int i = 0; i < nl; i++)
{
double s = 0;
for (int j = 0; j < nc; j++)
{
if (P[i][j] < 0 || P[i][j] > 1)
return 0;
s += P[i][j];
}
if (s != 1.0)
return 0;
}
return 1;
}
int estbistochastique(double P[][TAILLE], int n)
{
int nl = n;
int nc = TAILLE;
if (!eststochastique(P, n))
return 0;
for (int j = 0; j < nc; j++)
{
double s = 0;
for (int i = 0; i < nl; i++)
s += P[i][j];
if (s != 1.0)
return 0;
}
return 1;
}
int vecteurstable(double G[][TAILLE], double h[], int n)
{
int nl = n;
int nc = TAILLE;
if (!eststochastique(G, n))
return 0;
// Vérifier la condition h_i ≥ 0
double somme_h = 0;
for (int i = 0; i < nl; i++)
{
if (h[i] < 0)
return 0;
somme_h += h[i];
}
// Vérifier la condition h * G = h
for (int j = 0; j < nc; j++)
{
double s = 0;
for (int i = 0; i < nl; i++)
s += h[i] * G[i][j];
// Tolérance pour les erreurs d'arrondi
if (s < h[j] - 0.000001 || s > h[j] + 0.000001)
return 0;
}
return 1;
}
int main(void)
{
double A[TAILLE][TAILLE] = {{0.5, 0, 0.5}, {0, 0.5, 0.5}, {0.5, 0.5, 0}};
double h[TAILLE] = {0.2, 0.3, 0.5};
printf("Matrice stochastique ? %d\n", eststochastique(A, 3));
printf("Matrice bistochastique ? %d\n", estbistochastique(A, 3));
printf("Vecteur stable ? %d\n", vecteurstable(A, h, 3));
return 0;
}def eststochastique(P):
"""
Vérifie si la matrice P est stochastique
(éléments entre 0 et 1, somme de chaque ligne = 1)
"""
nl = len(P)
nc = len(P[0])
for i in range(nl):
s = 0
for j in range(nc):
if P[i][j] < 0 or P[i][j] > 1:
return False
s += P[i][j]
if abs(s - 1.0) > 1e-10: # Tolérance pour les erreurs d'arrondi
return False
return True
def estbistochastique(P):
"""
Vérifie si la matrice P est bistochastique
(stochastique + somme de chaque colonne = 1)
"""
nl = len(P)
nc = len(P[0])
if not eststochastique(P):
return False
for j in range(nc):
s = 0
for i in range(nl):
s += P[i][j]
if abs(s - 1.0) > 1e-10:
return False
return True
def vecteurstable(G, h):
"""
Vérifie si h est un vecteur stable de G
Conditions: h_i ≥ 0, somme(h) = 1, h * G = h
"""
nl = len(G)
nc = len(G[0])
if not eststochastique(G):
return False
# Vérifier que h_i ≥ 0
somme_h = 0
for val in h:
if val < 0:
return False
somme_h += val
# Vérifier que la somme des h est 1
if abs(somme_h - 1.0) > 1e-10:
return False
# Vérifier h * G = h
for j in range(nc):
s = 0
for i in range(nl):
s += h[i] * G[i][j]
if abs(s - h[j]) > 1e-10:
return False
return True
# Tests
A = [[0.5, 0, 0.5],
[0, 0.5, 0.5],
[0.5, 0.5, 0]]
h = [0.2, 0.3, 0.5]
print(f"Matrice stochastique ? {eststochastique(A)}")
print(f"Matrice bistochastique ? {estbistochastique(A)}")
print(f"Vecteur stable ? {vecteurstable(A, h)}")Sortie
Matrice stochastique ? True Matrice bistochastique ? True Vecteur stable ? False
Explication : La matrice A est bistochastique car chaque ligne et chaque colonne somme à 1. Le vecteur h = [0.2, 0.3, 0.5] n'est pas stable car h * G ≠ h.
Points clés à retenir
- Le partitionnement d'un tableau peut se faire en O(n) avec deux indices.
- Le tri par colonnes d'une matrice s'effectue en appliquant un tri classique à chaque colonne.
- La recherche d'éléments communs entre lignes nécessite une fonction de recherche.
- Une matrice stochastique a des lignes qui somment à 1, une matrice bistochastique a aussi des colonnes qui somment à 1.
- Un vecteur stable d'une matrice stochastique vérifie h·G = h et somme(h)=1.
Sortie
// La sortie apparaîtra ici…
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.