DEUG MIAGE

Structure de Données et Programmation

 

Travaux dirigés

Série n°7


This document is the API specification for the Java 2 Platform, Standard Edition, version 1.3.1

This document is the API specification for the Java 2 Platform, Standard Edition, version 1.4.2


EXERCICE 1 : Tableau de Fractions

 

EXERCICE 2 : Structure de Liste chaînée

 

EXERCICE 3 : Structure de Pile

 

EXERCICE 4 : Structure de File

 

EXERCICE 5 : Qui sera épargné par les cannibales ?

 


EXERCICE 1 : Tableau de Fractions               Exo1.java        Fraction.java


A)    Définir une classe Fraction. Une fraction possède deux attributs, un numérateur et un dénominateur ; les attributs sont de type entier, leur valeur initiale est un nombre entier aléatoire (non nul pour le dénominateur !). Une fraction est capable de répondre au message toString() qui retourne une description de la fraction sous la forme d’une String "numerateur/denominateur=valeur". Ecrire une méthode void simplifieToi() pour que l’exécution de f.simplifieToi() (envoi du message simplifieToi() à f)) simplifie la fraction f (division du numérateur et du dénominateur par leur pgcd). La classe Fraction sera stockée dans le fichier Fraction.java. Utilisez la classe Exo1 suivante pour tester votre solution :

public class Exo1 {

     public static void main(String[] args){

          Fraction f = new Fraction() ; System.out.println(f); // execute f.toString()

          f.numerateur = 6 ; f.denominateur = 2 ; System.out.println(f);

          f.simplifieToi(); System.out.println(f); }}

 

B)     Ecrire une méthode Fraction getSomme(Fraction f) pour que que l’exécution de f.getSomme(g) (envoi du message getSomme(g) à f) retourne la fraction f+g. Ecrire une méthode Fraction getProduit(Fraction f) pour que l’exécution de f.getProduit(g) (envoi du message getProduit(g) à f) retourne la fraction f*g. Utilisez la classe Exo1 suivante pour tester votre solution :

public class Exo1 {

     public static void main(String[] args){

         Fraction f=new Fraction() ; f.simplifieToi(); System.out.println(f);

         Fraction g=new Fraction() ; g.simplifieToi(); System.out.println(g);

         Fraction s=f.getSomme(g)  ; f.simplifieToi(); System.out.println(s);

         Fraction p=f.getProduit(g); f.simplifieToi(); System.out.println(p); }}

 

C)                       Dans la fonction main, créer et afficher un tableau de Fractions. Utiliser la méthode java.util.Arrays.sort() pour trier ce tableau. 
On trouvre dans l’ API l’information suivante :
public static void sort(Object[] a)

Sorts the specified array of objects into ascending order, according to the natural ordering of its elements. All elements in the array must implement the Comparable interface. Furthermore, all elements in the array must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the array).

 


EXERCICE 2 : Structure de Liste Chaînée             Exo2.java               Liste.java


A) On met à votre disposition la classe Element. Cette classe caractérise les éléments dans une liste chaînée ; un élément possède un attribut valeur (de type entier) et un attribut suivant de type Element (c’est bien une définition récursive !) ; la valeur initiale du champ valeur est un nombre entier positif aléatoire.

 

q       Définir la classe Liste. Une liste possède un seul attribut tete de type Element qui représente le premier élément de la liste. Une Liste est initialement vide (la valeur de l’attribut tete est null).

q       Ecrire une méthode void ajouterEnTete(Element e) qui ajouter un nouvel élément e en tête de la liste (celle qui reçoit ce message).

q       Ecrire une méthode String toString() qui retourne une description de la liste (celle qui reçoit ce message) sous la forme d’une String "[valeurDeTete..valeurDeQueue]".

Utilisez la classe Exo2 suivante pour tester votre solution :

public class Exo2 {

    public static void main(String[] args){

         Liste l = new Liste() ;

         for(int i=0; i<10 ; i++) {l.ajouterEnTete(new Element()); }

         System.out.println(l ); // execute l.toString() }}

 

B)

q       Ecrire une méthode void ajouterEnQueue(Element e) qui ajouter un nouvel élément e en queue de la liste.

q       Ecrire une méthode void retirerEnTete() qui supprime (s’il existe !) le premier élément de la liste.

q       Ecrire une méthode void retirerQueue() qui supprime (s’il existe !) le dernier élément de la liste.

Utilisez la classe Exo2 suivante pour tester votre solution :

public class Exo2 {

