Le problème de Josephus

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.

0. Guide

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.

1. Une liste chaînée

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.

1.1 Implémentation basique d'une liste chaînée

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 :

1.2 Accéder à l'élément suivant

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 :

1.3 Représenter la liste chaînée comme une chaîne de caractères

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 :

1.4 Compter les éléments d'une liste chaînée

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 :

1.5 Nombre d'éléments sans récursion ou itération

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 :

1.6 Créer la liste

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 :

1.7 Chercher et retirer un élément par son identité

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 :

1.8 Chercher et retirer un élément par sa position

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 :

2. Les tableaux

2.1 Une autre façon d'initialiser une liste

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 :

2.2 Initialiser une liste chaînée par une ligne de commande

Ajoutez à votre class Josephus la fonction suivante :

	static LinkedList flexibleInitialize(String[] s)

qui prend comme argument un tableau de Strings, et se comporte ainsi :

  • si s est null, alors la fonction retourne null.
  • si le tableau contient exactement une String, alors elle sera convertie en un entier n qui sera utilisé pour créer une LinkedList de taille n.
  • si le tableau contient plus d'une String, alors celles-ci seront converties en entiers qui seront utilisés comme identités des soldats pour créer une LinkedList.
  • 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 :

    3. Le bouclage

    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.

    3.1 Récupérer l'élément suivant avec un éventuel bouclage

    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 :

    3.2 Récupérer le m-ième élément après la position courante

    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 :

    3.3 Marquer un élément dans une liste

    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 :

    3.4 Récupérer le prochain élément non marqué dans une liste

    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 :

    3.5 Récupérer le m-ième élément non marqué après l'élément courant

    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 :

    4 Mettre tout ça ensemble

    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.

    4.1 Générer la sortie

    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ù :

  • le premier élément du tableau contient le premier soldat tué,
  • le dernier élément du tableau contient le dernier soldat tué, c'est-à-dire le soldat situé en "place sûre".
  • 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 :

    4.2 Let's kill soldiers

    Ç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 :

    4.3 Ecrire la fonction main

    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 :

  • si moins de deux arguments sont donnés, alors le message d'erreur "Wrong number of arguments" est affiché l'écran et l'exécution du programme s'arrête à l'aide de l'instruction System.exit(0),
  • si au moins deux arguments sont donnés, alors le dernier correspond à la distance et le reste est utilisé comme argument de flexibleInitialize.
  • Déposez la nouvelle version du fichier Josephus.java :

    5. Supprimer les soldats plutôt que de les marquer

    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 :

    6. Les listes circulaires

    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 :