Corrigé du Contrôle d'Informatique INF 311

Promotion 2001

Sujet proposé par François Morain

5 juillet 2002

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.

On se propose d'écrire un embryon de programme de gestion du fichier des cartes grises (document d'identification pour un véhicule à moteur).

Question 2.

a) Écrire la classe Proprietaire qui contient les éléments suivant : le nom (une variable de type String), et la date d'obtention du permis de conduire (trois entiers représentant le jour, le mois, l'année).
b) Écrire la fonction

  static Proprietaire creer(String n, int j, int m, int a){...}

qui crée un objet de la classe initialisé avec les valeurs passées en argument.
Corrigé.

class Proprietaire{
  String nom;
  int jour, mois, annee;

  static Proprietaire creer(String n, int j, int m, int a){
    Proprietaire prop = new Proprietaire();

    prop.nom = n;
    prop.jour = j;
    prop.mois = m;
    prop.annee = a;
    return prop;
  }
}

Question 4.

L'immatriculation d'un véhicule est une chaîne alphanumérique de 8 caractères dont voici trois exemples typiques :

1234 YZ 91      567 ABC 01      0123 LU 2A

Cette donnée est découpée en trois parties : la dernière code le département, toujours sur deux caractères (en métropole) ; la première et la deuxième partie permettent de coder le numéro d'ordre du véhicule. Ces deux parties seront supposées être constituées de quatre chiffres et deux lettres, ou bien trois chiffres et trois lettres. Pour simplifier, on suppose que tous les chiffres de 0 à 9 et toutes les lettres de l'alphabet sont utilisables.

On décide de représenter une immatriculation par une instance de la classe Immatriculation qui contiendra trois champs : un entier pour la première partie, une chaîne de caractères pour la deuxième et une chaîne de caractères pour la troisième.
a) Donner la définition de cette classe en Java.
b) Écrire une fonction

  static Immatriculation creer(int g, String m, String d){...}

qui permet de construire un objet de type Immatriculation de façon agréable, comme dans :

  Immatriculation im = Immatriculation.creer(1234, "YZ", "91");

Corrigé.

class Immatriculation{
  int partie1; String partie2; String partie3;

  static Immatriculation creer(int p1, String p2, String p3){
    Immatriculation im = new Immatriculation();

    im.partie1 = p1;
    im.partie2 = p2;
    im.partie3 = p3;
    return im;
  }
}

c) Écrire la fonction

  static void afficher(Immatriculation im){...}

permettant d'afficher un objet de la classe Immatriculation à l'écran. On demande que les affichages respectifs de 1234 ZZ 81, 11 ABG 91 soient (les trois parties séparées par un espace à chaque fois) :

1234 ZZ 81      011 ABG 91

Corrigé. Il est commode d'introduire une fonction versChaine convertissant une immatriculation en chaîne de caractères, la fonction d'affichage appelant ensuite cette fonction.

  static void afficher(Immatriculation im){
    System.out.print(versChaine(im));
  }

  static String versChaine(Immatriculation im){
    String s1, s2, s3;
    int l1, l2, l3;

    // traitement de la première partie
    // attention aux cas douteux, genre 011 ABG 91
    s1 = ""+im.partie1; // conversion
    l1 = s1.length();
    l2 = im.partie2.length();
    // partie1 doit occuper 6-l2 caractères (4 ou 3)
    for(int i = 0; i < 6-l2-l1; i++)
      s1 = "0"+s1;
    // traitement de la deuxième partie
    s2 = "";
    for(int i = 0; i < im.partie2.length(); i++)
      s2 = s2+im.partie2.charAt(i);
    return s1+" "+s2+" "+im.partie3;
  }

d) Écrire la méthode

  static Immatriculation suivante(Immatriculation im){...}

