Corrigé du Contrôle d'Informatique INF 311
Promotion 2002
Sujet proposé par François Morain
11 juillet 2003
Les exercices qui suivent sont indépendants et peuvent être
traités dans n'importe quel ordre. On attachera une
grande importance à la clarté, à la précision et à la
concision de la rédaction.
Exercice 1.
Justifiez en quelques mots ce qu'affiche le programme suivant.
class Exo1{
static void f(int[] t, int n){
if(n >= 0){
t[n] = t[n] * t[n];
f(t, n-1);
}
}
public static void main(String[] args){
int[] t = {1, 2, 3, 4};
int n;
n = 2;
f(t, n);
System.out.println(n);
for(int i = 0; i < t.length; i++)
System.out.println(t[i]);
}
}
Corrigé.
Le programme affiche:
2
1
4
9
4
En effet, n n'est pas changé par l'appel à f, puisque
les variables de type int sont passées par valeur. En revanche,
il y a passage par variable de t, ce qui veut dire que le
tableau t sera changé par l'appel à f. Ici, la case t[n] sera remplie avec la valeur n*n. La fonction f est
une boucle for déguisée sous une forme récursive.
Exercice 2.
Le Crédit Tigré a entrepris la définition de sa nouvelle carte de
paiement, appelée ici carte mauve. Le but de l'exercice est de
définir les éléments Java nécessaires à l'écriture du programme de
gestion de cette carte.
Question 2.
On demande d'écrire la classe Client qui va
contenir les renseignements sur les clients de la banque. Un client a
un nom (une chaîne de caractères), et un numéro de compte (un
entier). Écrire la classe correspondante, ainsi qu'une fonction
static Client creer(String n, int num){...}
qui construit un objet de la classe Client et le remplit avec
les valeurs n et num.
Corrigé.
class Client{
String nom;
int numero;
static Client creer(String n, int num){
Client cl = new Client();
cl.nom = n;
cl.numero = num;
return cl;
}
}
Question 4.
Une carte mauve est définie par un client (de type
Client), possède un numéro d'ordre (un int), ainsi
qu'un numéro de code secret (un int), qui n'est délivré qu'au
client. On veut également que le code secret ne soit pas
visible en dehors de l'objet. Écrire la classe CarteMauve qui
va décrire une carte.
Corrigé.
class CarteMauve{
Client cl;
int num_carte;
private int code;
}
On notera l'emploi du mot clef private pour empêcher les
utilisateurs d'accéder au code secret.
Question 6.
Écrire une fonction
static int fabriquerCode(){...}
qui retourne un nombre aléatoire de quatre chiffres, dont le chiffre
de tête n'est pas un 0.
Corrigé.
static int fabriquerCode(){
int c = 0;
c = 1 + (int)(9 * Math.random());
for(int i = 1; i < 4; i++)
c = 10 * c + (int)(10 * Math.random());
return c;
}
Question 8.
Écrire la fonction de création:
static CarteMauve creer(Client c){...}
qui fabrique une carte pour le client c, avec un numéro de code
aléatoire de quatre chiffres. On veut également que chaque carte ait
un numéro d'ordre différent, la première aura pour numéro 1, la
deuxième 2, etc.
Corrigé.
On utilise ici une variable de classe nombre qui est partagée
par toutes les fonctions de la classe:
static int nombre = 0;
static CarteMauve creer(Client c){
CarteMauve cm = new CarteMauve();
cm.cl = c;
nombre++;
cm.num_carte = nombre;
cm.code = fabriquerCode();
System.out.println("Voici votre numéro de code : "+cm.code);
return cm;
}
Question 10.
Écrire la fonction
static boolean verifierCode(CarteMauve cm, int c){...}
qui retourne vrai si le numéro de code c est correct.
Corrigé.
static boolean verifierCode(CarteMauve cm, int c){
return cm.code == c;
}
Question 12.
Écrire la classe GestionCartesMauves qui permet de
gérer au plus 100 cartes, sous la forme d'un tableau d'objets de la classe
CarteMauve. Écrire une fonction qui permet de tester toutes
les fonctions précédemment écrites, en créant une carte,
le nom du client étant laissé à votre imagination. On demandera à
l'utilisateur d'entrer un code pour vérification.
Corrigé.
class GestionCartesMauves{
final static int NB_CLIENTS = 100;
static CarteMauve[] tcm = new CarteMauve[NB_CLIENTS];
public static void main(String[] args){
Client cl;
int c;
cl = Client.creer("dg", 1234);
tcm[0] = CarteMauve.creer(cl);
c = TC.lireInt();
System.out.println(CarteMauve.verifierCode(tcm[0], c));
}
}
Exercice 3.
On reprend l'exercice fait en cours sur le développement des fonctions
cos n x et sin n x sous forme de polynômes en cos x et sin
x. On rappelle les formules:
Question 14.
On définit pour n³ 0 le vecteur
En particulier,
Montrer qu'il existe une matrice M dont les coefficients s'expriment
en fonction de C = cos x et S = sin x telle que
Corrigé.
On écrit:
D'où:
Question 16.
On décide de fabriquer une chaîne de caractères qui
représente le développement de cos n x (resp. sin n x) comme
dans le cours, mais de façon différente. La matrice M est
représentée par un tableau M à deux lignes et deux colonnes
dont les coefficients sont des chaînes de caractères. On va
effectuer des opérations sur ces chaînes comme on le ferait sur une
matrice normale, mais symboliquement.
a) Donner le type du tableau à deux lignes et deux colonnes
représentant la matrice M.
Corrigé.
String[][] M = new String[2][2];
b) Écrire la fonction
static String addmul(String ma, String mb, String va, String vb){...}
qui retourne une chaîne qui représente le résultat de la
multiplication symbolique ma × va + mb × vb. Par exemple,
le résultat de l'appel
s = addmul("aa", "bb", "(x)", "y+1");
donnera à s la valeur
"(aa)*((x))+(bb)*(y+1)"
(noter les parenthèses). On ne demande aucune simplification des
expressions au cours du calcul. On rappelle que pour concaténer deux
String, s et t, on utilise l'opération s+t.
Corrigé.
static String addmul(String ma, String mb, String va, String vb){
return "("+ma+")*("+va+")+("+mb+")*("+vb+")";
}
c) En déduire la fonction
static String[] mult(String[][] M, String[] V){...}
qui retourne le produit symbolique de M par V, où
M est une matrice 2× 2, et V un vecteur de deux
lignes.
Corrigé.
static String[] mult(String[][] M, String[] V){
String[] W = new String[2];
for(int i = 0; i < 2; i++)
W[i] = addmul(M[i][0], M[i][1], V[0], V[1]);
return W;
}
d) Écrire la fonction
static String[] cossin(int n){...}
qui retourne le vecteur Vn symbolique, calculé par n
multiplications par la matrice M.
Corrigé.
static String[] cossin(int n){
String[][] M = new String[2][2];
String[] V = new String[2];
M[0][0] = "C";
M[0][1] = "-S";
M[1][0] = "S";
M[1][1] = "C";
V[0] = "1";
V[1] = "0";
for(int i = 1; i <= n; i++)
V = mult(M, V);
return V;
}
e) Décrire un algorithme de calcul de Vn qui ferait
O(log n) itérations, au lieu de n. Écrire les fonctions Java
correspondantes.
Corrigé.
À partir de l'écriture Vn = Mn V0, on peut penser évaluer Mn
par la méthode d'exponentiation binaire vue en cours, puis de
multiplier le résultat par V0.
Cette approche nécessite d'abord d'écrire une fonction de produit de
deux matrices 2× 2:
// A et B sont des matrices 2x2
static String[][] multMat(String[][] A, String[][] B){
String[][] C = new String[2][2];
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
C[i][j] = addmul(A[i][0], A[i][1], B[0][j], B[1][j]);
return C;
}
puis d'écrire la méthode binaire d'exponentiation, qui est un
copier-coller du programme déjà donné:
static String[][] exp(String[][] M, int n){
if(n == 0){
String[][] Id = new String[2][2];
Id[0][0] = "1";
Id[0][1] = "0";
Id[1][0] = "0";
Id[1][1] = "1";
return Id;
}
if(n == 1)
return M;
if((n % 2) == 0){
String[][] MM = exp(M, n/2);
return multMat(MM, MM);
}
else{
String[][] MM = exp(M, n/2);
MM = multMat(MM, MM);
return multMat(MM, M);
}
}
Il ne reste plus alors qu'à écrire la fonction de calcul:
static String[] cossin2(int n){
String[][] M = new String[2][2], Mn;
String[] V = new String[2];
M[0][0] = "C";
M[0][1] = "-S";
M[1][0] = "S";
M[1][1] = "C";
Mn = exp(M, n);
V[0] = "1";
V[1] = "0";
return mult(Mn, V);
}
Ce document a été traduit de LATEX par
HEVEA.