DEUG MIAGE

Structure de Données et Programmation

 

Examen de Contrôle Continu


Durée 2 heures

Tous les documents sont autorisés

 

CORRECTION

Monome.java             Polynome.java           

 


Votre but sera de représenter et manipuler des Polynômes. Un Polynôme est une somme de Monômes.

Par exemple,

2*X^3       est un monôme de degré 3 et de coefficient 2,

5                  est un monôme de degré 0 et de coefficient 5,

X                  est un monôme de degré 1 et de coefficient 1,

5 + X + 2*X^3 est un polynôme de degré 3.

 


Question 1.

Un polynôme est représenté par une liste chaînée dont chaque élément est un monôme.

1.1.  Définir la classe Monome

1.2.  Définir la classe Polynome

 

On met à votre disposition la méthode public String toString() de la classe Polynome :

public String toString(){

    String s="";

    if (tete!=null) {

      s+=tete.toString();

      for(Monome m=tete.suivant ; m!=null ; m=m.suivant) s+=" + "+m.toString();}

    return s;

}

ainsi que la méthode public String toString() de la classe Monome :

public String toString(){return this.coefficient+"*X^"+this.degre ;}

 

L’exécution du programme :

public class Test{

  public static void main(String[] args){

    Polynome p=new Polynome() ; Monome m ;

    m=new Monome() ; m.coefficient=2 ; m.degre=3 ; p.tete=m ; S.o.p(p);

    m=new Monome() ; m.coefficient=1 ; m.degre=1 ; m.suivant=p.tete ; p.tete=m;

    S.o.p(p);

    m=new Monome() ; m.coefficient=5 ; m.degre=0 ; m.suivant=p.tete ; p.tete=m;

    S.o.p(p);

  }

}

donnera le résultat :

> java Test

2*X^3

1*X^1 + 2*X^3

5*X^0 + 1*X^1 + 2*X^3

 

1.3.  Modifier la méthode public String toString() de la classe Monome  pour obtenir le résultat suivant :

> java Test

2*X^3

X + 2*X^3

5 + X + 2*X^3

 


Question 2.

 

2.1. On suppose que dans un polynôme les monômes sont rangés selon l’ordre croissant de leur degré. Dans la classe Polynome définir une méthode public int degre() qui retourne de degré d’un polynôme ; c'est-à-dire le degré du monôme de degré le plus élevé (et donc le dernier élément de la liste chaînée !).

int degre(){

      int d=0 ;

      Monome curseur=this.tete ;

      ???

      return d ;

}

 

2.2. Dans la classe Polynome, définir la méthode private void ajouterEnQueue(Monome) qui ajoute en queue du polynôme qui reçoit ce message le monôme passé en argument.

 

2.3. On se propose de dériver une fonction polynôme. On rappelle que la fonction dérivée de la fonction monôme de degré strictement positif k*X^n est k*n*X^(n-1) et que la dérivée d’une somme est la somme des dérivées.

Définir la méthode public Monome deriver() de la classe Monome qui retourne le monôme dérivée du monôme qui reçoit le message.

Monome deriver(){

      // on suppose que le degré n'est pas nulle

      //(ie. Le monôme n'est pas une constante)

      Monome d      = new Monome() ;

      d.coefficient = ? ;

      d.degre       = ? ;

      return d ;

 }

 

Définir la méthode public Polynome deriver() de la classe Polynome qui retourne le polynôme dérivée du polynôme qui reçoit le message.

Polynome deriver(){

      Polynome d = new Polynome();

      for(Monome m=this.tete ; m!=null ; m=m.suivant){???}

      return d ;

}

 

L’exécution du programme :

public class Test {

  public static void main(String[] args){

     Polynome p=new Polynome() ; Monome m ;

     m=new Monome() ; m.coefficient=2 ; m.degre=3 ; p.tete=m ;

     m=new Monome() ; m.coefficient=1 ; m.degre=1 ; m.suivant=p.tete ; p.tete=m;

     m=new Monome() ; m.coefficient=5 ; m.degre=0 ; m.suivant=p.tete ; p.tete=m;

     S.o.p("P(X) = "+p) ;

     Polynome p_prime=p.deriver() ; S.o.p("P'(X)= "+p_prime) ;

     S.o.p("degré de P =  "+p.degre()+"\ndegré de P’ = "+p_prime.degre()) ;

    }

}

donnera le résultat :

> java Test

P(X) = 5 + X + 2*X^3

P'(X)= 1 + 6*X^2

degré de P  = 3

degré de P’ = 2

 



 

Question 3.

 

3.1. On suppose que dans un polynôme les monômes sont rangés selon l’ordre croissant de leur degré. On met à votre disposition la méthode public void inserer(Monome) de la classe Polynome qui insère à sa place dans le polynôme qui reçoit ce message le monôme passé en argument.

 

