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.