qui à partir de l'immatriculation im crée sa suivante dans l'ordre. Par exemple, la suivante de 1234 YZ 91 est 1235 YZ 91 et celle de 9999 ZZ 91 est 000 AAA 91. On conviendra que le suivant de 999 ZZZ 91 est 000 ??? 91.
Corrigé. Il s'agit là d'incrémenter un compteur alphabétique et numérique à la main. On commence par incrémenter la première partie du numéro. En cas de débordement arithmétique, on doit faire avancer la deuxième partie qui comporte des lettres. La fonction principale est la suivante :

  static Immatriculation suivante(Immatriculation im){
    int suiv1, l2;
    String suiv2;

    l2 = im.partie2.length();
    suiv1 = im.partie1 + 1;
    if(((l2 == 2) && (suiv1 >= 10000)) || ((l2 == 3) && (suiv1 >= 1000))){
      // on doit faire avancer les lettres
      suiv1 = 0;
      suiv2 = avancerLettres(im.partie2);
    }
    else
      suiv2 = im.partie2;
    return Immatriculation.creer(suiv1, suiv2, im.partie3);
  }
}

Il reste à écrire la fonction qui fait avancer les lettres :

  static String avancerLettres(String let){
    int l = let.length(), i;
    String av = "";

    for(i = l-1; i >= 0; i--){
      if(let.charAt(i) == 'Z'){
        av = "A" + av;
      }
      else{
        av = (char)(((int)let.charAt(i)) + 1) + av;
        break;
      }
    }
    if(i < 0){
      // let = "ZZ" ou "ZZZ"
      if(l == 3)
        av = "???";
      else
        av = "AAA";
    }
    for(--i ; i >= 0; i--)
      av = let.charAt(i) + av;
    return av;
  }

La ligne

        av = (char)(((int)let.charAt(i)) + 1) + av;

se lit de la façon suivante : le caractère let.charAt(i) a pour code un entier, que l'on incrémente, ce qui donne le caractère suivant dans l'ordre unicode. Ce nouveau caractère est concaténé avec la chaîne courante.
e) Écrire une fonction qui teste sur des exemples les différents cas possibles pour la fonction précédente.
Corrigé. On commence par programmer une fonction de test élémentaire : elle prend en entrée une immatriculation, ainsi qu'une chaîne qui devrait être une représentation de la chaîne suivante et affiche un message d'erreur en cas de problème :

  static void testerSuivante(Immatriculation im, String reponse){
    Immatriculation suiv = suivante(im);
    String s = versChaine(suiv);

    if(! reponse.equals(s)){
      P("Il y a un problème avec l'immatriculation "+versChaine(im)+"\n");
      P("("); 
      afficher(im);
      P(")+1 = ");
      afficher(suiv);
      P(" != "+reponse);
      P("\n");
    }
  }

Une fois cette fonction écrite, on écrit une fonction de test plus générale :

  static void tester(){
    Immatriculation im;
    
    im = creer(1234, "ZZ", "81");
    afficher(im); P("\n");
    im = creer(11, "ABG", "91");
    afficher(im); P("\n");
    im = creer(4567, "JJ", "2A");
    afficher(im); P("\n");
    im = creer(1, "AA", "10");
    afficher(im); P("\n");
    
    testerSuivante(creer(1234, "ZZ", "81"), "1235 ZZ 81");
    testerSuivante(creer(9999, "AB", "81"), "0000 AC 81");
    testerSuivante(creer(9999, "AZ", "2A"), "0000 BA 2A");
    testerSuivante(creer(9999, "ZZ", "81"), "000 AAA 81");
    testerSuivante(creer(999, "ZZZ", "81"), "000 ??? 81");
  }

Question 6.

Un objet de la classe CarteGrise contient un propriétaire et une immatriculation.
a) Donner la définition de cette classe en Java.
b) Écrire la fonction

  static void Initialiser(Immatriculation im){...}

qui permet d'initialiser l'immatriculation de départ.
Corrigé. Il s'agit ici d'utiliser une variable de classe im_orig :

  static Immatriculation im_orig;

  static void Initialiser(Immatriculation im){
    im_orig = im;
  }

c) Écrire la fonction de création d'une carte grise. On s'assurera que toute nouvelle création d'objet CarteGrise fournisse une nouvelle immatriculation suivant la dernière créée.
Corrigé.

class CarteGrise{
  Proprietaire prop;
  Immatriculation im;
  static Immatriculation im_orig;

  static CarteGrise creer(Proprietaire p){
    CarteGrise cg = new CarteGrise();

    cg.prop = p;
    im_orig = Immatriculation.suivante(im_orig);
    cg.im = Immatriculation.creer(im_orig.partie1, im_orig.partie2, im_orig.partie3);
    return cg;
  }

  public static void main(String[] args){
    Immatriculation im;
    Proprietaire p;
    CarteGrise cg;

    Immatriculation.tester();
    im_orig = Immatriculation.creer(9998, "ZZ", "91");
    p = Proprietaire.creer("FM", 27, 9, 2001);
    cg = CarteGrise.creer(p); 
    Immatriculation.afficher(cg.im);
    System.out.println();
    cg = CarteGrise.creer(p);
    Immatriculation.afficher(cg.im);
    System.out.println();
  }
}

Exercice 2.

On se donne une suite d'entiers distincts a₀, a₁, ..., a_n-1. On suppose que cette suite est circulairement triée (dans l'ordre croissant), c'est-à-dire qu'il existe un entier i, 0 £ i < n tel que a_i, a_i+1, ..., a_n-1, a₀, a₁, ..., a_i-1 soit triée dans l'ordre croissant. Par exemple, les suites

(3, 4, 7, 0, 1, 2), (0, 1, 3), (2, 3, 1)

sont de ce type.
a) Écrire une fonction

  static int trouverDebut(int[] a){...}

qui retourne l'indice de début d'une telle suite à l'aide de O(n) opérations.
Corrigé. Pour mieux visualiser la situation, on peut découper la suite a en trois parties :

la partie I (première montée) : a₀ < a₁ < ··· < a_i-1 ;
la partie II (rupture) : a_i-1 > a_i ;
la parti III (seconde montée) : a_i < a_i+1 < ··· < a_n-1 < a₀.

On fait la convention que si i=0, alors a_-1 = a_n-1. Dans le cas de la suite (3, 4, 7, 0, 1), on peut visualiser la situation sur un dessin :

Le programme qui repère la cassure est :

  static int trouverDebut(int[] a){
    int n = a.length;

    for(int i = 1; i < n; i++)
      if(a[i-1] > a[i])
        return i;
    return 0;
  }

Comme on peut parcourir tout le tableau, on fait bien O(n) comparaisons d'entiers.
b) Écrire une fonction

  static int trouverDebutRapidement(int[] a){...}

qui atteint le même résultat à l'aide de O(log n) opérations. On fournira une explication détaillée de l'algorithme ainsi qu'une justification du temps de calcul.
Corrigé. L'idée consiste à procéder par dichotomie. Supposons que l'indice i cherché se trouve dans l'intervalle [g, d] (au départ, on cherchera dans l'intervalle [0, n-1].

Si g=d, on a terminé. Sinon on coupe l'intervalle en deux et on calcule m=(g+d)/2. On compare alors a_m et a_d. Si a_m < a_d, c'est que m et d se trouvent dans la même montée. Par suite i £ m (on peut avoir i=m si on est au début de la montée). Si a_m > a_d, a_m appartient à la première montée et a_d à la seconde ; m ne peut être égal à i (car a_i est le plus petit élément de a). On en déduit le programme :

  // on sait que g <= i <= d
  static int tDRAux(int[] a, int g, int d){
    if(g == d) return g;
    int m = (g+d)/2;
    if(a[m] < a[d])
      return tDRAux(a, g, m);
    else // a[m] > a[d]
      return tDRAux(a, m+1, d);
  }

  static int trouverDebutRapidement(int[] a){
    return tDRAux(a, 0, a.length-1);
  }

Le temps de calcul est bien O(log n) car on réduit l'intervalle de recherche de moitié à chaque étape.

Ce document a été traduit de L^AT_EX par H^EV^EA.