Serie TD Tab 2 Dim

Correction série : Tableaux à 2 dimensions

[email protected] http://prepa-info.blogspot.com

1

Série d’exercices : Les tableaux à deux dimensions

Exercice n°1 :

EXEMPLE : n = 6

indice 0 1 2 3 4 5 6 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1

Remarques : 1. Les commentaires sont écrits en vert après deux slaches

Exemple : //ceci est un commentaire

2. On peut déclarer un tableau directement dans l’entête du sous programme.

Cas 1 : procédure afficher (A : tableau [1..NMAX, 1..NMAX] d’entiers)

Avec, NMAX : est une constante qui signifie le nombre maximale de

lignes et de colonnes et doit être déclarée dans le programme principal.

Cas 2 : procédure afficher (A : tableau [1..100, 1..100] d’entiers)

Dans ce cas, NMAX n’est pas déclarée dans le programme principal,

donc on écrit explicitement sa valeur dans la déclaration.

3. Exécuter manuellement l’algorithme pour le comprendre mieux.



2

Procédure trianglePascal (VAR M : tableau [0..NMAX, 0..NMAX] d’entiers, n : entier)

Var i, j : entier

Début

Si (n >= 0 et n <NMAX) alors

Pour i de 0 à n faire //lignes

M [i, 0] ← 1

Pour j de 1 à (i-1) faire

M [i, j] ← M [i-1, j-1] + M [i-1, j]

Fin pour

M [i, i] ← 1

Fin pour

Fin si

Fin

Exercice n°2 :

Fonction symMat (M : tableau [1..NMAX, 1.. NMAX] d’entiers ; L, C : entier) : booléen

Var

i, j : entier

Début

Pour i de 1 à (L-1) faire

Pour j de (i+1) à C faire

Si (M [i, j] ≠ M [j, i]) alors

Retourner (faux)

Fin si

Fin pour

Fin pour // si on termine le parcourt de toute la matrice sans retourner "f aux" on renvoie "vrai"

Retourner (vrai)

Fin

Remarque : Pour que la matrice soit triangulaire inférieure, il faut que toutes les cases au dessus de la diagonale sont nulles (=0) et au moins une des cases de la diagonale ou bien de celles se trouvant au dessous de la diagonale soit différente de zéro.



3

fonction trinagInf (M : tableau [1..NMAX, 1.. NMAX] d’entiers ; L, C : entier) : booléen

Var

i, j : entier

Début

Pour i de 1 à (L-1) faire

Pour j de (i+1) à C faire

// Il faut que toutes les cases du triangle supérieur (au dessus de la diagonale) égales à zéro, sinon on retourne "f aux"

Si (M [i, j] ≠ 0) alors

Retourner (faux)

Fin si

Fin pour

Fin pour

// Il faut tester aussi que au moins une des case de la diagonale est différente de zéro,

//si on trouve au moins une case ≠ 0, on retourne "vrai"

Pour i de 1 à L faire

Si (M [i, j] ≠ 0) alors

Retourner (vrai)

Fin si

Fin pour

// Si toutes les cases parcourues sont nulles, on applique la fonction symMat, pour vérifier que le triangle inférieur de la matrice n’est pas nul aussi

// si symMat (M, L, C) renvoie "vrai", donc toutes les cases = 0, alors on retourne non vrai

// et si symMat (M, L, C) renvoie "faux", donc il y a au moins une case ≠ 0, alors on retourne non

faux

Retourner (non symMat (M, L, C))

Fin



4

Exercice n°3 :

fonction magiqueMat (M : tableau [1..NMAX, 1.. NMAX] d’entiers ; n : entier) : booléen

Var

i, j, sd, sl, sc : entier

magique : booléen

Début

// Somme de la diagonale

sd ← 0

Pour i de 1 à n faire

sd ← sd + M [i, i]

Fin pour

magique ← vrai

i ← 1

Répéter

// Somme de la ligne n° i

sl ← 0

Pour j de 1 à n faire

sl ← sl + M [i, j] Fin pour

// Somme de la colonne n° i

sc ← 0


sc ← sc + M [j, i]

Fin pour

Si (sd = sc et sl = sd) alors

i ← i + 1

sinon

magique ← faux

Fin si

Jusqu’à (magique = faux ou i > n)

Retourner (magique)

Fin

Exercice n°4 :

Réaliser le transposé d’une matrice revient à permuter ses lignes et ses colonnes.

Afin d’éviter d’utiliser une autre matrice, la matrice d’origine doit être carrée.

Cas d’une matrice carrée : Permutation par rapport à la diagonale principale.

Cas d’une matrice quelconque : Exemple : L = 2, C=3 L = 3, C= 2 on doit créer une autre matrice résultante

1 1 1

2 2 2

3 3 3

1 1 1

2 2 2

1 2

1 2

1 2

1 2 3

1 2 3

1 2 3



5

// Cas d’une matrice carrée

Procédure transposeMat (VAR M : tableau [1..NMAX, 1.. NMAX] d’entiers ; n, m : entier)

Var i, j, x : entier

Début

Pour i de 1 à (n-1) faire

Pour j de (i+1) à m faire

x ← M [i, j] ;