    public static void main(String[] args){

         Liste l= new Liste() ;                                    System.out.println(l);

         for(int i=0; i<10 ; i++){l.ajouterEnTete(new Element());} System.out.println(l);

           Element e=new Element() ; e.valeur=99 ;

         l.ajouterEnQueue(e) ;                                     System.out.println(l);

         l.retirerEnTete()   ;                                     System.out.println(l);

         l.retirerEnQueue()  ;                                     System.out.println(l); }}

L’exécution donnera, par exemple, le résultat suivant :

> java Exo2

[]

[ 7 3 5 1 4 9 9 3 0 5 ]

[ 7 3 5 1 4 9 9 3 0 5 99 ]

[ 3 5 1 4 9 9 3 0 5 99 ]

[ 3 5 1 4 9 9 3 0 5 ]

 

D)    On met à votre disposition la classe Personne. Cette classe caractérise les éléments dans une liste chaînée de personnes; un élément possède un attribut numero (de type int), un attribut nom (de type String) et un attribut suivant (de type Personne).

q       Ecrire une méthode String toString() qui retourne une description d’une personne (celle qui reçoit ce message) sous la forme d’une String "(numero,nom)".

q       Définir la classe ListeDePersonnes. Une liste de personnes possède un seul attribut tete de type Personne qui représente le premier élément de la liste.

q       On suppose que la liste est triée par ordre croissant des numéros de personne. Ecrire une méthode void inserer(Personne p) qui ajoute un nouvel élément p dans la liste (celle qui reçoit ce message) en conservant l’ordre des numéros.

q       Ecrire une méthode String toString() qui retourne une description de la liste (celle qui reçoit ce message) sous la forme d’une String "[(numero,nom)..(numero,nom)]".

Utilisez la classe Exo2 suivante pour tester votre solution :

import unsa.Console ;

public class Exo2 {

    public static void main(String[] args){

         ListeDePersonnes l = new ListeDePersonnes() ;

         Personne p ;

         for(int i=0; i<3 ; i++) {

             p=new Personne(); p.numero=(int) (Math.random()*100);

             p.nom=Console.readLine("Votre Nom ?");

             l.inserer(p);

         }

         System.out.println(l);

     }

}

L’exécution donnera, par exemple, le résultat suivant :

> java Exo2

[ (17,tutu) (22,toto) (39,titi) (45,tete) (95,tata) ]

 


EXERCICE 3 : Structure de Pile  Exo3.java


A)     Définir la classe Pile. Une pile est une liste chaînée particulière sur laquelle on peut accéder uniquement au premier élément (le sommet !).

q       Ecrire une méthode void empiler(Element e) qui ajouter un nouvel élément e en tête de la pile (celle qui reçoit ce message).

q       Ecrire une méthode void depiler() qui supprime (s’il existe !) le sommet de la pile.

q       Ecrire une méthode int getSommet() qui retourne (s’il existe !) la valeur du sommet de la pile.

Utilisez la classe Exo3 suivante pour tester votre solution :

public class Exo3 {

    public static void main(String[] args){

         Pile p= new Pile() ;                                 System.out.println(p);

         for(int i=0; i<10 ; i++) {p.empiler(new Element());} System.out.println(p);

         p.depiler() ;  p.depiler() ; p.depiler() ;           System.out.println(p);

         Element e= new Element() ; e.valeur=99 ;

         p.empiler(e);                                        System.out.println(p);

         System.out.println("SOMMET : "+p.getSommet()) ;      System.out.println(p); }}

L’exécution donnera, par exemple, le résultat suivant :

> java Exo3

[ ]

[ 2 1 0 7 0 1 9 0 3 7 ]

[ 7 0 1 9 0 3 7 ]

[ 99 7 0 1 9 0 3 7 ]

SOMMET : 99

[ 99 7 0 1 9 0 3 7 ]

 

B)     Ecrire une méthode main pour afficher un menu et exécuter les actions choisies par l’utilisateur. Le menu se présentera sous la forme suivante :

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

                                  *   E)mpiler    *

                                  *   D)epiler    *

                                  *   A)fficher   *

                                  *   S)ommet     *

                                  *   V)ider      *

                                  *   Q)uitter    *

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

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

 

C)     On veut simuler l'emploi d'une calculatrice à notation polonaise inversée. Pour cela, on commence par empiler les arguments numériques, et l'on invoque ensuite les opérations. On cherche donc à définir une application qui traite une série d'arguments itérativement. La commande  java Exo3C arg1 arg2 ... argn traite successivement les arguments arg1, arg2, ... Si l'argument est numérique, on empile ce nombre, sinon l'argument doit être l'un des caractères suivantes :

q       ‘+’ Dans ce cas, on dépile deux nombres et l'on empile leur somme

q       ‘-‘ on dépile deux nombres et l'on empile leur différence

q       ‘*’ on dépile deux nombres et l'on empile leur produit

q       ‘/’ on dépile deux nombres et l'on empile leur quotient

q       ‘a’ on affiche le contenu de la pile

 

On pourra compléter le code suivant :

public class Exo3C {

    public static void main(String[] argv) {

       Pile p = new Pile() ; Element e ;

       int a, b ;

       for(int i=0; i<argv.length; i++) {

           if(argv[i].equals("+"))      {???}

           else if(argv[i].equals("-")) {???}

           else if(argv[i].equals("*")) {???}

           else if(argv[i].equals("/")) {???}

           else if(argv[i].equals("a")) System.out.println(p);

           else // on suppose alors que c'est un nombre entier

               ???

        }

        System.out.println(”Sommet de la pile : ”+p.getSommet());

    }

 }

 

