Liste des cours‎ > ‎

Algorithmique en Java (24 octobre)

Toutes les solutions des exercices devront être placées dans le paquetage fr.enst.transports

Exercice 1

Dans le cadre de sa politique de sécurité l'agence nationale de sécurité ferroviaire a décidé de vous faire écrire un programme permettant de vérifier automatiquement si des chemins empruntés par des trains sont bien disjoints. Pour cela, on dispose d'un fichier contenant, pour chaque trajet, la liste des points par lesquels passent ces chemins. À vous de déterminer si les chemins se croisent ou non.

Invocation du programme : java fr.enst.transports.Croisement fichier_source

Format du fichier source :
  • le fichier est au format texte
  • le fichier contient autant de lignes qu'il y a de trains actuellement en circulation
  • chaque ligne contient la description du chemin d'un train
  • un chemin est constitué d'une succession de points clefs nommés de manière arbitraire et séparés par une virgule
  • toute ligne commençant par le caractère # doit être ignorée

Format de l'affichage en sortie :
  • afficher, à raison d'un par ligne, l'ensemble des points clef  se trouvant sur au moins deux chemins
Tests : vous pouvez utiliser tous les fichiers attachés dont le nom commence par exo1.

Exercice 2

Afin d'étudier la couverture de Paris, l'agence municipale de couverture ferroviaire a décidé de vous faire écrire un programme permettant de déterminer automatiquement si on peut aller en métro / RER d'un endroit à un autre. Pour cela, on dispose d'un fichier contenant la liste des stations par lesquelles passe chaque itinéraire. À vous de déterminer (encore !) si un trajet souhaité est possible.

Invocation du programme : java fr.enst.transports.Chemin fichier_source station_depart station_arrivée

Format du fichier source :
  • le fichier est au format texte
  • chaque ligne contient une succession des stations situées sur une même ligne de métro, séparées par une virgule, dans le sens parcourable par la rame
  • toute ligne commençant par le caractère # doit être ignorée
  • vous pourrez faire des tests avec le fichier exo2-metro.txt (ci-dessous)

Format de l'affichage en sortie :
  • donner un seul trajet de longueur minimale (s'il existe).


Exercice 3

Afin d'éviter les stations de métro qui sentent vraiment trop mauvais, l'office municipal du bien-être a décidé de vous faire écrire un programme permettant d'éviter certaines stations trop malsaines. Compléter fr.enst.transports.Chemin de l'exercice 2 pour que les arguments supplémentaires donnés sur la ligne de commande spécifient des stations par lesquelles les trajets renvoyés ne devront jamais passer.
ċ
exo1-data1.txt
(0k)
Samuel Tardieu,
28 nov. 2011 à 11:31
ċ
exo1-data2.txt
(0k)
Samuel Tardieu,
28 nov. 2011 à 11:31
ċ
exo1-data3.txt
(0k)
Samuel Tardieu,
28 nov. 2011 à 11:31
ċ
exo1-data4.txt
(263k)
Samuel Tardieu,
28 nov. 2011 à 11:31
ċ
exo2-metro.txt
(25k)
Samuel Tardieu,
28 nov. 2011 à 11:31