M [i, j] ← M [j, i] ;

M [j, i] ← x

Fin pour

Fin pour

Fin

Exercice n°5 :

procédure circulanteMat (VAR M : tableau [1..NMAX, 1.. NMAX] d’entiers ; n : entier)

Var

i, j : entier

Début


M [1, j] ← j

Fin pour


M [i, 1] ←M [i-1, n]


M [i, j] ← M [i-1, j-1]

Fin pour

Fin pour

Fin



6

Exercice n°6 :

Pour i = 1, j = 1, n = 4, q = 2

TA = a*b + c*d

= 1*2 + 3*4

= 2 + 12 = 14

TB = e*f + g*h

= 1*2 + 3*4

= 2 + 12 = 14

Ci,j = [(a+f)*(b+e)] +[(c+h)*(d+g)]-TA-TB

= (1+2)*(2+1) + (3+4)*(4+3) -TA-TB

= 3* 3+7*7 - TA -TB

= 9+49-TA-TB

= 58-14-14

= 30

Vérification avec la méthode classique :

Ci,j = a*e + b*f + c*g + d*h

= 1*1 + 2*2 + 3*3 + 4*4

=1+4+9+16

=30



7

Procédure WINOGRAD (A, B : MAT ; m, n, p : entier ; VAR C : MAT) : entier

Var

i, j, k, TA, TB, SQ : entier

q : réel

Début

Si (n mod 2 = 0) alors

q ← n / 2

Pour i de 1 à m faire

Pour j de 1 à p faire

TA ← 0

TB ← 0

SQ ← 0

Pour k de 1 à q faire

TA ← TA + A [i, 2*k-1] * A [i, 2*k]

TB ← TB + B [2*k-1, j] * B [2*k, j]

SQ ← SQ + (A [i, 2*k-1] + B [2*k, j]) * (A [i, 2*k] + B [2*k-1, j])

Fin pour

C [i, j] ← SQ-TA-TB

Fin pour

Fin pour

Fin si

Fin

Exercice n°7 :

1)

Fonction saisie () : entier

Var n : entier

Début

Répétera

Ecrire ("n=")

Lire (n)

Jusqu’à (n>=2 et n <=10) // (2 ≤ n ≤ 10) ou n in [2..10] sont interdits

Retourner (n)

Fin



8

2)

Procédure saisie_Mat (VAR M : MAT1, n : entier)

Var i, j : entier

Début


Pour j de 1 à n faire lire (M [i, j])

Fin pour

Fin pour

Fin

3)

// Attention !

// Les composantes de la matrice H sont de type réel

// Donc on doit ajouter un autre type de matrice carrée de type réel

MATR = tableau [1.. NMAX, 1..NMAX] de réels

Procédure hilbert (VAR H : MATR, n : entier)

Var i, j : entier

Début


Pour j de 1 à n faire H [i, j] ← 1 / (i+j-1)

Fin pour

Fin pour

Fin

4)

Procédure concat (A : MAT1, H : MATR, VAR B : MAT2, n : entier)

Var i, j : entier

Début


Pour j de 1 à n faire B [i, j] ← A [i, j]

B [i, j+n] ← H [i, j]

Fin pour

Fin pour Fin



9

Exercice n° 8 :

Fonction saisir () : entier

Var n : entier

Début

Répéter

Ecrire ("n=")

Lire (n)

Jusqu’à (n ≥ 1 et n ≤ NMAX) // (1 ≤ n ≤ NMAX) ou n in [1..NMAX] sont interdits

Retourner (n)

Fin

Procédure remplir_Mat (VAR A : MAT, n : entier)

Var i, j : entier

Début


Pour j de 1 à n faire A [i, j] ← i / (j+1) // vous pouvez lui affecter une autre valeur de type réel

Fin pour

Fin pour

Fin

Procédure produit_Mat (A : MAT ; m, n : entier ; B : MAT ; p, q : entier ; VAR C : MAT)

Var i, j, k : entier

Début

Si (n=p) alors

Pour i de 1 à m faire

Pour j de 1 à q faire

C [i, j] ← 0

Pour k de 1 à n faire

C [i, j] ← C [i, j] + A [i, k] * B [k, j] Fin pour

Fin pour

Fin pour

Fin si

Fin



10

Exercice n° 9 :

// On déclare un nouveau type pour la matrice C de nombre de lignes maximale égale

// au nombre maximum de composantes de la matrice A

MATCR = // la matrice C est d’ordre (p,3) = Cp,3

Procédure compacte ( A : MAT ; n, m : entier ;

VAR C : tableau [1..NMAX*NMAX, 1..3] d’entiers ; VAR p : entier)

Var i, j, k, nb: entier

Début

C [1, 1] ← n

C [1, 2] ← m

nb 0

k 1


Pour j de 1 à m faire

Si A [i, j] ≠0 alors

nb ← nb+1

k ← k + 1 //préparer la ligne suivante

C [k, 1] ← i

C [k, 2] ← j

C [k, 3] ← A [i, j]

Fin si

Fin pour

Fin pour

C [1, 3] ←nb

p ← k // p est le nombre de lignes final de C

Fin

Documents

Serie TD Tab 2 Dim