Correction du TD n°17
Tri récursif.
001 action tri(t,indi,indf)
002 Données t : tableau [N] de entier { Tableau dont une portion est a trier }
003 indi : entier { Indice du premier entier }
004 { de la portion de tableau a trier }
005 indf : entier { Indice du dernier entier }
006 { de la portion de tableau a trier }
007 Locales aux : entier { Variable auxilaire pour permutation }
008 ind : entier { Indice de la valeur a mi distance }
009 { entre indi et indf }
010 si indf != indi alors
011 si indf == indi+1 alors
012 si t[indi] > t[indf] alors
013 aux := t[indi]
014 t[indi] := t[indf]
015 t[indf] := aux
016 fsi
017 sinon
018 ind := indi+(indf-indi)/2
019 tri(t,indi,ind)
020 tri(t,ind+1,indf)
021 fusion(t,indi,ind,indf)
022 fsi
023 fsi
024 fin action
001 action triRecursif(t)
002 Données t : tableau [N] de entier { Tableau a trier }
003 tri(t,0,N-1) { Lancement du tri recursif des indices 0 à N-1 }
004 fin action
Une classe vecteur de 4 valeurs réelles.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Avril 2005 */
public class Vecteur {
/* Tableau de 4 valeurs double pour le stockage */
/* des 4 reels d'un objet Vecteur */
double [] t;
/* Constructeur sans parametre avec initialisation */
/* complete a 0 d'un Vecteur */
public Vecteur() {
/* Allocation de memoire pour le tableau t */
/* (initialisation a 0 realisee automatiquement) */
t = new double[4];
}
/* Constructeur avec 4 parametres double */
/* pour l'initialisation des 4 reels d'un Vecteur */
public Vecteur(double x,double y,double z,double s) {
/* Allocation de memoire pour le tableau t */
t = new double[4];
/* Affectations separees des reels de t */
t[0] = x;
t[1] = y;
t[2] = z;
t[3] = s;
}
/* Methode de multiplication par une Matrice */
/* avec par modification du Vecteur */
/* m : Matrice utilisee pour multiplier le Vecteur */
public void multiplie(Matrice m) {
/* Appel a la methode multiplie de la classe Matrice */
m.multiplie(this);
}
/* Surcharge de la methode toString */
public String toString() {
return("["+t[0]+","+t[1]+","+t[2]+","+t[3]+"]");
}
}
Une classe matrice de 4x4 valeurs réelles.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Avril 2005 */
public class Matrice {
/* Tableau de 4x4 valeurs double pour le stockage */
/* des 4x4 reels d'un objet Matrice */
double [][] t;
/* Constructeur sans parametre avec initialisation */
/* d'une Matrice a la matrice identite */
public Matrice() {
/* Allocation de memoire pour le tableau t */
/* (initialisation a 0.0 realisee automatiquement) */
t = new double[4][4];
/* Affectation a 1.0 des reels de la diagonale */
t[0][0] = t[1][1] = t[2][2] = t[3][3] = 1.0;
}
/* Methode de reaffectation complete d'une Matrice */
/* vers une transformation geometrique de type */
/* translation de tx en x, ty en y et tz en z */
/* tx, ty, tz : Reels decrivant les valeurs */
/* de translation */
public void toTranslation(double tx,double ty,double tz) {
/* Affectation a 0.0 des trois premieres colonnes */
/* sauf sur la diagonale ou la valeur 1.0 est affectee */
for ( int i = 0 ; i < 4 ; i++ )
for ( int j = 0 ; j < 3 ; j++ )
t[i][j] = ( i == j ) ? 1.0 : 0.0;
/* Affectation de la troisieme colonne */
t[0][3] = tx;
t[1][3] = ty;
t[2][3] = tz;
t[3][3] = 1.0;
}
/* Methode de multiplication d'un vecteur par la matrice */
/* Le resultat de la multiplication est stocke */
/* dans le vecteur */
/* v : Vecteur a multiplier et a utiliser */
/* pour le stockage du resultat */
public void multiplie(Vecteur v) {
/* Utilisation d'un vecteur auxiliaire pour le produit */
/* matriciel (necessaire pour ne pas ecraser des valeurs */
/* de v qui devraient etre reutilisees par la suite */
Vecteur nv = new Vecteur();
/* Produit matriciel */
for ( int i = 0 ; i < 4 ; i++ )
for ( int k = 0 ; k < 4 ; k++ )
nv.t[i] += t[i][k]*v.t[k];
/* Reaffectation de v avec les valeurs de nv */
for ( int i = 0 ; i < 4 ; i++ )
v.t[i] = nv.t[i];
}
/* Methode de multiplication d'une matrice */
/* par la matrice */
/* Le resultat de la multiplication est stocke */
/* dans la matrice */
/* m : Matrice a multiplier et a utiliser */
/* pour le stockage du resultat */
public void multiplie(Matrice m) {
/* Utilisation d'une matrice auxiliaire pour le produit */
/* matriciel (necessaire pour ne pas ecraser des valeurs */
/* de v qui devraient etre reutilisees par la suite */
Matrice nm = new Matrice();
/* Produit matriciel */
for ( int i = 0 ; i < 4 ; i++ )
for ( int j = 0 ; j < 4 ; j++ ) {
nm.t[i][j] = 0.0;
for ( int k = 0 ; k < 4 ; k++ )
nm.t[i][j] += m.t[i][k]*t[k][j]; }
/* Reaffectation de la Matrice avec les valeurs de nm */
for ( int i = 0 ; i < 4 ; i++ )
for ( int j = 0 ; j < 4 ; j++ )
t[i][j] = nm.t[i][j];
}
/* Surcharge de la methode toString */
public String toString() {
String s = new String();
for ( int i = 0 ; i < 4 ; i++ )
s = s+("["+t[i][0]+","+t[i][1]+","+t[i][2]+","+t[i][3]+"]");
return(s);
}
}
Une application manipulant des Vecteur et des Matrice.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Avril 2005 */
public class ApplicationMatricesVecteurs {
public static void main(String [] args) {
/* Definition, instanciation et affichage d'un vecteur */
Vecteur v = new Vecteur(2.2,3.1,-1.2,1.0);
System.out.println("Vecteur v :");
System.out.println(v);
/* Definition et instanciation d'une matrice */
Matrice m = new Matrice();
/* Transformation de m en une translation */
m.toTranslation(2.2,-5.0,3.4);
System.out.println("Matrice m :");
System.out.println(m);
/* Multiplication de v par m */
m.multiplie(v);
/* Affichage de la nouvelle valeur de v */
System.out.println("Produit de m par v :");
System.out.println(v);
/* Recreation du vecteur v a sa valeur initiale */
v = new Vecteur(2.2,3.1,-1.2,1.0);
/* Multiplication de v par m */
v.multiplie(m);
/* Affichage de la nouvelle valeur de v */
System.out.println("Produit de m par v :");
System.out.println(v);
/* Definition et instanciation d'une premiere matrice */
Matrice m1 = new Matrice();
/* Transformation en une translation */
m1.toTranslation(4.2,-2.0,1.4);
/* Affichage */
System.out.println("Matrice m1 :");
System.out.println(m1);
/* Definition et instanciation d'une premiere matrice */
Matrice m2 = new Matrice();
/* Transformation en une translation */
m2.toTranslation(-1.7,4.2,3.4);
/* Affichage */
System.out.println("Matrice m2 :");
System.out.println(m2);
/* Composition de m1 par m2 dans m1 */
m1.multiplie(m2);
/* Reaffichage de m1 */
System.out.println("Produit de m1 par m2 :");
System.out.println(m1);
}
}
ApplicationMatricesVecteurs.java
Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr
