TD n 2 - Correction PDF Java. Licence Informatique. Année

Tri par insertion [tr05] - Exercice

Java - Tri par insertion (Solution). Mots-Clés Algorithmes de tris et rangs Tri par insertion ?. Requis Axiomatique impérative (sauf Fichiers) ?.

Les différentes méthodes de tries

IV)Tri par Insertion (insertionSort) . Au 5èmele tableau est trié et l'algorithme s'arrête et on s'aperçoit qu'il y a N-1 ... Implémentation en java :.

Leçon 903 : Exemples dalgorithmes de tri. Correction et complexité

Java im- plémente ce tri pour des tableau de taille inférieure ou égale à 7. Le tri par insertion séquentiel (Algorithme 4) effectue la recherche de la ...

Algorithmique Trier et Trouver

Tableaux triés algorithmes de tris. 11 de 47. Insertion dans un tableau trié. Algorithme (Insert). Entrées : • Tableau tab

Les algorithmes de tris

Quelques algorithmes de tris. Tris élémentaires. Tri par insertion. Tri par sélection. Tri par permutation. Tris avancés. Tri Fusion. Tri rapide. Blin Lélia.

Chapitre 14 Les techniques de Recherche et de Tri

Fichier : Search.java ; Méthode linearsearch L'algorithme de tri associé au tri par sélection consiste à trouver l'emplacement du ... Tri par insertion.

ALGORITHMES DE TRI

ALGORITHMES DE TRI Entrée : tableau A[] de données comparables (interface Comparable en Java) ... tri par insertion (insertion sort).

TD n 2 - Correction

Java. Licence Informatique. Année 2005-2006. TD n. ?. 2 - Correction Exercice 2 [Tri par insertion et piles] Écrire un programme de tri par insertion ...

Algorithmes de tri quadratiques en java

8 nov. 2008 Algorithmes de tri quadratiques en java ... 3 Tri insertion ... dichotomique dans un tableau trié a une complexité logarithmique.

Algorithmes de tris

— Dans le pire des cas le nombre de comparaisons et d'échanges du tri par insertion est équivalent à n2. 2 . Preuve. Insérer un élément dans un tableau trié de

Universit´e Paris 7Java

Licence InformatiqueAnn´ee 2005-2006

TD n ◦2 - Correction

Piles, Tri et Tours de Hanoi

Exercice 1[Piles]´Ecrire une classe implantant une pile d"´el´ements.

1. Comment repr´esenter la pile vide?

2. D´efinir la classePile. Le constructeur de cette classe construira la pile vide.

3. D´efinir une m´ethode permettant de tester si une pile est vide.

4. D´efinir la m´ethodeempile(ajoute un ´el´ement au sommet de la pile)

5. D´efinir la m´ethodedepile(retourne le sommet et le retire de la pile)

6. D´efinir la m´ethodesommet(retourne le sommet de la pile sans le retirer)

On consid`ere d´esormais qu"un ´el´ement de pile encapsuleune valeur enti`ere.

1. Comment repr´esenter un ´el´ement de pile?

2. D´efinir la classeElementPilequi repr´esente un ´el´ement d"une pile. Les attributs de cette

classe seront priv´es. D´efinir les constructeurs et les accesseurs de cette classe.

3. D´efinir dans la classePilela m´ethodeaffichequi affiche le contenu d"une pile.

Tester la cr´eation d"une pile et sa manipulation en empilant puis d´epilant divers ´el´ements...

Correction :

