LE PROBLEME DE JOSEPHE

Josèphe Flavius était un célèbre historien du premier siècle. Durant une guerre il fut pris au piège dans une grotte 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 Josèphe 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 Josèphe.

Le but de ce projet est d'écrire un programme qui simule une version généralisée de ce problème avec $n$ soldats (Josèphe inclus), où il faut retirer les soldats un par un jusqu'à ce qu'il n'y en ait plus qu'un.

Travail :

A faire

• Par groupe de deux ou trois, vous devez écrire un progamme python qui simule cette situation pour un nombre quelconque de soldats et qui identifie le soldat survivant
• La structure de données à utiliser est la liste chaînée.
• On pourra améliorer le rendu de la simulation en affichant des étapes intermédiares(soldats tués, soldats restants, etc...)

A rendre

• Un fichier individuel au format .pdf de 5 pages maximum contenant un rapport avec :
  • La répartition des tâches dans le groupe.
  • Les difficultés rencontrées et les solutions proposées.
  • L'explication d'une partie de code que vous aurez plus spécifiquement travaillé.