Bonjour à tous ! Il m'a été demandé de coder un programme qui permet de simuler le problème de Josephe dont voici l'énoncé :

Des soldats juifs, cernés par des soldats romains, décident de former un cercle. En suivant la circonférence du cercle, un homme sur trois se fait tuer. Tant qu'il y a des soldats, la sélection continue. Le but est de trouver à quel endroit doit se tenir un soldat pour être le dernier. Josèphe, peu enthousiaste à l'idée de mourir, parvint à trouver l'endroit où se tenir. Quel est-il ?

Je vous laisse notamment une petite simulation histoire d'être sur que l'on ait compris le même énoncé ! 

https://www.geogebra.org/m/ExvvrBbR

Voici le code :

def superstes():
    cercle=[]
    for i in range (1,11):
        cercle.append(i)
    epee = 0
    for i in range (len(cercle)):
        while cercle[epee+1] == -1:
            epee +=1
        epee = (2+3*i)%len(cercle)
        cercle[epee] = -1
        
       
        
    return cercle
        
       
print superstes() 

Le programme marche pour les première itération (jusqu'à l’exécution du numéro 2). Toutefois j'ai du mal à exprimer une condition ou à voir comment il faudrait orienter ma réflexion pour prendre en compte les personnes déjà mortes (en -1 dans la liste) en effet pour l'exemple d'une liste de 10 personnes l'ordre d’exécution est 3,6,9,2 (jusque ici la boucle ne pose pas de soucis) l'épée passe au voisin vivant du 2 le plus proche or il faut prendre en compte que ce n'est pas 3 qui est déjà mort mais 4 et ceci je n'arrive pas à l'exprimer.

Merci par avance pour l'aide. 

Bonne soirée

-
Edité par FoxerStreet 19 mars 2019 à 22:12:23

BergiGnon a écrit:

Utilise l'index

La liste avec des numéros de 1 à n c'est bien, ensuite du peux faire del liste[i], puis i += 2, et si i est trop grand on reviens au début (congruence).

Ceci jusqu'à ce que la liste soit de longueur 1.

N'oubliez pas qu'il s'agit d'un problème mathématique. Et qu'il doit exister une formule pour le résoudre.
Il y a d'ailleurs la réponse sur la page du site dont est extrait l'énoncé.

J'ai bien sur pensé à cette méthode hein mais il semblerait que la solution générale n'existe que pour une personne sur 2 tuée. Quoi qu'il en soit le problème est résolu je vous met le code si vous voulez voir à quoi cela ressemble.

def superstes(n):
    """renvoie le couple gagnant pour le probleme de Josephe avec un nombre de personnes initial n""" 
    cercle=[]
    epee = 2   #definit l'index du detenteur de l'epee 
    for i in range (1,n+1):
        cercle.append(i)
    while len(cercle) != 2:
        del(cercle[epee])
        epee = (epee+2)%len(cercle)
    return cercle

Un petit oneliner pour le plaisir (solution récursive).

f = lambda n, k: (f(n - 1, k) + k) % n if n > 1 else 0

Edit: Correction.

-
Edité par Anonyme 22 mars 2019 à 9:38:01