Info 1ième année
  C ontrôle      A lgo   C ++
durée: 50 minutes
février 2005
Des explications ou justifications concises sont appréciées du correcteur.

Question 1

La classe Point, définie ci-contre, mémorise les coordonnées d'un point (attributs x et y) et un caractère (attribut a) servant par exemple à désigner un point.

♦ a ♦ Donnez l'affichage fourni par le programme ci-contre quand on tape au clavier   -6   8.8

♦ b ♦ Définir la fonction milieu (prototype ci-contre) qui prenant deux points a et b en paramètre, renvoie un point calculé comme le milieu du segment [a b]. Le troisième argument du prototype sert à désigner le point calculé.

 class Point {
 private:
 float x,y;
 Point(float u,float v){x=u;y=v;a='?';}
 public:
 char a;
 Point(char c='O'){ a=c; x=0; y=0;}
 float abs() const {return x;}
 float ord() const {return y;}
 Point translater(float u,float v)const{
    return Point(x+u,y+v);
    }
 void affiche(char tc[]="") const {
    cout<<tc<<a<<'('<<x<<','<<y<<')';
    }
 };
 
 Point milieu(Point a,Point b,char c='M');
 
 int main(int nm,char*tm[],char*te[]) {
 const Point p('P'); Point q('Q');
 p.affiche("un Point:");
 float a,b;
 cout<<"\n2 coordonnées? "; cin>>a>>b;
 q=p.translater(a,b);
 q.affiche();
 return 0;
 } 

Question 2

Dans l'agrégat Etudiant, défini ci-contre, gene est la moyenne générale obtenue par un étudiant sur toutes les matières, alors que info est sa moyenne obtenue sur les notes d'informatique.
Le type Promo est utilisé pour mémoriser ne étudiants dans le tableau te; on considère que les éléments de te sont ordonnés par ordre croissant sur le nom de l'étudiant.
 constante MAXE: (entier ← 1000) 
 Type Etudiant = agrégat
    nom: chaîne
    gene: réel
    info: réel
 fin
 Type Promo = agrégat
    te:tableau[1,MAXE] d'Etudiant
    ne: entier
 fin

♦ a ♦ Ecrire en langage algorithmique la procédure extraire(p,ti,ni) qui, à partir d'une Promo p, fournit d'une part dans le tableau ti les indices des étudiants ayant une moyenne en informatique supérieure ou égale à 10 (ce tableau doit être ordonné), et d'autre part le nombre ni de ces étudiants.

♦ b ♦ Ecrire en langage algorithmique la fonction geneEtu(p,ti,ni,nomEtu) qui, à partir d'une Promo p et d'un nom nomEtu vérifie que l'étudiant en question a plus de 10 en informatique et renvoie sa moyenne générale; si le nom n'existe pas ou si cet étudiant a moins de 10 en informatique, la valeur renvoyée doit être -1. Les paramètres ti et ni sont fournis à la fonction et ont le même sens que ci-dessus.

 

 

 

 

 

  Correction  

Question 1

L'affichage fourni par le programme est ci-contre. Remarquer que la méthode translater renvoie un Point construit par le constructeur privé, qui fixe à l'attribut a la valeur '?'; donc p.translater(a,b) renvoie un Point avec l'attribut a valant '?'.
   un Point:P(0,0)
   2 coordonnées? -6 8.8
   ?(-6,8.8)

La fonction milieu, ci-contre, est externe, donc on ne peut y utiliser que les attributs ou méthodes publiques de la classe Point.
Pour renvoyer un point avec l'attribut a valant c (3ième paramètre), on écrit l'affectation m.a=c , qui est autorisée car l'attribut a est public.
   Point milieu(Point a, Point b, char c) {
   Point m;
   float u = (a.abs()+b.abs())/2,
   v =(a.ord()+b.ord())/2;
   m = m.translater(u,v);
   m.a = c;
   return m;
   }

Question 2

