Les seuls documents papier autorisés sont vos notes de cours, de travaux dirigés et de travaux pratiques. Les documents électroniques autorisés sont les documents présents sur les machines de l'IUT et dont vous êtes l'unique auteur (ainsi que les éventuels documents de cours). En dehors de la machine qui vous est attribuée et de votre matériel de composition (crayons, stylos, feuilles de brouillon…), aucun matériel n'est autorisé.
La documentation de l'API Java doit être consultée uniquement en version locale.
Toutes les réponses devront prendre la forme de fichiers source en langage Java, plus le
fichier QuestionsTest.txt qui est à remplir. Suivez scrupuleusement les
instructions de ce sujet. Vos réponses doivent correspondre aux exemples
d'exécution : soyez rigoureux !
Sauf indication contraire, vous pouvez supposer que les données fournies sur la ligne de commande ou l'entrée standard respectent les restrictions de l'énoncé et ne nécessitent donc pas de contrôle.
Téléchargez l'archive ARemplirDEV32.tar.gz.
Déposez son contenu dans le répertoire de votre choix. Vous obtiendrez un répertoire
nommé DEV32 contenant deux sous-répertoires nommés 1 et
2. Utilisez ces sous-répertoires comme répertoire courant et placez-y tous
les fichiers que vous écrirez durant l'épreuve. Votre nom complet devra être mentionné au
début de chaque fichier (en commentaire).
Effacez tous les fichiers temporaires et ne gardez que les fichiers d'extension
.java et .txt (attention à ne pas effacer vos fichiers
source !). Placez-vous ensuite dans le répertoire immédiatement au
dessus de DEV32 et archivez votre travail, par exemple par la
commande :
bob@box:~$ tar czvvf bob_dev32.tar.gz DEV32Téléversez l'archive ainsi obtenue à cet endroit.
Bulles. (10 points) La technique du tri à bulle permet de trier par ordre croissant une suite de valeurs entières. Si la première valeur n’est pas plus petite que la deuxième, on les intervertit. Puis on fait de même avec la deuxième et la troisième valeur, puis la troisième et la quatrième, et ainsi de suite jusqu’à la dernière valeur. Un tel parcours ne suffit pas à tout trier, mais il garantit que la plus grande valeur se retrouve placée à la fin. Chaque parcours successif va mettre à sa place au moins une valeur, donc en faisant un nombre suffisant de parcours, on obtient obligatoirement une suite triée.
| Exemple : | suite initiale : | 15 | 78 | 21 | 11 | 14 |
|---|---|---|---|---|---|---|
| parcours n°1 : | 15 | 21 | 11 | 14 | 78 | |
| parcours n°2 : | 15 | 11 | 14 | 21 | 78 | |
| parcours n°3 : | 11 | 14 | 15 | 21 | 78 | |
| parcours n°4 : | 11 | 14 | 15 | 21 | 78 |
Écrivez une méthode bulle qui fait un parcours comme décrit précédemment (une bulle). Elle prendra en argument une première file contenant des entiers dans un certain ordre et une seconde file initialement vide. À l'issue de l'exécution de la méthode, la première file devra être vide et la seconde devra contenir les mêmes entiers dans leur nouvel ordre. Cette méthode devra renvoyer un booléen qui indique si l'ordre des valeurs a vraiment changé.
Écrivez ensuite une méthode tri qui trie une file d’entiers en invoquant la méthode bulle à répétition. Vous devrez pour cela créer une file intermédiaire dont la classe est laissée à votre discrétion, et qui n'est pas nécessairement la même que celle de la file d’origine. Lorsqu'une bulle ne modifie pas l'ordre des valeurs, cela indique que le tri est terminé.
Écrivez un programme qui teste votre tri avec une série d'entiers obtenus sur la ligne de commande.
bob@box:DEV32$ java Bulles 6 2 0 5 3 4 7 1 0 1 2 3 4 5 6 7
Dans un deuxième temps (et donc dans un autre fichier), modifiez vos deux méthodes pour qu'elles permettent de trier des files de n'importe quel type d'éléments (pourvu qu'il soit Comparable). Vous pouvez vous baser sur la signature de la méthode sort de la classe Collections qui fait un travail similaire.
Attention N'utilisez pas de files que vous avez personnellement codées dans cette question. Les classes et interfaces du package java.util sont suffisantes.
Deque. (10 points) Un deque (ou file d'attente à
double extrémité) est une structure de données abstraite qui cumule les opérations
des piles et des files. Elle impose un ordre à ses éléments, et permet de retirer ou
d'ajouter un élément à la fin ou au début. Pour éviter la lourdeur de l'interface
Deque de l'API officielle, une interface simplifiée vous est
fournie dans le fichier MinimalDeque.java.
Écrivez une classe SimpleDeque qui réalise cette interface, sans vous aider des classes du package java.util. Vous veillerez à ce que les performances des méthodes demandées ne soient pas dégradées lorsque le nombre d'éléments augmente. De plus, cette classe devra posséder un constructeur sans argument qui instancie un deque vide.
Attention Vous pouvez vous baser sur la classe
Exemple.java pour tester votre travail.
Tests. (20 points, mais en DEV 3.4) Lisez le fichier
QuestionsTest.txt et suivez ses instructions. Notez que pour avoir tous les
points il faut remplir les fichiers QuestionsTest.txt et
TestSimpleDeque.java.