L’exécution donnera, par exemple, le résultat suivant :

> java Exo3C  2 a 3 a + a 7 a - a 10 a * a 60 a / a

[ 2 ]

[ 3 2 ]

[ 5 ]

[ 7 5 ]

[ 2 ]

[ 10 2 ]

[ 20 ]

[ 60 20 ]

[ 3 ]

Sommet de la pile : 3

 


EXERCICE 4 : Structure de File  Exo4.java


A)     Définir la classe File. Une file d’attente est une liste chaînée particulière sur laquelle on ajoute les éléments en tête et on les retire en queue .

B)     Ecrire une méthode void enFiler(Element e) qui ajoute un nouvel élément e en queue de file (en fait en tête de la liste).

C)     Ecrire une méthode void enFiler(int v) qui ajoute un nouvel élément en queue de file dont la valeur est v.

D)     Ecrire une méthode void deFiler() qui supprime (s’il existe !) l’élément en tête de file (en fait en queue de la liste).

E)      Ecrire une méthode int getProchainSorti() qui retourne (s’il existe !) la valeur du prochain élément à sortir de la file (ie. La valeur en tête de file).

Utilisez la classe Exo4 suivante pour tester votre solution :

public class Exo4 {

    public static void main(String[] args){

         File f= new File() ; System.out.println(f);

         for(int i=0; i<5 ; i++) {f.enFiler(i);} System.out.println(f);

         f.deFiler() ;  f.deFiler() ; f.deFiler() ; System.out.println(f);

         Element e = new Element() ; e.valeur=99;

         f.enFiler(e); System.out.println(f);

         System.out.println("PROCHAIN A SORTIR : "+f.getProchainSorti());System.out.println(f); }}

L’exécution donnera, par exemple, le résultat suivant :

> java Exo4

[ ]

[ 4 3 2 1 0 ]

[ 4 3 ]

[ 99 4 3 ]

PROCHAIN A SORTIR : 3

[ 99 4 3 ]

 


EXERCICE 5 : Qui sera épargné par les cannibales ?        Exo5.java


Neuf naufragés échouent sur une île peuplée de cannibales qui ne savent compter que de cinq en cinq. Selon la coutume locale le dernier naufragé est épargné. Afin de faciliter le travail des cannibales, il est suggéré de placer les 9 naufragés sur un cercle ; en d’autres termes, vous devez créer une liste circulaire (le suivant du dernier sera le premier). Il vous suffira ensuite de parcourir cette liste en comptent de cinq en cinq …

A)    Compléter la classe ListeDesNaufrages suivante :

public class ListeDesNaufrages { // liste circulaire des naufragés

    public  Element tete = null  ;

   

    public String toString(){

         String s=""; Element p=tete ;

         int v=p.valeur ;

         do { // on suppose la liste circulaire non vide

             s+="["+p.valeur+"]"+" -> "; p=p.suivant;

         } while (p.valeur!=v);

         return s;

    }

   

    public void ajouterEnTete(Element e){e.suivant=tete ; tete=e;}

   

    public void mangerLeNaufrage(int v){

        // on supprimer le naufragé de numéro v

        // on suppose la liste circulaire non vide

        Element p=tete, pred=null;

        if (tete.valeur==v){// suppression du premier element

            // recherche du dernier

            do {pred=p ; p=p.suivant;} while(p.valeur!=v);

            pred.suivant = ??? ; tete = ??? ;

        }   

        else {// on supprime un élément qui n’est pas en tete

            do{pred=p ; p=p.suivant;}while (p.valeur!=v);

            pred.suivant = ???;

        }

    }

}

 

B)     Qui sera épargné ?

L’exécution donnera, par exemple, le résultat suivant :

> java Exo5

Je compte de 5 en 5 à partir du naufragé 8

[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] ->

LE NAUFRAGE 3 EST MANGE

[1] -> [2] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] ->

LE NAUFRAGE 8 EST MANGE

[1] -> [2] -> [4] -> [5] -> [6] -> [7] -> [9] ->

LE NAUFRAGE 5 EST MANGE

[1] -> [2] -> [4] -> [6] -> [7] -> [9] ->

LE NAUFRAGE 2 EST MANGE

[1] -> [4] -> [6] -> [7] -> [9] ->

LE NAUFRAGE 1 EST MANGE

[4] -> [6] -> [7] -> [9] ->

LE NAUFRAGE 4 EST MANGE

[6] -> [7] -> [9] ->

LE NAUFRAGE 7 EST MANGE

[6] -> [9] ->

LE NAUFRAGE 9 EST MANGE

[6] ->  Je suis épargné !

 


 

Signaler une erreur - Proposer une amélioration -

 

Haut du document