|
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
/* Methode de recherche la plus petite valeur */
/* contenue dans une matrice de int */
static int min(int [][] t) {
int min = t[0][0];
int i;
int j;
for ( i = 0 ; i < t.length ; i = i+1 ) {
for ( j = 0 ; j < t[0].length ; j = j+1 ) {
if ( t[i][j] < min ) {
min = t[i][j]; } } }
return min;
}
/* Type agrege de stockage d'une position */
static class Position {
int l = 0;
int c = 0; };
/* Methode de recherche de la position */
/* de la plus petite valeur */
/* contenue dans une matrice de int */
static Position positionMin(int [][] t) {
Position pMin = new Position();
int min = t[0][0];
int i;
int j;
for ( i = 0 ; i < t.length ; i = i+1 ) {
for ( j = 0 ; j < t[0].length ; j = j+1 ) {
if ( t[i][j] < min ) {
pMin.l = i;
pMin.c = j;
min = t[i][j]; } } }
return pMin;
}
/* Methode de calcul de la somme des valeurs */
/* contenues dans un tableau de int */
static int sommeLigne(int [] ligne) {
int somme;
int i;
somme = 0;
for ( i = 0 ; i < ligne.length ; i = i+1 ) {
somme = somme+ligne[i]; }
return somme;
}
/* Methode de calcul de l'indice de la ligne */
/* de somme maximum des lignes */
/* contenues dans un tableau de int */
static int ligneMax(int [][] t) {
int max;
int iMax;
int i;
int somme;
max = sommeLigne(t[0]);
iMax = 0;
for ( i = 1 ; i < t.length ; i = i+1 ) {
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 NxM dans une matrice NxM.
b) Développer un sous-algorithme permettant de copier la matrice transposée d'une matrice NxM dans une matrice
MxN. Tranposer 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 NxN. La transposition
se fait "en place", sans utilisation d'une matrice auxiliaire.
|
ManipulationsMatriceReel.java
/* Methode de copie d'une matrice de double */
/* dans une matrice de double supposee */
/* de taille identique */
static void copie(double [][] src,double [][] dst) {
int i;
int j;
for ( i = 0 ; i < src.length ; i = i+1 ) {
for ( j = 0 ; j < src[0].length ; j = j+1 ) {
dst[i][j] = src[i][j]; } }
}
/* Methode de transposition d'une matrice */
/* de double dans une matrice de double */
/* supposee de taille compatible */
static void transposition(double [][] src,double [][] dst) {
int i;
int j;
for ( i = 0 ; i < src.length ; i = i+1 ) {
for ( j = 0 ; j < src[0].length ; j = j+1 ) {
dst[j][i] = src[i][j]; } }
}
/* Methode de transposition d'une matrice */
/* carree de double */
static void transposition(double [][] m) {
int i;
int j;
double aux;
for ( i = 0 ; i < m.length-1 ; i = i+1 ) {
for ( j = i+1 ; j < m.length ; j = j+1 ) {
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 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 i;
int j;
int [][] md = new int[nl][nc];
for ( i = 0 ; i < nl ; i = i+1 ) {
for ( j = 0 ; j < nc ; j = j+1 ) {
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 i;
int j;
int l;
int c;
int nl = t.length;
int nc = t[0].length;
boolean change;
int distance = 0;
int [][] md = new int[nl][nc];
for ( i = 0 ; i < nl ; i = i+1 ) {
for ( j = 0 ; j < nc ; j = j+1 ) {
md[i][j] = -1; } }
md[py][px] = 0;
do {
change = false;
for ( l = 0 ; l < nl ; l = l+1 ) {
for ( c = 0 ; c < nc ; c = c+1 ) {
if ( voisinage(c,l,md,distance,t,t[py][px]) ) {
change = true;
md[l][c] = distance+1; } } }
distance = distance+1; }
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 i;
int j;
int l;
int c;
int nl = tp.length;
int nc = tp[0].length;
boolean [][] tpa = new boolean[nl][nc];
int [][] md = new int[nl][nc];
for ( i = 0 ; i < nl ; i = i+1 ) {
for ( j = 0 ; j < nc ; j = j+1 ) {
md[i][j] = -1; } }
md[py][px] = 0;
tpa[py][px] = true;
for ( int distance = 0 ; distance < dist ; distance++ ) {
for ( l = 0 ; l < nl ; l = l+1 ) {
for ( c = 0 ; c < nc ; c = c+1 ) {
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
Programmer un sous-algorithme permettant de calculer la matrice somme de deux matrices d'entiers de tailles
identiques.
|
SommeMatrices.java
/* Methode de calcul de la somme de 2 matrices */
/* de int de tailles compatibles */
/* Resultat stocke dans la 3eme matrice */
/* en entete */
static void somme(int [][] m1,int [][] m2,int [][] ms) {
int i;
int j;
for ( i = 0 ; i < m1.length ; i = i+1 ) {
for ( j = 0 ; j < m1[0].length ; j = j+1 ) {
ms[i][j] = m1[i][j]+m2[i][j]; } }
}
/* Methode de calcul de la somme de 2 matrices */
/* de int de tailles compatibles */
/* Resultat stocke dans la matrice allouee */
/* et retournee */
static int [][] somme(int [][] m1,int [][] m2) {
int [][] ms = new int[m1.length][m1[0].length];
somme(m1,m2,ms);
return ms;
}
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
/* Methode 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 i;
int j;
int x;
int y;
int l = mr.length;
int c = mr[0].length;
int xf;
int yf;
double v;
for ( i = 0 ; i < l ; i = i+1 ) {
for ( j = 0 ; j < c ; j = j+1 ) {
mr[i][j] = 0.0;
yf = i+mc.length;
xf = j+mc[0].length;
for ( y = i ; y < yf ; y = y+1 ) {
for ( x = j ; x < xf ; x = x+1 ) {
mr[i][j] = mr[i][j] + mc[y-i][x-j]*m[y][x]; } } } }
}
/* Methode 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
|
|
