|
| Le signe © renvoie à la correction |
Écrivez un programme qui construit une collection triée par ordre croissant contenant n nombres entiers (représentés par des objets Integer) produits au hasard et dont la valeur est comprise entre 0 et 1000. A votre choix, la valeur de n est lue au début de l’exécution ou est un argument du programme. Ensuite, ce dernier affiche la collection construite afin qu’on puisse constater qu’elle est bien triée.
A. Dans la première version du programme la collection est une sorte de List (par exemple un Vector ou une LinkedList) que vous triez, après la construction, en utilisant une méthode ad hoc de la classe Collections.
B. Dans une deuxième version, la collection est une sorte de Set (c’est-à-dire un HashSet ou un TreeSet, mais avez-vous le choix ?) si bien qu’elle est constamment triée.
Quelle différence importante y a-t-il entre ces deux manières de faire ?
En supposant qu’une interface CritereSelection a été ainsi définie
public interface CritereSelection {
boolean ok(Object x);
}
écrivez une classe TestSelection avec une méthode de signature
static Collection selection(Collection source, CritereSelection critere);
qui renvoie la collection formée des éléments de source
qui satisfont le critere donné. Écrivez, également dans la classe TestSelection, une méthode
main qui
A. Pour commencer, faites en sorte que selection renvoie un objet Vector.
B. Une meilleure solution consisterait à renvoyer une collection de même type que source. A cet effet, constatez que toutes les classes implémentant l’interface Collection ont un constructeur public sans argument et examinez la documentation des méthodes java.lang.Object.getClass() et java.lang.Class.newInstance().
En supposant que vous disposez d’une interface telle que
public interface Transformation {
Object transfo(Object x);
}
programmez une classe ListeTransformable ainsi définie : un objet lt de type ListeTransformable est une liste chaînée (classe LinkedList) possédant en plus une méthode ordinaire (c.-à-d. non statique)
ListeTransformable transforme(Transformation f);
telle que lt.transforme(f) est la liste obtenue en appliquant la transformation f à chaque élément de lt.
A. Définissez la classe ListeTransformable en
utilisant la composition (c.-à-d. un objet ListeTransformable
a un objet LinkedList). Écrivez une méthode main qui la teste en construisant et en affichant une première ListeTransformable qui contient les 50 premiers entiers et une deuxième ListeTransformable qui contient les carrés de ces nombres : 0, 1, 4, 9, 16...
B. Définissez la classe ListeTransformable en
utilisant l’héritage (c.-à-d. un objet ListeTransformable
est une sorte d’objet LinkedList), avec une méthode main comme ci-dessus.
C. Quelle manière de faire vous semble préférable ? Citez une situation où la composition serait évidemment préférable.
On vous demande d’écrire une classe Annuaire pour mémoriser un ensemble de numéros de téléphone et d’adresses. Chaque entrée est représentée par une fiche à plusieurs champs : un nom, un numéro et une adresse. La structure des fiches est décrite par une classe Fiche que vous devez écrire.
Écrivez également une classe Annuaire comportant une table associative (Map) qui sera faite d’associations ( un_nom , une_fiche ).
A. Dans un premier temps, la table associative en question sera une instance de la classe HashMap. Écrivez un programme répétant les opérations suivantes
B. On constate que la commande ! produit l’affichage des fiches dans un ordre imprévisible. Que faut-il changer dans le programme précédent pour que les fiches apparaissent dans l’ordre des noms ?
C. [Facultatif] Faites en sorte qu’à la fin (resp. au début) du programme l’annuaire soit enregistré (resp. lu) dans un fichier nommé annuaire.obj. Utilisez des flux ObjectInputStream et ObjectOutputStream (que l’on doit créer à partir de flux FileInputStream et FileOutputStream préexistants).
N’oubliez pas d’autoriser (par un énoncé « implements Serializable ») la « sérialisation » des objets qui doivent être écrits ou lus dans le fichier.
Les applications Java accèdent à un ensemble de propriétés système qui définissent des aspects de leur environnement d’exécution, comme la version de la machine Java, le système d’exploitation sous-jacent, le répertoire de travail, etc. Ces propriétés sont codées sous la forme de couples de chaînes (clé, valeur), et on les obtient par un appel de la méthode System.getProperties() qui renvoie un objet Properties qui est une sorte de table associative ou Map.
Pour connaître la valeur d’une propriété à partir de son nom on utilise System.getProperty(nom)
De manière analogue, une application Java accède à l’ensemble de variables d’environnement (path, user, etc.) définies au niveau du système d’exploitation sous-jacent ; c’est encore une table associative, ou Map, qu’on obtient par un appel de la méthode System.getenv().
Pour obtenir la valeur d’une variable d’environnement a partir de son nom on écrit System.getenv(nom).
Écrivez une méthode
static void afficherMap(Map tableAssoc);
qui affiche les éléments d’une table associative sous la forme
clé1 --> valeur1
clé2 --> valeur2
etc. Servez-vous en pour obtenir la liste des propriétés système avec leur valeurs, puis des variables d’environnement avec leurs valeurs.
N.B. Properties est une sous-classe de Hashtable, elle-même sous-classe de Dictionary. N’investissez pas dans ces deux classes, elles sont obsolètes l’une et l’autre.
Une arborescence (avec moins de rigueur on dit souvent arbre) est une structure de données formée d’un ensemble E et d’une relation qui à chaque élément de E – sauf un, appelé la racine de l’arborescence – associe un autre élément appelé son père.
Les éléments d’une arborescence sont appelés nœuds ; à chaque nœud n est donc associée une liste, éventuellement vide, de nœuds dont n est le père ; on les appelle les fils de n. Lorsqu’un nœud n’a pas de fils, on dit que c’est une feuille.
A. Écrivez une classe Noeud<E> pour représenter les [nœuds des] arborescences (E représente le type des informations portées par les nœuds). Cette classe doit avoir les méthodes publiques suivantes :
B. Pour essayer la classe Noeud, écrivez un programme qui construit et affiche l’arbre de tous les « mots », sensés ou non, d’au plus trois lettres formés avec les quatre lettres a, b, c, d (il y en 85: le mot vide, puis a, aa, aaa, aab, aba, abb, ..., ddc, ddd).
C. Pour avoir un essai plus intéressant, écrivez un programme qui construit et affiche l’arborescence des fichiers et répertoires ayant pour racine un répertoire donné.
Indications. Pour vous promener dans les fichiers et répertoires, les méthodes suivantes de la classe java.io.File vous seront utiles : getName(), isDirectory(), listFiles().
Un graphe non orienté G = (S, A) est déterminé par la donnée d’un ensemble S, dont les éléments sont appelés les sommets, et un ensemble A de paires de sommets dont les éléments sont appelés arêtes. Étant donnée une arête a = {s1, s2} on dit que s1 et s2 sont les extrémités de a et donc que s1 et s2 sont deux sommets adjacents ou voisins.
On représente souvent S comme un ensemble de points du plan et A comme un ensemble d’arcs ou segments joignant ces sommets (il découle de notre définition des graphes qu’il ne peut pas y avoir deux arêtes distinctes ayant les mêmes extrémités).
Dans beaucoup d’applications on associe un poids à chaque arête : par exemple, si le graphe représente un réseau routier, chaque arête correspond à un tronçon de route entre deux carrefours et est naturellement affectée d’un poids, la longueur du tronçon :
Il existe plusieurs manières de représenter les graphes. Dans le programme réalisé ici nous allons le faire en associant à chaque sommet s la liste des couples (s’, p) où s’ est un sommet adjacent à s et p le poids de l’arête correspondante. Par exemple, dans la figure ci-dessus, pour le sommet étiqueté a cette liste est [(f, 5), (b, 3)], pour le sommet b la liste est [(a, 3), (f, 6), (e, 4 ), (c, 1)] et ainsi de suite.
A. Écrivez la classe Voisin dont les instances représentent ces couples (sommet, poids). Faites le plus simplement simple, ce n’est qu’une classe auxiliaire.
Écrivez la classe Sommet dont les instances représentent les sommets du graphe. Elle comporte les méthodes publiques :
Écrivez la classe Graphe qui se comporte comme une table associative (ou « map ») dont les valeurs sont les sommets du graphe et les clés les étiquettes correspondantes. Elle aura les méthodes publiques :
Pour essayer tout cela, écrivez un programme principal qui crée un graphe analogue à celui de la figure ci-dessus et affiche tous les chemins joignant deux de ses sommets.
Indication. Pour l’écriture de la fonction tousChemins il est recommandé d’écrire une fonction auxiliaire
void chemins(Sommet depart, Sommet arrivee, Stack pile);
qui, si le problème n’est pas résolu (i.e. si départ n’est pas égal à arrivée), parcourt les sommets voisins de départ et se rappelle elle même avec chacun de ces sommets pour nouveau départ. La pile donnée représente le bout de chemin déjà construit ; elle sert à vérifier que le chemin en cours de construction ne boucle pas et à l’affichage de la solution le moment venu.
B. Ajoutez à la classe Graphe une méthode publique
void unChemin(String depart, String arrivee)
qui affiche un chemin joignant les sommets indiqués (n’importe quel chemin ; par exemple, le premier trouvé).
C. Écrivez une méthode
void plusCourtChemin(String depart, String arrivee)
qui affiche le plus court chemin joignant les deux sommets indiqués.