Cours CNAM par J. Laforgue

Exercice04_Dichotomie

Retour

Télécharger

Recherche d'un élément dans un tableau d'entier en utilisant un algorithme par recherche dichotomique et tri d'un tableau d'entier

EnonceExercice04.pdf

README.txt
Exercice04.java

//Recherche d'un élément dans un tableau d'entier en utilisant un algorithme par recherche dichotomique et tri d'un tableau d'entier
import java.util.*;

public class  Exercice04
{
        public static void main(String a_args[])
        {

Terminal.ecrireStringln("Si on saisie 0 alors on utilise un tableau déja initialisé : 2,32,12,4,3,213,34,7,9,12,3,10,13.\nCela evite de saisir tous les élements a chaque fois que l'on teste.");

// Création du tableau
        //
        int l_n;
        Terminal.ecrireString("Nombre d'element (ou 0) : ");
        l_n = Terminal.lireInt();
        
        //
        int[] l_tab = {2,32,12,4,3,213,34,7,9,12,3,10,13};
        if (l_n!=0)
            {
                // Saisie des elements du tableau
                //
                l_tab = new int[l_n];
                for(int i=0;i<l_n;i++)
                    {
                        Terminal.ecrireString("element " + i + " : ");
                        l_tab[i] = Terminal.lireInt();
                    }
            } 
        Terminal.ecrireStringln("Affichage du tableau en entrée:");
        for(int l_v : l_tab) Terminal.ecrireString(l_v+" ");
        Terminal.ecrireStringln("");
        
        Terminal.ecrireStringln("Tri par ordre croissant du tableau");
        //
        // L'algorithme est celui du tri à bulle
        //
        boolean l_fini = false;
        int l_nbtri=0;
        while(! l_fini)
            {
                l_fini = true;
                for(int j=0;j<l_tab.length-l_nbtri-1;j++)
                    if (l_tab[j]>l_tab[j+1])
                        {
                            int l_tmp = l_tab[j];
                            l_tab[j]=l_tab[j+1];
                            l_tab[j+1]=l_tmp;
                            l_fini = false;
                        }
                l_nbtri++;
            }

// Affichage du tableau
        Terminal.ecrireStringln("Tableau trie:");
        for(int i=0;i<l_tab.length;i++)
            Terminal.ecrireStringln(""+i+" : "+l_tab[i]);

// Saisir l'élément à rechercher
        Terminal.ecrireString("Element a rechercher (0 pour sortir) : ");
        int l_elt = Terminal.lireInt();

// On boucle tantqeue la valeur saisie est différente de 0
        while(l_elt!=0)
            {
                Terminal.ecrireStringln("Recherche par dichotomie");
                // ------------------------------------------
                
                // initialisation des bornes
                int l_inf = 0;
                int l_sup = l_tab.length-1;
                
                // Initialisation des resultats
                boolean l_trouve = false;  // si l'element est trouve
                int     l_indice = -1;     // indice de l'element trouve
                
                // On vérifie d'abord si l'element ne se trouve pas au début et à la fin 
                //  du tableau
                l_fini = false;
                if (l_tab[l_inf]==l_elt)
                    {
                        l_indice = l_inf;
                        l_trouve = true;
                        l_fini = true;
                    }
                if (l_tab[l_sup]==l_elt)
                    {
                        l_indice = l_sup;
                        l_trouve = true;
                        l_fini = true;
                    }
                
                // On réalise la recherche dichotomique
                while(! l_fini)
                    {
                        // On teste si l'élément est au milieu des bornes
                        int l_milieu = (l_inf+l_sup)/2;
                        if (l_tab[l_milieu]==l_elt)
                            {
                                l_trouve = true;
                                l_fini = true;
                                l_indice = l_milieu;
                            }
                        else
                            {
                                // Si les bornes se touchent la recherche est terminée
                                if ( (l_inf==l_milieu)||(l_sup==l_milieu) )
                                    l_fini = true;
                                else
                                    {
                                        // On continue la recherche en ajustant uen des bornes
                                        //  en fonction de l'ordre des éléments
                                        if(l_elt<l_tab[l_milieu])
                                            l_sup = l_milieu;
                                        if(l_elt>l_tab[l_milieu])
                                            l_inf = l_milieu;
                                    }
                            }
                        
                    }
                
                if (l_trouve)
                    Terminal.ecrireStringln("Element trouve en " + l_indice);
                else
                    Terminal.ecrireStringln("Element non trouve");
                
                Terminal.ecrireString("Element a rechercher : ");
                l_elt = Terminal.lireInt();
                
            }
        }
}