Extraction des indices des étudiants d'une promo ayant au moins 10 en informatique.
C'est un parcours complet du tableau te d'une Promo. En extrayant les indices par valeurs croissantes on conserve l'ordre sur les noms, déjà présent dans te, c'est-à-dire qu'on a après extraction:
    te[ti[0]] ≤ te[ti[1]] ≤ ... te[ti[ni-1]]
   procédure extraire(p, ti, ni)
   Paramètres (D) p : Promo
              (R) ti : tableau[1,MAXE] d'entiers
              (R) ni : entiers  { nb.entiers dans ti }
   Variables i;
   Début
      { Parcours complet du tableau d'Etudiant }
      ni ← 0
      pour i←1 à p.ne faire
         si   p.te[i].info >= 10 alors
            ni ← 1+ni
            t[ni] ← i;
         fsi
      fpour
   Fin
Recherche d'un étudiant d'après son nom.
Les noms des étudiants sont ordonnés dans p.te, mais aussi les noms accessibles par les indices placés dans ti, car l'algorithme d'extraction a placé dans ti des indices croissants. On peut donc adapter donc l'algorithme standard de recherche dichotomique.
 
Chercher un nom en utilisant les indices mémorisés dans ti assure qu'on atteint tous les étudiants ayant plus au moins 10 en informatique.
 
geneEtu recherche un étudiant d'après son nom, parmi les étudiants ayant au moins 10 en informatique et renvoie sa moyenne générale. Si le nom ne correspond pas à un étudiant ayant au moins 10, la valeur renvoyée est -1.
   fonction geneEtu(p, ti, ni, nomEtu) retourne réel
   Paramètres (D) p : Promo
              (D) ti : tableau[1,MAXE] d'entiers
              (D) ni : entiers     { nb.entiers dans ti }
              (D) nomEtu : chaîne
   Variables id, if, im;
   Début
     { recherche dichotomique standard }
     id←0; if←1+ni
     Tant que if-id>1
        im ← (id+if)/2
        Si nomEtu < p.te[ti[im]].nom alors im ← if
                                     sinon im ← id
        Fsi
     Ftq
     { Analyse à la sortie de la boucle }
     Si id=0 alors retourner -1
     sinon si p.te[ti[id]].nom != nomEtu
             alors retourner -1
     sinon         retourner p.te[ti[id]].gene
   Fin
   

 

 

 

 

 

Info 1ième année
  C ontrôle      A lgo   C ++
durée: 50 minutes
février 2005
Des explications ou justifications concises sont appréciées du correcteur.

Question 1

 class Vecteur {
 private:
 int x,y;
 Vecteur(int u,int v){x=u;y=v;a='?';}
 public:
 char a;
 Vecteur(char c='O'){ a=c; x=0; y=0;}
 int cx() const {return x;}
 int cy() const {return y;}
 Vecteur changer(int u,int v)const{
    return Vecteur(x+u,y+v);
    }
 void affiche(char tc[]="") const {
    cout<<tc<<a<<'['<<x<<','<<y<<']';
    }
 };
 Vecteur oppose(const Vecteur &a,char c='S');
 
 int main(int nm,char*tm[],char*te[]) {
 const Vecteur u('U'); Vecteur v('V');
 u.affiche("un Vecteur:");
 int a,b;
 cout<<"\n2 composantes? "; cin>>a>>b;
 v=u.changer(a,b);
 v.affiche();
 return 0;
 } 
La classe Vecteur, définie ci-dessus, mémorise les composantes d'un vecteur d'entiers (attributs x et y) et un caractère (attribut a) servant par exemple à désigner ce vecteur.
♦ a ♦ Donnez l'affichage fourni par le programme ci-contre quand on tape au clavier   -6   8
♦ b ♦ Définir la fonction oppose(prototype ci-dessus) qui prenant un vecteur a en paramètre, renvoie l'opposé de ce vecteur. Le deuxième argument du prototype sert à désigner le vecteur calculé.

Question 2

L'agrégat Adhérent, défini ci-contre, permet de mémoriser des informations sur les membres d'un club.
Le type Club est utilisé pour mémoriser na adhérents dans le tableau ta; on considère que les éléments de ta sont ordonnés par ordre croissant sur le nom de l'adhérent.
 constante MAXA: (entier ← 1000) 
 Type Adhérent = agrégat
    nom: chaîne
    sexe: caractère { 'M' ou 'F'}
    age: entier
 fin
 Type Club = agrégat
    ta:tableau[1,MAXA] d'Adhérent
    na: entier
 fin

♦ a ♦ Ecrire en langage algorithmique la procédure extraire(c,ti,ni) qui, à partir d'une Club c, fournit d'une part dans le tableau ti les indices des adhérents de sexe féminin et d'autre part le nombre ni de ces adhérentes.

♦ b ♦ Ecrire en langage algorithmique la fonction ageAdhérente(c,ti,ni,nomAdh) qui, à partir d'une Club c et du nom nomAdh vérifie qu'il existe une adhérente ayant ce nom et renvoie son age; si elle n'existe pas, la valeur renvoyée doit être -1. Les paramètres ti et ni sont fournis à la fonction et ont le même sens que ci-dessus.