Exercices corrigés - matrices - Python et Langage C - TD6
Exercice 1
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 ;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).
Solution :
#include <stdio.h>
void deplacer(int T[], int k, int n)
{
int i, d, aux;
i = 0;
d = n - 1;
while (i < d)
{
if (T[i] < k)
i += 1;
else if (T[d] < k)
{
// echange
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]);
}
}
int main(void)
{
int T[] = {3, 5, 8, 13, 19, 2, 6};
int k = 12;
deplacer(T, k, 7);
afficher(T, 7);
return 0;
}
def deplacer(T, k):
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
deplacer(T, k)
print(T)
Lorsque le code ci-dessus est compilé et exécuté, il produit le résultat suivant
Exercice 2
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
Solution :
#include <stdio.h>
#define TAILLE 3
void Trier(int A[][TAILLE], int n)
{
int nl, nc, aux, m;
nl = n; // nombre de lignes
nc = TAILLE; // nombre de colonnes
for (int k = 0; k < nc; k++)
{
// tri par selection
for (int i = 0; i < nl - 1; i++)
{
m = i;
for (int j = i + 1; j < nl; j++)
{
if (A[j][k] > A[m][k])
m = j;
}
aux = A[i][k];
A[i][k] = A[m][k];
A[m][k] = aux;
}
// fin tri par selection
}
}
void afficher(int T[][TAILLE], int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < TAILLE; j++)
printf("%d - ", T[i][j]);
printf("\n");
}
}
int main(void)
{
int A[TAILLE][TAILLE] = {{3, 2, 1}, {6, 5, 4}, {9, 8, 7}};
Trier(A, 3);
afficher(A, 3);
return 0;
}
def Trier(A):
nl = len(A) # nombre de lignes
nc = len(A[0]) # nombre de colonnes
for k in range(nc):
# tri par selection
for i in range(nl-1):
m = i
for j in range(i+1, nl):
if A[j][k] > A[m][k]:
m = j
A[i][k], A[m][k] = A[m][k], A[i][k]
# fin tri par selection
T = [[3, 2, 1], [6, 5, 4], [9, 8, 7]]
Trier(T)
print(T)
Lorsque le code ci-dessus est compilé et exécuté, il produit le résultat suivant
Exercice 3
Soit une matrice A de n ligne et m colonnes(n<100, m<50). Et soit le tableau T définie par rapport à la matrice A comme suit : L’ième élémént 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.
Solution :
#include <stdio.h>
#define TAILLE 3
void afficher(int T[], int n)
{
for (int i = 0; i < n; i++)
{
printf("%d - ", T[i]);
}
}
// chercher val dans T
int find(int T[], int n, int val)
{
for (int i = 0; i < n; i++)
{
if (T[i] == val)
return 1;
}
return 0;
}
int *build(int A[][TAILLE], int n)
{
int nl, nc, aux, m, nb;
int T[n - 1];
nl = n; // nombre de lignes
nc = TAILLE; // nombre de colonnes
for (int i = 0; i < nl - 1; i++)
{
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);
}
afficher(T, n - 1);
return T;
}
int main(void)
{
int A[TAILLE][TAILLE] = {{3, 5, 1}, {9, 5, 7}, {9, 8, 7}};
int *t;
t = build(A, 3);
return 0;
}
def build(A):
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(build(A))
Lorsque le code ci-dessus est compilé et exécuté, il produit le résultat suivant
Exercice 4
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.
Voici un exemple de matrice stochastique P (dans cet exemple, la somme des éléments de chaque ligne est égale à 1 ; on remarque que la somme des éléments de chaque colonne est quelconque):
Exemple
Si G est une matrice stochastique, alors on appelle vecteur stable pour G un vecteur h tel que :
Et
- Ecrire une fonction eststochastique(P) qui permet de vérifier est ce que la matrice P est stochastique ou non
- Ecrire une fonction estbistochastique(P) qui permet de vérifier est ce que la matrice P est bistochastique ou non
- Ecrire une fonction vecteurstable(G, h) qui permet de vérifier est ce que h est un vecteur stable de G ou non
Solution :
#include <stdio.h>
#define TAILLE 3
int eststochastique(double P[][TAILLE], int n)
{
int nl, nc, etat;
double s;
nl = n; // nombre de lignes
nc = TAILLE; // nombre de colonnes
etat = 1; // on suppose que la matrice est stochastique
for (int i = 0; i < nl; i++)
{
s = 0;
for (int j = 0; j < nc; j++)
s += P[i][j];
if (s > 1)
{
etat = 0;
break;
}
}
return etat;
}
int estbistochastique(double P[][TAILLE], int n)
{
int nl, nc, etat;
double s;
nl = n; // nombre de lignes
nc = TAILLE; // nombre de colonnes
etat = 1; // on suppose que la matrice est bistochastique
if (eststochastique(P, n) == 1)
{
for (int j = 0; j < nc; j++)
{
s = 0;
for (int i = 0; i < nl; i++)
s += P[i][j];
if (s > 1)
{
etat = 0;
break;
}
}
}
return etat;
}
int vecteurstable(double P[][TAILLE], int v[], int n)
{
int nl, nc, etat;
double s;
nl = n; // nombre de lignes
nc = TAILLE; // nombre de colonnes
etat = 1; // on suppose que v est une vecteur stable de P
if (eststochastique(P, n) == 1)
{
for (int j = 0; j < nc; j++)
{
s = 0;
for (int i = 0; i < nl; i++)
s += v[i] * P[i][j];
if (s != v[j])
{
etat = 0;
break;
}
}
}
else
{
etat = 0;
}
return etat;
}
int main(void)
{
double A[3][TAILLE] = {{0.5, 0, 0.5}, {0, 0.5, 0.5}, {0.5, 0.5, 0}};
printf("%d", estbistochastique(A, 3));
return 0;
}
def eststochastique(P):
nl = len(P) # nombre de lignes
nc = len(P[0]) # nombre de colonnes
etat = True # on suppose que la matrice est stochastique
for i in range(nl):
s = 0
for j in range(nc):
s += P[i][j]
if s > 1:
etat = False
break
return etat
def estbistochastique(P):
nl = len(P) # nombre de lignes
nc = len(P[0]) # nombre de colonnes
etat = True # on suppose que la matrice est bistochastique
if(eststochastique(P)):
for j in range(nc):
s = 0
for i in range(nl):
s += P[i][j]
if s > 1:
etat = False
break
return etat
def vecteurstable(G, h):
nl = len(G) # nombre de lignes
nc = len(G[0]) # nombre de colonnes
etat = True
if(eststochastique(G)):
for j in range(nc):
s = 0
for i in range(nl):
s += h[i]*G[i][j]
if s != h[j]:
etat = False
break
else:
etat = False
return etat