Terminal.java

import java.io.*;
import java.util.*;

/** La classe terminal permet de réaliser ses premiers programmes Java en permettant d'afficher dans la console d'exécution des données de type différents, et en permettant de saisir au clavier des données de type différents.<BR>
    Elle permet aussi de lire et écrire un fichier texte
    Cette classe contient que des méthodes statiques. */
public class Terminal{

// Le buffer standard  de lecture = le clavier
    private static BufferedReader in =
        new BufferedReader(new InputStreamReader(System.in));

/** Cette méthode lit un fichier texte et retourne un le contenu du fichier sous la forme d'un StringBuffer.
        @param nomFichier le nom du fichier qui doit être dans le répertoire courant.
        @return StringBuffer le contenu du fichier. 
        @exception TerminalException (de type RuntimeException) si erreur d'écriture<BR>
        Rappel : Une exception de type RuntimeException n'a pas l'obligation d'être capturée.
*/
    public static StringBuffer lireFichier(String nomFichier)
    {
        try{
            File fichier = new File(nomFichier);
            FileInputStream fis = new FileInputStream(new File(nomFichier));
            
            byte[] buffer = new byte[(int)fichier.length()];
            fis.read(buffer);
            fis.close();
            return(new StringBuffer(new String(buffer)));
        }
        catch(Exception ex)
            {
                exceptionHandler(ex);
            }
        return null;
    }

/** Cette méthode permet de créer un fichier texte à partir du contenu d'un StringBuffer.
        @param nomFichier Le nom du fichier qui est créé dans le répertoire courant
        @param strbuf Le StringBuffer contenant le texte à écrire. 
        @exception TerminalException (de type RuntimeException) si erreur d'écriture
    */
    public static void ecrireFichier(String nomFichier,
                                     StringBuffer strbuf)
    {
        try{
            File fichier = new File(nomFichier);
            FileOutputStream fos = new FileOutputStream(new File(nomFichier));
            
            byte[] buffer = strbuf.toString().getBytes();
            fos.write(buffer);
            fos.close();
        }
        catch(Exception ex)
            {
                exceptionHandler(ex);
            }
    }

/** Cette méthode lit une chaîne de caractère
        @return String la chaîne saisie dans la console d'exécution
       @exception TerminalException (de type RuntimeException) si erreur de lecture
    */
    public static String lireString() // Lire un String
    {
        String tmp="";
        char C='\0';
        try {
            tmp = in.readLine();
        }
        catch (IOException e)
            {
                exceptionHandler(e);
            }
        return tmp;
    }

/** Cette méthode lit un entier
        @return int L'entier saisi dans la console d'exécution
       @exception TerminalException (de type RuntimeException) si la saisie n'est pas un entier ou erreur de lecture
    */
    public static int lireInt()  // Lire un entier
    {
        int x=0;
        try {
            x=Integer.parseInt(lireString());
        }
        catch (NumberFormatException e) {
            exceptionHandler(e);
        }    
        return x ;
    }

/** Cette méthode lit un boolean (false ou true)
        @return boolean Le boolean saisi dans la console d'exécution
       @exception TerminalException (de type RuntimeException) si erreur de lecture. <BR>
       Tout autre valeur que TRUE, FALSE, true ou false, retourne la valeur false
    */
    public static boolean lireBoolean()  // Lire un entier
    {
        boolean b = true;
        try {
            b = Boolean.valueOf(lireString()).booleanValue();
        }
        catch (NumberFormatException e) {
            exceptionHandler(e);
        }    
        return b;
    }

/** Cette méthode lit un double
        @return double Le double saisi dans la console d'exécution
       @exception TerminalException (de type RuntimeException) si la valeur saisie n'est pas un double ou ereur de lecture.
    */
    public  static double lireDouble()  // Lire un double
    {
        double x=0.0;
        try {
            x=Double.valueOf(lireString()).doubleValue();
        }
        catch (NumberFormatException e) {
            exceptionHandler(e);
        }    
        return x ;
    }

/** Cette méthode lit un caractère.
       @exception TerminalException (de type RuntimeException) si erreur de lecture.<BR>
       Si on saisit plus d'1 caractère alors le caractère retourné est le premier.
    */
    public  static char lireChar()  // Lire un caractere
    {
        String tmp=lireString();
        if (tmp.length()==0)
            return '\n';
        else 
            {
                return tmp.charAt(0);
            }
    }

/** Cette méthode ecrit une chaine et ne revient pas à la ligne.
    */
    public static void ecrireString(String s){ // Afficher un String
        System.out.print(s);
    }

/** Cette méthode écrit une chaine et revient à la ligne.
    */
    public static void ecrireStringln(String s) // Afficher un String
    {
        ecrireString(s);
        sautDeLigne();
    }

/** Cette méthode ecrit un entier et ne revient pas à la ligne.
    */
    public static void ecrireInt(int i)  // Afficher un entier
    {
        ecrireString(""+i);
    }

/** Cette méthode écrit un entier et revient à la ligne.
    */
    public static void ecrireIntln(int i)  // Afficher un entier
    {
        ecrireString(""+i);
        sautDeLigne();
    }

/** Cette méthode écrit un booléan et ne revient pas à la ligne.
    */
    public static void ecrireBoolean(boolean b){
        ecrireString(""+b);
    }

/** Cette méthode écrit un booléan et revient à la line.
    */
    public static void ecrireBooleanln(boolean b){
        ecrireString(""+b);
        sautDeLigne();
    }

/** Cette méthode écrit un double et ne revient pas à la ligne.
    */
    public  static void ecrireDouble(double d)  // Afficher un double
    {
        ecrireString(""+d);
    }

/** Cette méthode écrit un double et revient à la ligne.
    */
    public  static void ecrireDoubleln(double d)  // Afficher un double
    {
        ecrireDouble(d);
        sautDeLigne();
    }

/** Cette méthode écrit un caractère et ne revient pas à la ligne.
    */
    public  static void ecrireChar(char c)  // Afficher un caractere
    {
        ecrireString(""+c);
    }

/** Cette méthode écrit un caractère et revient à la ligne.
    */
    public  static void ecrireCharln(char c)  // Afficher un caractere
    {
        ecrireChar(c);
        sautDeLigne();
    }

/** Cette méthode revient à la ligne.
    */
    public static void sautDeLigne(){
        try{
            System.out.println();
        }catch(Exception ex){
            exceptionHandler(ex);
        }
    }

/** Cette méthode retourne l'exception TerminalException
    */
    protected static void exceptionHandler(Exception ex){
        TerminalException err = new TerminalException(ex);
        throw err;
    }

/** Cette méthode écrit l'exception
    */
    public static void ecrireException(Throwable ex){
        ecrireString(ex.toString());
        ex.printStackTrace(System.err);
    }
}

/** Classe de définition de l'exception TerminalException qui peut être retournée dans l'usage des méthodes de la classe Terminal. */
class TerminalException extends RuntimeException{
    Exception ex;
    TerminalException(Exception e){
        ex = e;
    }
}

compil.bat
run.bat

Cours d'Informatique par Jacques LAFORGUE

Retour

Télécharger

Cours d'Informatique
par Jacques LAFORGUE