Le problème de Josèphe

INFOS COMPLÈTES SUR LA PAGE WIKIPÉDIA

En mathématiques et en informatique, le problème de (Flavius) Josèphe ou problème de Caligula est un problème d'élimination, conduisant à l'obtention d'un unique survivant.

Il a été énoncé sous différentes formes, mais sa première formulation est due à Flavius Josèphe.

Problème originel⚓︎

Quarante et un soldats juifs (dont Flavius Josèphe), cernés par des soldats romains, décident de se suicider. Ils se mettent en [[cercle]], et un premier soldat est choisi au hasard pour être exécuté ; puis le troisième à partir de sa gauche (ou droite) est exécuté. Tant qu'il y a des soldats, la sélection continue de la même façon. Le but est de trouver à quelle place doit se tenir un soldat pour être le dernier. Josèphe, peu enthousiaste à l'idée de mourir, parvint à trouver cette place. Quelle est-elle ?

Problème général⚓︎

Les soldats sont au nombre de n, numérotés de 1 à n ; les premiers soldats éliminés sont ceux dont le numéro est multiple d'un entier k ⩾ 2 ( k = 3 dans le problème originel) ; après un tour, les éliminations de k en k des soldats restants se poursuivent jusqu'à ce qu'il n'en reste qu'un. On demande le numéro \(J_k( n )\)

Voici par exemple, pour n = 10 , k = 3, les différents ordres d'élimination des soldats :

i	1	2	3	4	5	6	7	8	9	10
ordre d'élimination	6	4	1	10	8	2	5	7	3	9

Le but est d'écrire un programme permettant de résoudre le problème de Joséphus en révisant les listes de Python.

On représente un cercle de n soldats par la liste [1,2,...,n]

1)

Écrire une liste par compréhension qui renvoie la liste [1,2,....,n]

2) Compléter le code ci-dessous