Correction du TD n°10

Exercice 1

Ecrire un algorithme qui calcule la transposée d'une matrice carrée donnée.

001 { Transposition d'une matrice carree }
002 { de chaines de caracteres }
003
004 action calculTransposee(m)
005 Donnees / Resultat m : tableau [N][N] de chaine { tableau a transposer }
006 de caracteres
007 Locales i,j : entier { indices de boucle pour }
008 aux : chaine de caracteres { variable auxiliaire de permutation }
009 pour i de 0 à N-2 faire
010 pour j de i+1 à N-1 faire
011 aux := m[i][j]
012 m[i][j] := m[j][i]
013 m[j][i] := aux
014 fait
015 fait
016 fin action

CalculTransposee.lda

Exercice 2

Ecrire algorithme qui, étant données une matrice carrée A de taille N x N et un entier P, calcule la matrice puissance AP.

001 { Calcul la puissance nieme d'une matrice }
002 { carree de reels }
003
004 action puissanceMatrice(a,p,m)
005 Donnees a : tableau [N][N] de reel { tableau source }
006 p : entier { puissance }
007 Donnees / Resultat m : tableau [N][N] de reel { tableau resultat }
008 Locales i : entier { variable indice de boucle pour }
009 aux : tableau [N][N] de reel { tableau auxiliaire }
010 copieMatrice(a,aux)
011 pour i de 0 à N-2 faire
012 produitMatrices(aux,a,aux)
013 fait
014 copieMatrice(aux,m)
015 fin action

Avec utilisation de l'algorithme de copie de matrice du TD n°9 adapté aux tableaux de réels.

PuissanceMatrice.lda

Exercice 3

On se propose de déterminer si une matrice carrée d'entiers (de taille NxN) est magique, c'est à dire si les sommes des coefficients de chaque ligne, de chaque colonne et de chaque diagonale sont égales et si tous les nombres entiers entre 1 et N2 sont présents une et une seule fois dans la matrice.
Pour cela, écrire les actions/fonctions suivantes :

- Calcul de la somme des coefficients d'une ligne.

001 { Calcul de la somme des valeurs }
002 { d'une ligne d'une matrice d'entiers }
003
004 fonction sommeLigneMatrice(t,l) : entier
005 Donnees t : tableau [N][N] de entier { tableau traite }
006 l : entier { ligne de calcul }
007 Locales i : entier { indice de boucle pour }
008 cumul : entier { variable maximum resultat }
009 cumul := t[l][0]
010 pour i de 1 à N-1 faire
011 cumul := cumul + t[l][i]
012 fait
013 Resultat : cumul
014 fin fonction

SommeLigneMatrice.lda

- Calcul de la somme des coefficients d'une colonne.

001 { Calcul de la somme des valeurs }
002 { d'une colonne d'une matrice d'entiers }
003
004 fonction sommeColonneMatrice(t,c) : entier
005 Donnees t : tableau [N][N] de entier { tableau traite }
006 c : entier { colonne de calcul }
007 Locales i : entier { indice de boucle pour }
008 cumul : entier { variable maximum resultat }
009 cumul := t[0][c]
010 pour i de 1 à N-1 faire
011 cumul := cumul + t[i][c]
012 fait
013 Resultat : cumul
014 fin fonction

SommeColonneMatrice.lda

- Calcul de la somme des coefficients d'une diagonale.

001 { Calcul de la somme des valeurs }
002 { d'une diagonale d'une matrice d'entiers }
003
004 fonction sommeDiagonaleMatrice(t,d,sens) : entier
005 Donnees t : tableau [N][N] de entier { tableau traite }
006 d : entier { diagonale de calcul }
007 sens : booleen { sens de la diagonale }
008 { descendante ou montante }
009 Locales i : entier { indice de boucle pour }
010 cumul : entier { variable maximum resultat }
011 l : entier { numero le ligne }
012 cumul := t[d][0]
013 pour i de 1 à N-1 faire
014 si sens alors
015 l = (d+i) modulo N
016 sinon
017 l = (d+N-i) modulo N
018 fsi
019 cumul := cumul + t[l][i]
020 fait
021 Resultat : cumul
022 fin fonction

SommeDiagonaleMatrice.lda

- Test si tous les nombres entiers entre 1 et N2 sont présents une et une seule fois.

001 { Test de la presence de tous les entiers }
002 { entre 1 et NxN dans un tableau carre NxN }
003
004 fonction testEnsembleNombresMatrice(t) : booleen
005 Donnees t : tableau [N][N] de reel { tableau de recherche }
006 Locales i : entier { indice de boucle tant que et pour }
007 b : tableau [NxN] de booleen { tableau de test de presence }
008 v : entier { valeur extraite du tableau }
009 res : booleen { variable booleenne resultat }
010 res := vrai
011 pour i de 0 à NxN faire
012 b[i] := faux
013 fait
014 i := 0
015 tant que res et (i < N*N) faire
016 v := t[i/N][i modulo N]-1
017 si ( v < 0 ) ou ( v >= N*N ) alors
018 res := faux
019 sinon
020 si b[v] alors
021 res := faux
022 sinon
023 b[v] := vrai
024 fsi
025 fsi
026 i := i+1
027 fait
028 Resultat : res
029 fin fonction

TestEnsembleNombresMatrice.lda

Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr