LE PROBLEME DE FLAVIUS JOSEPHE

1. Le problème :

Quarante et un soldats juifs (dont Flavius Josèphe), cernés par des soldats romains, doivent être exécuté. 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 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 ?

2. Comment je l'ai abordé :

J'ai tout d'abord pris une feuille et fait l'algorithme avec un nombre de 7 soldats et un pas de 3 pour le prochain exécuté. J'ai commencer par l'étude sur feuille pour comparer mes résultat avec ceux du programme. Car ma deuxième partie de projet à été la conception de mon programme python. J'ai choisis d'utiliser une liste chainée circulaire afin de refaire le tour du cercle autant de fois que possible. J'ai choisis de différencier la création de la liste et la recherche du soldat qui sera évincé, dans deux fonction différentes afin de commencer par la fonction de recherche pour que la liste se face plus facilement et raidement par la suite. Après avoir terminer l'écriture du programme je l'ai lancé et là, je me suis rendu compte que ça ne me retrouver pas le bon soldat. Donc j'ai fait pleins de petits test avec des print (voir 3.) et au bout d'un petit moment (un peu long..) j'ai trouvé que l'erreur venait de l'indice que je prenait au départ. Je mettait ma variable indice au départ sur le soldat 1 (indice = 0) en pensant que c'était le soldat exécuté au début. Je suis donc parti du soldat 0 (indice = -1), j'ai fait comme si il venait d'être "pop" comme dans la fin de ma fonction et que la boucle while recommencer. J'ai donc retrouvé la bonne place. J'ai fait d'autres tests avec d'autre valeurs de n mais aussi de p et à chaque fois j'ai retrouvé la bonne valeur.

3. Mon code :

from listes_chainees2 import *

def liste(n):
    '''prend en argument un nombre entier n
    renvoi un liste le grandeur n-1 avec des valeur allant de 1 jusqu'à n-1'''
    list = []
    for x in range (1,n):
        list.append(x)
    return list

def flavius(n,p):
    '''prend en argument un nombre de soldats n et un pas p
    renvoie la place du survivant'''
    cercle = liste(n)#création du cercle avec l'appel de la fonction liste
    #print(cercle)
    indice = -1 #indice incrémenter au premier soldat mort qui n'est donc pas dans la list donc -1
    while n>2 : #boucle pour qu'il ne reste qu'un seul soldat à la fin
        #print('taille tableau :', len(cercle))
        #print('indice depart :', indice)
        for x in range(0,p):#boucle pour tuer la p ème en partant de la gauche du soldat éxecuté
            if indice >= len(cercle)-1 :
                indice = 0
                #print(indice)
            else :
                indice += 1
                #print(indice)
        cercle.pop(indice)#éxecution du soldat
        indice -= 1
        n-=1
        #print(cercle)
    return 'La bonne place pour survivre est la ' + str(cercle[0]) + ' en partant de la gauche du soldat exécuté.'


##tests##
print(flavius(4,1))
print(flavius(4,2))
print(flavius(7,3))
print(flavius(7,1))
print(flavius(41,3))

			

4. Conclusion :

Grâce à ce programme j'ai pu trouver que la bonne place pour Flavius est la 28ème place.