void inserer(Monome nouveau) {

        int d=nouveau.degre ; int c=nouveau.coefficient ;

        if (tete==null || tete.degre>d) {// insertion en tête

            nouveau.suivant=tete ; tete=nouveau;

        }

        else {// On recherche la position ou insérer le monôme

            Monome precurseur=tete ;

            Monome curseur   =tete.suivant ;

            while(curseur!=null && curseur.degre<d){

                 precurseur=curseur ; curseur=curseur.suivant ;

            }

            precurseur.suivant=nouveau ; nouveau.suivant=curseur ;

        }

}

 

L’exécution du programme :

public class Test {

   public static void main(String[] args){

     Polynome p=new Polynome() ; Monome m ;

     m=new Monome() ; m.coefficient=2  ; m.degre=3 ; p.inserer(m) ;

     m=new Monome() ; m.coefficient=1  ; m.degre=1 ; p.inserer(m) ;

     m=new Monome() ; m.coefficient=5  ; m.degre=0 ; p.inserer(m) ;

     S.o.p("P(X) = "+p) ;

     m=new Monome() ; m.coefficient=7  ; m.degre=2 ; p.inserer(m) ;

     S.o.p("P(X) = "+p) ;

     m=new Monome() ; m.coefficient=9  ; m.degre=1 ; p.inserer(m) ;

     S.o.p("P(X) = "+p) ;

     m=new Monome() ; m.coefficient=-10; m.degre=1 ; p.inserer(m) ;

     S.o.p("P(X) = "+p) ;

   }

}

donnera le résultat :

> java Test

P(X) = 5*X^0 + 1*X^1 + 2*X^3

P(X) = 5*X^0 + 1*X^1 + 7*X^2 + 2*X^3

P(X) = 5*X^0 + 9*X^1 + 1*X^1 + 7*X^2 + 2*X^3

P(X) = 5*X^0 + -10*X^1 + 9*X^1 + 1*X^1 + 7*X^2 + 2*X^3

 

Modifier la méthode public void inserer(Monome) de la classe Polynome  afin d’effectuer si nécessaire des simplifications lors de l’insertion. Par exemple, on devra obtenir le résultat suivant :

> java Test

P(X) = 5*X^0 + 1*X^1 + 2*X^3

P(X) = 5*X^0 + 1*X^1 + 7*X^2 + 2*X^3

P(X) = 5*X^0 + 10*X^1 + 7*X^2 + 2*X^3

P(X) = 5*X^0 + 7*X^2 + 2*X^3

 

3.2. Dans la classe Polynome, définir la méthode public Polynome somme(Polynome) qui retourne le polynôme somme du polynôme qui reçoit ce message et du polynôme passé en argument. On pourra utiliser la méthode void inserer(Monome) définie précédemment

 

Polynome somme(Polynome p){

     Polynome s=new Polynome() ; Monome m, curseur ;

     for(curseur=? ; curseur!=null ; curseur=curseur.suivant){

         m=new Monome() ; m.degre=curseur.degre ;

         m.coefficient=curseur.coefficient ; ? ;

     }

     for(curseur=? ; curseur!=null ; curseur=curseur.suivant){

         m=new Monome() ; m.degre=curseur.degre ;

         m.coefficient=curseur.coefficient ; ? ;

     }

     return s ;

}

 

L’exécution du programme :

public class Test {

    public static void main(String[] args){

       Polynome p=new Polynome() ; Monome m  ;

       m=new Monome() ; m.coefficient=2 ; m.degre=2 ; p.inserer(m);

       m=new Monome() ; m.coefficient=1 ; m.degre=3 ; p.inserer(m);

       m=new Monome() ; m.coefficient=5 ; m.degre=1 ; p.inserer(m);

       S.o.p("P(X) = "+p) ;

       Polynome q=new Polynome() ;

       m=new Monome() ; m.coefficient=8 ; m.degre=5 ; q.inserer(m);

       m=new Monome() ; m.coefficient=7 ; m.degre=3 ; q.inserer(m);

       m=new Monome() ; m.coefficient=9 ; m.degre=2 ; q.inserer(m);

       S.o.p("Q(X) = "+q) ;

       S.o.p("P(X)+Q(X) = "+p.somme(q));

   }

}

donnera le résultat :

> java Test

P(X) = 5*X^1 + 2*X^2 + 1*X^3

Q(X) = 9*X^2 + 7*X^3 + 8*X^5

P(X)+Q(X) = 5*X^1 + 11*X^2 + 8*X^3 + 8*X^5

 

3.3. Dans une classe Test, définir une méthode void main(String[]) qui affiche un menu et exécute les actions choisies par l’utilisateur dans ce menu. Le menu se présentera sous la forme suivante :

                               *****************

                               *   A)fficher   *

                               *   I)nserer    *

                               *   S)ommer     *

                               *   D)ériver    *

                               *   D)egré      *

                               *   Q)uitter    *

                               *****************

On pourra, en plus de la méthode main, définir une méthode static void afficherMenu() qui affiche le menu.