Langage Python

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

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

[3, 5, 8, 6, 2, 19, 13]

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

[[9, 8, 7], [6, 5, 4], [3, 2, 1]]

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

[2, 1]

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




  1. Ecrire une fonction eststochastique(P) qui permet de vérifier est ce que la matrice P est stochastique ou non
  2. Ecrire une fonction estbistochastique(P) qui permet de vérifier est ce que la matrice P est bistochastique ou non
  3. 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
                                            
                                        

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :