|
Exercice n°1
On considère une matrice d'entiers composée de 20 lignes de 8 colonnes. On souhaite effectuer diverses recherches au sein de ce tableau.
a) Développer un sous-algorithme permettant de calculer la plus petite valeur contenue dans un tel tableau.
b) Développer un sous-algorithme permettant de calculer la position de la plus petite valeur contenue dans un tel tableau.
c) Développer un sous-algorithme permettant de calculer l'indice de la ligne dont la somme des valeurs est la plus grande.
|
ManipulationsMatriceEntier.java
/* Fonction de recherche et retour */
/* de la plus petite valeur contenue */
/* dans une matrice d'int */
/* t : Le tableau d'int où faire la recherche */
static int min(int [][] t) {
int min = t[0][0];
for ( int i = 0 ; i < t.length ; i++ ) {
for ( int j = 0 ; j < t[0].length ; j++ ) {
if ( t[i][j] < min ) {
min = t[i][j]; } } }
return min;
}
/* Type agrege de stockage d'une position 2D }
/* a coordonnees entières */
static class Position {
int l = 0;
int c = 0; };
/* Fonction de recherche et retour */
/* des coordonnees de la plus petite valeur */
/* contenue dans une matrice d'int */
/* t : La matrice d'int où faire la recherche */
static Position positionMin(int [][] t) {
Position pMin = new Position();
for ( int i = 0 ; i < t.length ; i++ ) {
for ( int j = 0 ; j < t[0].length ; j++ ) {
if ( t[i][j] < t[pMin.l][pMin.c] ) {
pMin.l = i;
pMin.c = j; } } }
return pMin;
}
/* Fonction de calcul et retour */
/* de la somme des valeurs contenues */
/* dans un tableau d'int */
/* ligne : Le tableau d'int traité */
static int sommeLigne(int [] ligne) {
int somme = 0;
for ( int i = 0 ; i < ligne.length ; i++ ) {
somme = somme+ligne[i]; }
return somme;
}
/* Fonction de calcul et retour */
/* de l'indice de la ligne de somme maximum */
/* des lignes contenues */
/* dans une matrice d'int */
/* t : Le tableau d'int traité */
static int ligneMax(int [][] t) {
int somme;
int max = sommeLigne(t[0]);
int iMax = 0;
for ( int i = 1 ; i < t.length ; i++ ) {
somme = sommeLigne(t[i]);
if ( somme > max ) {
iMax = i;
max = somme; } }
return iMax;
}
Clavier.class - Ecran.class - Exemple
d'exécution
|
Exercice n°2
On manipule des matrices de réels.
a) Développer un sous-algorithme permettant de copier une matrice dans une matrice. Leurs tailles sont supposées identiques.
b) Développer un sous-algorithme permettant de copier la matrice transposée d'une matrice dans une matrice. Leurs tailles sont supposées
compatibles. Transposer une matrice est l'opération consistant à permuter ses valeurs autour de la diagonale.
c) Développer un sous-algorithme permettant de réaliser la transposition d'une matrice. La transposition se fait "en place", sans utilisation
d'une matrice auxiliaire.
|
ManipulationsMatriceReel.java
/* Fonction de copie d'une matrice de double */
/* dans une matrice de double supposee */
/* de tailles identiques */
/* src : La matrice de double source */
/* dst : La matrice de double cible */
static void copie(double [][] src,double [][] dst) {
for ( int i = 0 ; i < src.length ; i++ ) {
for ( int j = 0 ; j < src[0].length ; j++ ) {
dst[i][j] = src[i][j]; } }
}
/* Fonction de transposition d'une matrice */
/* de double dans une matrice de double */
/* supposee de tailles compatibles */
/* src : La matrice de double source */
/* dst : La matrice de double cible */
static void transposition(double [][] src,double [][] dst) {
for ( int i = 0 ; i < src.length ; i++ ) {
for ( int j = 0 ; j < src[0].length ; j++ ) {
dst[j][i] = src[i][j]; } }
}
/* Fonction de transposition d'une matrice */
/* carree de double */
/* m : La matrice de double à transposer */
static void transposition(double [][] m) {
double aux;
for ( int i = 0 ; i < m.length-1 ; i++ ) {
for ( int j = i+1 ; j < m.length ; j++ ) {
aux = m[i][j];
m[i][j] = m[j][i];
m[j][i] = aux; } }
}
Clavier.class - Ecran.class - Exemple
d'exécution
|
Exercice n°3
On manipule des tableaux et des matrices de caractères.
a) Développer un sous-algorithme permettant de générer un tableau à partir d'une matrice. Le tableau généré sera de taille nl*nc où nl et nc sont
les nombres de lignes et de colonnes de la matrice. Les valeurs de la matrice seront reportées les unes à la suite des autres dans le tableau
ligne de la matrice après ligne de la matrice (de gauche à droite et de bas en haut).
b) Développer un sous-algorithme permettant de générer une matrice à partir d'un tableau. Outre le tableau, le sous-algorithme aura comme
paramètre le nombre de lignes et le nombre de colonnes de la matrice à générer. Le report des valeurs dans la matrice est effectué
séquentiellement de gauche à droite et de bas en haut. S'il n'y a pas assez de place, le report sera arrêté une fois la matrice pleine. S'il y a
plus de place que nécessaire, les emplacements non remplis seront affectés avec le caractère espace.
|
ManipulationsMatriceCaractere.java
/* Fonction de calcul et retour du tableau */
/* de caracteres obtenu par linéarisation */
/* d'une matrice de carateres */
/* t : La matrice à linéariser */
static char [] transformationEnTableau(char [][] t) {
char [] res = new char[t.length*t[0].length];
int i = 0;
for ( int l = 0 ; l < t.length ; l++ ) {
for ( int c = 0 ; c < t[0].length ; c++ ) {
res[i] = t[l][c];
i++; } }
return res;
}
/* Fonction de calcul et retour de la matrice */
/* de caracteres obtenue par transformation */
/* en matrice d'un tableau de carateres */
/* t : Le tableau à transformer */
/* lignes : Le nombre de lignes */
/* de la matrice créée */
/* colonnes : Le nombre de colonnes */
/* de la matrice créée */
static char [][] transformationEnMatrice(char [] t,
int lignes,
int colonnes) {
char [][] res = new char[lignes][colonnes];
if ( lignes*colonnes <= t.length ) {
int i = 0;
for ( int l = 0 ; l < lignes ; l++ ) {
for ( int c = 0 ; c < colonnes ; c++ ) {
res[l][c] = t[i];
i++; } } }
else {
int l = 0;
int c = 0;
for ( int i = 0 ; i < lignes*colonnes ; i++ ) {
if ( i < t.length ) {
res[l][c] = t[i]; }
else {
res[l][c] = ' '; }
c++;
if ( c == colonnes ) {
c = 0;
l++; } } }
return res;
}
Clavier.class - Ecran.class - Exemple
d'exécution
|
Exercice supplémentaire
On considère une matrice de NxM "cellules". Chaque cellule possède 4 cellules voisines (à droite, à gauche, en haut et en bas). Un déplacement
élémentaire entre cellules ne peut être réalisé qu'entre deux cellules voisines. La "distance" existant entre deux cellules est le
nombre minimum de déplacements élémentaires permettant de passer de la première cellule à la seconde.
a) Développer un sous-algorithme permettant de calculer la matrice des distances existant entre chaque cellule d'une matrice NxM et une cellule
de position arbitraire.
Pour une matrice de 14 lignes de 20 colonnes et la position départ (8,5)
On considère que la matrice de taille NxM est une matrice de booléens. Cette matrice représente un plateau de jeu définissant 2 territoires (vrai
pour le joueur n°1, faux pour le joueur n°2).
Exemple de plateau de jeu
b) Développer un sous-algorithme permettant de calculer la matrice des distances existant entre chaque cellule d'une matrice NxM et une cellule
de position arbitraire. Dans cette version, le passage par une cellule du territoire du joueur opposé au joueur auquel appartient la cellule de départ
est interdit. Une distance égale à -1 signifie une cellule non atteignable.
Distances à partir de la position initiale (8,5)
Distances à partir de la position initiale (1,8)
|
ParcoursMatrice.java
/* Calcul de la matrice des distances */
/* "a vol d'oiseau" */
static int [][] matriceDesDistances(int px,int py,int nl,int nc) {
int [][] md = new int[nl][nc];
for ( int i = 0 ; i < nl ; i++ ) {
for ( int j = 0 ; j < nc ; j++ ) {
md[i][j] = Math.abs(i-py)+Math.abs(j-px); } }
return md;
}
/* Calcul de la matrice des distances */
/* "avec obstacles sur le passage" */
static boolean voisin(int x,int y,int [][] md,int distance) {
boolean res = false;
if ( ( x >= 0 ) && ( x < md[0].length ) &&
( y >= 0 ) && ( y < md.length ) ) {
if ( md[y][x] == distance) {
res = true; } }
return res;
}
static boolean voisinage(int c,int l,int [][] md,int distance,
boolean [][] t,boolean v) {
boolean res = false;
if ( ( md[l][c] == -1 ) && ( t[l][c] == v ) ) {
if ( voisin(c+1,l,md,distance) ) {
res = true; }
else {
if ( voisin(c-1,l,md,distance) ) {
res = true; }
else {
if ( voisin(c,l+1,md,distance) ) {
res = true; }
else {
if ( voisin(c,l-1,md,distance) ) {
res = true; } } } } }
return res;
}
static int [][] distances(int px,int py,boolean [][] t) {
int nl = t.length;
int nc = t[0].length;
boolean change;
int distance = 0;
int [][] md = new int[nl][nc];
for ( int i = 0 ; i < nl ; i++ ) {
for ( int j = 0 ; j < nc ; j++ ) {
md[i][j] = -1; } }
md[py][px] = 0;
do {
change = false;
for ( int l = 0 ; l < nl ; l++ ) {
for ( int c = 0 ; c < nc ; c++ ) {
if ( voisinage(c,l,md,distance,t,t[py][px]) ) {
change = true;
md[l][c] = distance+1; } } }
distance++; }
while ( change );
return md;
}
static void ajusteVoisin(int [][] tp,boolean [][] tpa,int [][] md,int c,int l,int dst,int distance) {
if ( ( c >= 0 ) && ( c < md[0].length ) &&
( l >= 0 ) && ( l < md.length ) ) {
int dt = dst+tp[l][c];
if ( ( md[l][c] == -1 ) && ( dt <= distance ) ) {
tpa[l][c] = true;
md[l][c] = dt; } }
}
static void ajusteVoisinage(int [][] tp,boolean [][] tpa,int [][] md,int c,int l,int distance) {
ajusteVoisin(tp,tpa,md,c+1,l,md[l][c],distance);
ajusteVoisin(tp,tpa,md,c-1,l,md[l][c],distance);
ajusteVoisin(tp,tpa,md,c,l-1,md[l][c],distance);
ajusteVoisin(tp,tpa,md,c,l+1,md[l][c],distance);
}
static boolean [][] positionsAtteignables(int [][] tp,int px,int py,int dist) {
int nl = tp.length;
int nc = tp[0].length;
boolean [][] tpa = new boolean[nl][nc];
int [][] md = new int[nl][nc];
for ( int i = 0 ; i < nl ; i++ ) {
for ( int j = 0 ; j < nc ; j++ ) {
md[i][j] = -1; } }
md[py][px] = 0;
tpa[py][px] = true;
for ( int distance = 0 ; distance < dist ; distance++ ) {
for ( int l = 0 ; l < nl ; l++ ) {
for ( int c = 0 ; c < nc ; c++ ) {
if ( md[l][c] == distance )
ajusteVoisinage(tp,tpa,md,c,l,dist); } } }
affichageMatrice(md);
Ecran.sautDeLigne();
return tpa;
}
Clavier.class - Ecran.class - Exemple
d'exécution
|
Exercice n°4
On dispose d'une matrice carrée d'entiers. Sa taille est quelconque. Les valeurs qu'elle contient sont quelconques. On souhaite réaliser sur
cette matrice l'opération consistant à déplacer ses valeurs de 90° en sens horaire.
Implanter un sous-algorithme permettant de réaliser cette opération par modification réalisée "en place" (sans utilisation d'une matrice
auxilliaire).
|
RotationMatrice.java
/* Fonction de rotation de 90° en sens horaire */
/* autour du centre de 4 valeurs contenues */
/* dans une matrice carree de int */
static void rotation(int [][] m,int l,int c) {
int n = m.length;
int aux = m[n-1-c][l];
m[n-1-c][l] = m[n-1-l][n-1-c];
m[n-1-l][n-1-c] = m[c][n-1-l];
m[c][n-1-l] = m[l][c];
m[l][c] = aux;
}
/* Fonction de rotation de 90° en sens horaire */
/* autour du centre des valeurs contenues */
/* dans une matrice carree de int */
static void rotation(int [][] m) {
int n = m.length;
for ( int i = 0 ; i < n/2 ; i++ ) {
for ( int j = 0 ; j < (n+1)/2 ; j++ ) {
rotation(m,i,j); } }
}
Clavier.class - Ecran.class - Exemple
d'exécution
|
Exercice n°5
Programmer un sous-algorithme permettant de calculer le produit de convolution d'une matrice de réels M de taille supérieure ou égale à 3x3 par
la matrice MC de taille 3x3 composée uniquement de 1.0/12.0 sauf un 4.0/12.0 au centre.
|
ProduitDeConvolution.java
/* Fonction de calcul du produit de convolution */
/* d'une matrice de double par une matrice */
/* de convolution */
/* Stockage du resultat dans la 3eme matrice */
/* passee en entete supposee de taille */
/* compatible avec les deux premieres */
static void produitDeConvolution(double [][] m,
double [][] mc,
double [][] mr) {
int l = mr.length;
int c = mr[0].length;
int xf;
int yf;
double v;
for ( int i = 0 ; i < l ; i++ ) {
for ( int j = 0 ; j < c ; j++ ) {
mr[i][j] = 0.0;
yf = i+mc.length;
xf = j+mc[0].length;
for ( int y = i ; y < yf ; y++ ) {
for ( int x = j ; x < xf ; x++ ) {
mr[i][j] = mr[i][j] + mc[y-i][x-j]*m[y][x]; } } } }
}
/* Fonction de calcul du produit de convolution */
/* d'une matrice de double par une matrice */
/* de convolution */
/* Stockage du resultat dans une matrice */
/* allouee et retournee en resultat de fonction */
static double [][] produitDeConvolution(double [][] m,
double [][] mc) {
int l = m.length-mc.length+1;
int c = m[0].length-mc[0].length+1;
double [][] mr = new double[l][c];
produitDeConvolution(m,mc,mr);
return mr;
}
Clavier.class - Ecran.class - Exemple
d'exécution
|
|