d´ebut Pile.java public class Pile { private int pos; // position dans le tableau private ElementPile [] p; public Pile () { // creation d"une pile vide de taille 10 p = new ElementPile[10]; pos = 0; public Pile (int taille) { // creation d"un pile vide de taille donnee p = new ElementPile[taille]; public void empile (ElementPile e) { if (pos == p.length) { // plus d"expace

ElementPile[] tmp = new ElementPile[p.length+10];

for (int i = 0; i < p.length; i++) tmp[i] = p[i]; p = tmp; p[pos++] = e; public ElementPile depile () { return p[--pos]; 1 public ElementPile sommet () { return p[pos-1]; public boolean estVide () { return pos == 0; public void affiche () {

System.out.print("Pile: [");

for (int i = pos-1; i >= 0; i--) p[i].affiche ();

System.out.println (" ]");

fin Pile.java d´ebut ElementPile.java public class ElementPile { private int valeur; public ElementPile () { this.valeur = 0; public ElementPile (int valeur) { this.valeur = valeur; public int getValue () { return valeur; public void affiche () {

System.out.print (" "+valeur);

fin ElementPile.java Exercice 2[Tri par insertion et piles]´Ecrire un programme de tri par insertion d"un ensemble de nombres entiers. Les donn´ees sont stock´ees dans une pile A et le programme doit retourner une pile B contenant ces nombres tri´es avec le minimum au sommet de la pile. L"algorithme

propos´e est le suivant : on utilise une pile C qui est vide au d´ebut. Tant que la pile A n"est pas

vide, on consid`ere les deux cas suivants : - si la pile B est vide ou si l"´el´ement au sommet de A est plus petit que celui de B : on retire l"´el´ement au sommet de la pile A pour empiler dansla pile B, puis si la pile C n"est pas vide on retire tous les ´el´ements de la pile C pour empiler dans la pile B. - sinon : on d´eplace l"´el´ement au sommet de la pile B `a la pile C.

D´efinir une classe Tri qui contient trois piles A, B et C, une m´ethodetri(Pile A, pile B, Pile C)

et la m´ethodemain(). La pile A peut ˆetre construite `a partir d"un tableau d"entiers en utilisant

la m´ethodeempile. Tester avec la pile A ={4,3,2,5,8,2,6,9,3}. 2

Correction :d´ebut Tri.java

public class Tri { private Pile A, B, C; public Tri () {} public Tri (Pile A, Pile B, Pile C) { this.A = A; this.B = B; this.C = C; private void tri () { while (!A.estVide()) { if (B.estVide() || B.sommet().getValue() < A.sommet().getValue()) {

B.empile(A.depile());

while (!C.estVide()) B.empile(C.depile()); else C.empile(B.depile()); public Pile tri(Pile A, Pile B, Pile C) { this.A = A; this.B = B; this.C = C; tri(); return B; public static void main (String[] args) { int[] tab = {4,3,2,5,8,2,6,9,3};

Pile A = new Pile();

for (int i = 0; i < tab.length; i++) A.empile (new ElementPile(tab[i]));

Tri t = new Tri();

t.tri (A, new Pile(), new Pile()).affiche(); fin Tri.java

Exercice 3[Jeu des Tours de Hanoi]Pour ceux qui ont encore du temps´Etant donn´e trois piles, etndisques de taille diff´erente empil´es sur la premi`ere, lesplus

petits au dessus des plus grands : Un d´eplacement consiste `a choisir une pile A non vide, et `aenlever le disque au sommet pour le mettre au sommet d"une autre pile B, si le sommet de cette pilen"est pas un disque plus petit (sinon, le d´eplacement est impossible).

On veut d´eplacer tous les disques de la premi`ere pile sur laseconde, en se servant de la derni`ere.

L"algorithme propos´e est le suivant : Pour d´eplacerndisques de la pile A sur la pile C en

utilisant la pile B, on d´eplace (r´ecursivement)n-1 disques de A vers B, puis on d´eplace le

disque restant sur le sommet de la pile A vers la pile C, et on d´eplace (r´ecursivement)n-1 disques de B vers C. 3

D´efinir une classeHanoiqui repr´esente le jeu : trois piles et le nombre de disques. D´efinir le

constructeur qui initialise le jeu `a partir d"un nombre de disques `a empiler et initialise les piles

dans la situation de d´epart. D´efinir la m´ethodeaffichequi affiche le contenu des piles. D´efinir la

m´ethode priv´eedeplaceet la m´ethodejouequi lance le jeu. Enfin, d´efinir la m´ethode statique

mainqui `a partir d"un entier saisi en ligne de commande initialise et lance le jeu. Pour visualiser plus agr´eablement le d´eroulement du jeu,modifier la m´ethode deplace

afin d"afficher l"´etat du jeu apr`es chaque d´eplacement. On vous propose d"utiliser une classe

Afficheurqui propose un affichage un peu ´elabor´e et quelques options pour le d´eroulement du jeu. Recopier le ficher/ens/capron/pub/Afficheur.javadans votre r´epertoire de travail. Modifier la classeHanoien ajoutant un champ de typeAfficheur. Le constructeur devra prendre en param`etre un objet de ce type et l"affecter a votrechamp. Remplacer le contenu de la m´ethodeafficheen effectuant simplement un appel `a la m´ethodeafficherde l"Afficheur qui prend en param`etre les trois piles puis le nombre de disques. Compiler le tout et lancer le jeu en ex´ecutant lemainde la classeAfficheur.

Correction :

d´ebut Hanoi.java public class Hanoi { private Afficheur aff; private Pile A, B, C; private int nbDisques; public Hanoi (int nbDisques, Afficheur aff) { this.aff = aff; this.nbDisques = nbDisques;

A = new Pile();

B = new Pile ();

C = new Pile ();

for (int i = nbDisques; i > 0; i--) A.empile(new ElementPile (i)); public void affiche () { aff.affiche(A, B, C, nbDisques); private void deplace (Pile src, Pile dest, Pile tmp, int n) { if (n > 0) { deplace(src, tmp, dest, n-1); dest.empile(src.depile()); affiche(); deplace(tmp, dest, src, n-1); public void joue () { deplace (A, B, C, nbDisques); fin Hanoi.java 4quotesdbs_dbs6.pdfusesText_12

[PDF] TD n 2 - Correction Java. Licence Informatique. Année

Universit´e Paris 7Java

Licence InformatiqueAnn´ee 2005-2006

Piles, Tri et Tours de Hanoi

1. Comment repr´esenter la pile vide?

2. D´efinir la classePile. Le constructeur de cette classe construira la pile vide.

3. D´efinir une m´ethode permettant de tester si une pile est vide.

4. D´efinir la m´ethodeempile(ajoute un ´el´ement au sommet de la pile)

5. D´efinir la m´ethodedepile(retourne le sommet et le retire de la pile)

6. D´efinir la m´ethodesommet(retourne le sommet de la pile sans le retirer)

1. Comment repr´esenter un ´el´ement de pile?

2. D´efinir la classeElementPilequi repr´esente un ´el´ement d"une pile. Les attributs de cette

3. D´efinir dans la classePilela m´ethodeaffichequi affiche le contenu d"une pile.

Correction :

ElementPile[] tmp = new ElementPile[p.length+10];

System.out.print("Pile: [");

System.out.println (" ]");

System.out.print (" "+valeur);

Correction :d´ebut Tri.java

B.empile(A.depile());

Pile A = new Pile();

Tri t = new Tri();

Correction :

A = new Pile();

B = new Pile ();

C = new Pile ();