Josephus Flavius était un célèbre historien du premier siècle. Durant une guerre il fut pris au piège dans une cave avec son groupe de 40 soldats, entouré par les troupes ennemies. La légende raconte que le groupe encerclé préféra se suicider plutôt que d'être capturé. Ainsi Josephus et ses soldats formèrent un cercle et décidèrent de se tuer mutuellement et successivement, de manière à ce qu'une personne tue la troisième personne sur sa gauche, que la personne à droite du mort tue à son tour la troisième personne sur sa gauche, ainsi de suite jusqu'à ce qu'il ne reste qu'un seul survivant. Restant seul, ce dernier est censé se suicider lui-même. Josephus, qui ne souhaitait pas mourir, trouva rapidement la place sûre, c'est-à-dire la place de la dernière personne debout, sans que quiconque ne reste pour le tuer. Ainsi il resta en vie et put par la suite raconter cette légende. Trouver cette place sûre est maintenant appelé le problème de Josephus.
Après ce TD, vous pouvez en lire plus sur Josephus Flavius à travers cet article sur Wikipedia.
Durant cet exercice nous implémenterons un programme qui simulera une version généralisée du problème de Josephus de la manière suivante : étant donnés n soldats, placés en cercle aux positions [0 ; n-1] avec 0 comme position de départ, il faut retirer chaque m-ième soldat jusqu'à ce que tous les soldats (même Josephus pour simplifier les choses) soient retirés.
Dans l'exemple ci-dessous, nous commençons avec 8 soldats, et nous tuons à chaque tour le troisième soldat sur la gauche (remarquez que lorsqu'il reste au plus trois personnes vivantes, le soldat tuant se compte lui-même dans cette distance de trois soldats):
Le programme que vous devez développer devra prendre comme entrées les nombres n et m, respectivement le nombre de soldats et la distance (dans l'exemple nous avons n=8 et m=3), et produire comme sortie l'ordre dans lequel les soldats seront tués, le dernier "tué" étant finalement le survivant :
java Josephus 8 3
4 7 2 6 3 1 5 8 The surviving soldier is 8
c'est-à-dire que le soldat à la position 4 est le
premier à être tué, et 8 est la place
sûre recherchée par Josephus.
Faites attention au nom des classes, des fonctions et des variables demandées, et respectez le type des entrées et de la sortie des fonctions. Vos programmes seront testés automatiquement, non seulement sur les entrées/sorties mais également sur les structures internes et leur comportement. Aussi le fait de ne pas utiliser les noms demandés fera-t-il échouer les tests automatiques.
Prenez soin de lire et faire exactement ce qui est demandé pour chaque question. Il n'y a pas que les résultats qui seront évalués, mais également la manière dont ils sont obtenus.
Quand c'est le cas, il est indiqué qu'un exercice est indépendant des exercices suivants, ce qui signifie qu'il est possible de continuer les exercices suivants sans résoudre l'exercice courant. Ainsi si vous bloquez à l'un de ces exercices, il peut être bénéfique de le laisser pour plus tard et de continuer les autres exercices.
Notez que tous les exercices donnent des points, et que l'on s'attend à ce que tous les exercices soient résolus.
Aide : Vérifiez toujours si la valeur d'une
référence est
null dans le but d'éviter un
NullPointerException, même dans les cas
extrêmes (par exemple une liste vide). Ces erreurs vous causeront
des points négatifs.
Nous utiliserons une liste chaînée comme structure de
données pour stocker Josephus et ses soldats. Dans cette
partie, nous développerons une liste chaînée
nommée LinkedList, et nous mettrons les fonctions
usuelles sur les listes chaînées dans une
classe Josephus.
Ecrivez un enregistrement LinkedList, qui implémente une
liste chaînée d'entiers (liste chaînée au
sens du polycopié, un entier représentant ici
l'identité d'un soldat). Le champ entier de
l'enregistrement LinkedList se
nommera id. Le champ LinkedList de
l'enregistrement LinkedList se
nommera next. Ecrivez une classe Josephus
qui contient la fonction suivante :
static LinkedList add(int s, LinkedList l)
qui ajoute un élément à la
tête de la LinkedList donnée
en argument. La fonction retourne la
référence de la nouvelle
LinkedList ainsi obtenue.
Vous devez tester votre implémentation en utilisant le code suivant (faites du copier-coller) :
public static void main(String[] args) {
LinkedList list = null;
list = add(9, add(4, add(5, list)));
for(int i=1; list != null; i++)
{
System.out.println("Item number " + i + " : " + list.id);
list = list.next;
}
}
qui doit vous donner le résultat suivant :
Item number 1 : 9 Item number 2 : 4 Item number 3 : 5
Déposez la fichier Josephus.java :
Ajoutez à votre class Josephus la fonction
suivante :
static LinkedList getNext(LinkedList l)
qui retourne la référence de
l'élément suivant l dans la liste
chaînée. Si l'argument l est la
référence du dernier
élément d'une liste, alors la fonction
devra retourner null.
Vous devez tester votre implémentation en utilisant le code suivant (remplacez l'ancienne fonction main par celle-ci) :
public static void main(String[] args) {
LinkedList list = null;
LinkedList nextList;
list = add(9, add(4, add(5, list)));
nextList = getNext(list.next);
System.out.println("nextList item : " + nextList.id);
}
qui doit vous donner le résultat suivant :
nextList item : 5
Déposez la nouvelle version du fichier Josephus.java :
Pour être capable d'afficher facilement le contenu
d'une LinkedList à l'écran, ajoutez
à la class Josephus la fonction suivante :
static String toString(LinkedList l)
qui prend comme argument la référence d'une liste chaînée et retourne une String contenant la représentation textuelle de la liste chaînée, avec chaque élément de la liste séparé du suivant par un espace, mais sans espace après le dernier élément. Ainsi, si la liste chaînée contient les éléments 1-2-3, alors la fonction doit retourner :
"1 2 3"(sans les guillemets).
Aide : deux Strings se concatènent par l'opérateur
+. Ainsi, avec le code :
String s1 = "a"; String s2 = "b"; String s3 = s1+s2;
la variable s3 contiendra la valeur "ab"
(c'est-à-dire la valeur de s1
concaténée avec la valeur de s2).
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = null;
list = add(9, add(4, add(5, list)));
System.out.println(toString(list));
}
qui doit vous donner le résultat suivant :
9 4 5
Déposez la nouvelle version du fichier Josephus.java :
Ajoutez à votre class Josephus la fonction
suivante :
static int countElem(LinkedList l)
qui prend en argument la référence d'une liste chaînée et retourne un entier, à savoir le nombre d'éléments contenus dans cette liste.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = null;
int size;
list = add(9, add(4, add(5, list)));
size = countElem(list);
System.out.println("Length : " + size);
}
qui doit vous donner le résultat suivant :
Length : 3
Déposez la nouvelle version du fichier Josephus.java :
Cet exercice est indépendant des exercices suivants. Résoudre correctement cet exercice donnera des points, mais il est possible de résoudre les exercices suivants sans résoudre celui-ci.
Utiliser une fonction récursive ou itérative pour calculer le nombre d'éléments d'une liste chaînée nous force à "visiter" tous les éléments de la liste. Si nous avons n éléments dans la liste chaînée, alors nous visitons chacun de ces n éléments. En termes informatiques, on dit que la complexité de ce calcul est en O(n), c'est-à-dire en temps linéaire.
Nous pouvons faire mieux que cela : nous voulons être capables de connaître le nombre total d'éléments en visitant seulement le premier élément de la liste. En termes informatiques, ce que nous voulons obtenir est une complexité en O(1), c'est-à-dire en temps constant.
Ajoutez à votre class Josephus la fonction
suivante :
static int noElem(LinkedList l)
qui prend en argument la référence d'une liste chaînée et retourne un entier, à savoir le nombre d'éléments contenus dans cette liste.
Aide : Cette fonction ne devra être ni récursive
ni itérative. Pour cela, vous devez ajouter un
champ length dans votre class LinkedList et
modifier légèrement votre
fonction add (...).
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = null;
int size;
list = add(9, add(4, add(5, list)));
size = noElem(list);
System.out.println("Length : " + size);
}
qui doit vous donner le résultat suivant :
Length : 3
Déposez la nouvelle version du fichier Josephus.java :
Ajoutez à votre class Josephus la fonction
suivante :
static LinkedList initializeList(int n)
qui prend en argument un entier n et initialise (c'est-à-dire crée) une
LinkedList avec les
éléments [1 ; n] en utilisant
votre fonction add. La fonction retourne
la référence de
la LinkedList créée.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = initializeList(5);
System.out.println(toString(list));
}
qui doit vous donner le résultat suivant :
1 2 3 4 5
Déposez la nouvelle version du fichier Josephus.java :
Cet exercice est indépendant des exercices suivants. Résoudre correctement cet exercice donnera des points, mais il est possible de résoudre les exercices suivants sans résoudre celui-ci.
Ajoutez à votre class Josephus la fonction
suivante :
static LinkedList removeId(LinkedList l, int i)
qui retire de la LinkedList l
l'élément contenant l'identité i. La
fonction retourne la référence de la liste
résultante.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = initializeList(5);
System.out.println(toString(list));
list = removeId(list, 3);
list = removeId(list, 1);
list = removeId(list, 5);
System.out.println(toString(list));
}
qui doit vous donner le résultat suivant :
1 2 3 4 5 2 4
Déposez la nouvelle version du fichier Josephus.java :
Cet exercice est indépendant des exercices suivants. Résoudre correctement cet exercice donnera des points, mais il est possible de résoudre les exercices suivants sans résoudre celui-ci.
Ajoutez à votre class Josephus la fonction
suivante :
static LinkedList removePos(LinkedList l, int p)
qui retire de la LinkedList l son p-ième
élément. Le premier élément est
à la position 0 (zéro). La fonction retourne la
référence de la liste résultante.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = initializeList(5);
System.out.println(toString(list));
list = removePos(list, 2);
list = removePos(list, 0);
list = removePos(list, 2);
System.out.println(toString(list));
}
qui doit vous donner le résultat suivant :
1 2 3 4 5 2 4
Déposez la nouvelle version du fichier Josephus.java :
Ajoutez à votre class Josephus la fonction
suivante :
static LinkedList initializeListFromArray(String[] s)
qui prend comme argument un tableau de Strings où chaque
String contient l'identité d'un soldat, et
retourne la référence de
la LinkedList contenant ces soldats,
créée en utilisant votre
fonction add.
Aide : Pour convertir une String en un int,
Java fournit une fonction static int Integer.parseInt(String
s), qui s'utilise ainsi :
String s = "42"; int i = Integer.parseInt(s);
Nous aurons alors la valeur 42 affectée
à la variable i.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
String[] string = {"9","4","5"};
LinkedList list = initializeListFromArray(string);
System.out.println(toString(list));
}
qui doit vous donner le résultat suivant :
9 4 5
Déposez la nouvelle version du fichier Josephus.java :
Ajoutez à votre class Josephus la fonction
suivante :
static LinkedList flexibleInitialize(String[] s)
qui prend comme argument un tableau de Strings, et se comporte ainsi :
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
String[] s1 = {"9","4","5"};
String[] s2 = {"5"};
LinkedList l1 = flexibleInitialize(s1);
LinkedList l2 = flexibleInitialize(s2);
System.out.println(toString(l1));
System.out.println(toString(l2));
}
qui doit vous donner le résultat suivant :
9 4 5 1 2 3 4 5
Déposez la nouvelle version du fichier Josephus.java :
Puisque nos soldats sont disposés en cercle et qu'une structure LinkedList est une ligne, nous devons dans cet exercice nous occuper du bouclage des soldats : quand nous atteignons la fin d'une liste, nous devons recommencer à partir du début de la liste. Nous ne procéderons pas dans cet exercice à la transformation de la liste en liste circulaire, mais nous nous occuperons plutôt d'une gestion soigneuse des références.
Ajoutez à votre class Josephus la fonction
suivante :
static LinkedList getNextCircular(LinkedList head, LinkedList curr)
qui prend comme arguments la référence de la tête (premier élément) d'une liste, et la référence de l'élément (curr) pour lequel l'élément suivant est recherché, et retourne la référence de l'élément trouvé. Si l'élément courant est le dernier élément de la liste, alors l'élément suivant sera la tête de la liste. Ce principe est illustré par l'image ci-dessous.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = initializeList(5);
LinkedList nextList, startingList = list;
System.out.println(toString(list));
nextList = getNextCircular(list, list.next.next);
System.out.println(nextList.id);
while(list.next != null)
list = list.next;
nextList = getNextCircular(startingList, list);
System.out.println(nextList.id);
}
qui doit vous donner le résultat suivant :
1 2 3 4 5 4 1
Déposez la nouvelle version du fichier Josephus.java :
Ajoutez à votre class Josephus la fonction
suivante :
static LinkedList getMthElement(LinkedList head, LinkedList curr, int m)
qui prend comme arguments la référence de la tête d'une liste, et la référence de l'élément pour lequel le m-ième élément suivant est recherché, et retourne la référence de l'élément trouvé. Remarquez que la recherche du m-ième élément suivant peut nécessiter de gérer un bouclage, comme dans la question 3.1.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = initializeList(5);
LinkedList nextList;
System.out.println(toString(list));
nextList = getMthElement(list, list, 0);
System.out.println(nextList.id);
nextList = getMthElement(list, list.next.next, 1);
System.out.println(nextList.id);
nextList = getMthElement(list, list, 5);
System.out.println(nextList.id);
}
qui doit vous donner le résultat suivant :
1 2 3 4 5 1 4 1
Déposez la nouvelle version du fichier Josephus.java :
Nous sommes maintenant presque prêts pour tuer des soldats. Cependant, nous devons avoir un moyen de distinguer les soldats morts des vivants.
Ajoutez à votre class Josephus la fonction
suivante :
static void markElement(LinkedList l)
qui marque l'élément l d'une liste chaînée.
Ajoutez à votre class Josephus la fonction
suivante :
static boolean isMarked(LinkedList l)
qui retourne true si l'élément l d'une
liste chaînée est marqué, et false
sinon.
Pour cela, vous avez besoin d'ajouter un champ (de quel type?)
nommé marked dans
votre class LinkedList et de modifier
légèrement votre fonction add (...).
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = initializeList(5);
LinkedList dump = list;
while(dump != null)
{
if(!isMarked(dump))
System.out.print(dump.id + " ");
dump = dump.next;
}
System.out.println();
markElement(list.next);
dump = list;
while(dump != null)
{
if(!isMarked(dump))
System.out.print(dump.id + " ");
dump = dump.next;
}
System.out.println();
}
qui doit vous donner le résultat suivant :
1 2 3 4 5 1 3 4 5
Déposez la nouvelle version du fichier Josephus.java :
A chaque fois que nous "tuons" un soldat, nous voulons être sûrs que ce soldat n'est pas déjà mort. Dans notre cas, ceci peut être vérifié en déterminant si un élément de la liste, représentant un soldat, n'est pas déjà marqué.
Ajoutez à votre class Josephus la fonction
suivante :
static LinkedList nextUnmarked(LinkedList head, LinkedList curr)
qui prend comme arguments la référence de la tête d'une liste, et la référence de l'élément pour lequel le prochain élément non marqué est recherché, et qui retourne la référence de l'élément trouvé. Remarquez que la recherche de ce prochain élément non marqué peut nécessiter de gérer un bouclage, comme dans la question 3.1.
Si aucun élément non marqué n'est trouvé,
renvoyez null.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = initializeList(5);
System.out.println(toString(list));
markElement(list);
markElement(list.next.next.next);
markElement(list.next.next.next.next);
LinkedList search = nextUnmarked(list, list.next.next);
if(search != null)
System.out.println("found : " + search.id);
else
System.out.println("search is null");
markElement(list.next);
markElement(list.next.next);
search = nextUnmarked(list, list.next.next);
if(search != null)
System.out.println("found : " + search.id);
else
System.out.println("search is null");
}
qui doit vous donner le résultat suivant :
1 2 3 4 5 found : 2 search is null
Déposez la nouvelle version du fichier Josephus.java :
Ajoutez à votre class Josephus la fonction
suivante :
static LinkedList getMthUnmarkedElement(LinkedList head, LinkedList curr, int m)
qui prend comme arguments la référence de la tête d'une liste, et la référence de l'élément pour lequel le m-ième élément non marqué est recherché en ne comptant que les éléments non marqués (donc la recherche doit "traverser" m-1 éléments non marqués). Remarquez que la recherche du cet m-ième élément non marqué peut nécessiter de gérer un bouclage, comme dans la question 3.1.
Si aucun élément non marqué n'est trouvé,
renvoyez null.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = initializeList(5);
System.out.println(toString(list));
markElement(list);
markElement(list.next.next.next);
markElement(list.next.next.next.next);
LinkedList search = getMthUnmarkedElement(list, list, 3);
if(search != null)
System.out.println("found : " + search.id);
else
System.out.println("search is null");
markElement(list.next);
markElement(list.next.next);
search = getMthUnmarkedElement(list, list, 2);
if(search != null)
System.out.println("found : " + search.id);
else
System.out.println("search is null");
}
qui doit vous donner le résultat suivant :
1 2 3 4 5 found : 2 search is null
Déposez la nouvelle version du fichier Josephus.java :
Maintenant nous avons la base pour notre première tentative de résolution du problème de Josephus. Pour simplifier l'exécution du programme, nous allons tuer tous les soldats jusqu'au dernier, et considérer que ce dernier est justement celui qui se trouve en place sûre.
Exécuter votre programme doit générer une sortie comme celle ci-dessous :
4 7 2 6 3 1 5 8 The surviving soldier is 8
Ajoutez à votre class Josephus la fonction
suivante :
static void print(int[] ret)
qui prend comme argument un tableau d'entiers où :
et génère à l'écran une sortie (avec
System.out.print(...) et System.out.println(...)) comme indiqué
précédemment.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
int[] tab = {4, 7, 2, 6, 3, 1, 5, 8};
print(tab);
}
qui doit vous donner le résultat suivant :
4 7 2 6 3 1 5 8 The surviving soldier is 8
Déposez la nouvelle version du fichier Josephus.java :
Ça y est, le moment est venu de tuer les soldats et de résoudre le problème de Josephus : étant données une liste de soldats et une distance, quel soldat se trouve en "place sûre" ?
Ajoutez à votre class Josephus la fonction
suivante :
static int[] josephusSimple(LinkedList l, int distance)
qui prend comme arguments une liste chaînée initialisée de soldats et une distance entre le soldat tuant et le soldat à tuer, et qui retourne un tableau d'entiers contenant les identités des soldats dans l'ordre dans lequel ils sont tués.
Vous devez tester votre implémentation en utilisant le code suivant :
public static void main(String[] args) {
LinkedList list = initializeList(8);
int[] simulation = josephusSimple(list, 3);
print(simulation);
}
qui doit vous donner le résultat suivant :
4 7 2 6 3 1 5 8 The surviving soldier is 8
Déposez la nouvelle version du fichier Josephus.java :
Supprimez le contenu de votre fonction static void main(String[]
args) courante et remplacez ce contenu par un code qui permet
de lire les arguments d'une ligne de commande, de les interpréter
correctement, et qui résoud le problème de Josephus et
génère la sortie appropriée, tout ceci en
réutilisant les fonctions que vous avez
précédemment développées.
Concernant la lecture des arguments de la ligne de commande :
Déposez la nouvelle version du fichier Josephus.java :
Dans les exercices précédents, nous avons marqué les soldats d'une liste lorsqu'ils sont tués plutôt que de les supprimer de la liste. Ici, nous voulons résoudre le problème de Josephus comme avant, mais en supprimant cette fois les morts de la liste chaînée. Trivialement, le programme termine quand la liste est vide.
Ajoutez à votre class Josephus la fonction
suivante :
static int[] josephusRemove(LinkedList l, int distance)
qui est identique à la fonction développée pour la question 4.2, à la différence près que lorsqu'un soldat est tué, il est supprimé de la liste.
Déposez la nouvelle version du fichier Josephus.java :
Bien que nos soldats soient en cercle, nous les avons représentés par une simple liste chaînée, et nous avons dû traiter les cas de bouclage.
Dans cet exercice, nous allons utiliser une liste circulaire comme elle a été introduite dans le TD456, et quand un soldat sera "tué", il sera supprimé de la liste.
Créez une nouvelle class JosephusCircular qui
gère une liste circulaire : elle doit contenir les fonctions qui vous
semblent nécessaires pour implémenter la simulation du
problème de Josephus utilisant comme structure de
données une liste circulaire.
Déposez la nouvelle version du fichier Josephus.java :