TP1 IPT : Flavius Josèphe

Python
from functools import reduce
 
 
 
def flaviusPyth2(nSinistre,nbPers):
    """Version directement pythonesque du problème de Flavius"""
    surv = ["No " + str(k) for k in range(1,nbPers + 1)]
    noVictime = 0
    while len(surv) > 1:
        noVictime = (noVictime + nSinistre - 1) % len(surv)
        print(surv.pop(noVictime))
    return("Et le survivant est le " + surv[0])
 
def flaviusPyth(nSinistre, nbPers) :
    vivant, mort = 1, 0
    cercle = [ vivant ] * nbPers 
    noVictime = 0
    for nbVictimes in range(nbPers) :
        avance = 0
        while avance < 7 :
            noVictime = (noVictime + 1) % nbPers
            avance += cercle[noVictime]
        cercle[noVictime] = mort
        print(noVictime)
    print("Et le survivant est le No " + str(noVictime))
 
 
 
def flaviusPyth3(nSinistre,nbPers):
    """ Par pliage, avec X = (surv,noVictime)"""
    def reduit(X,NbTues):
        print(X[0].pop(X[1]))
        return (X[0], (X[1] + nSinistre - 1) % (nbPers - NbTues))
    return reduce(reduit, range(1,nbPers),  ( ["No " + str(k) for k in range(1,nbPers + 1)],nSinistre - 1) )

Pas de réelle différence entre les versions récursives et impératives mais la version «manuelle» est plus dix fois plus lente:

Python
In [32]: %timeit flaviusPyth2(7,400)
1000 loops, best of 3: 222 µs per loop
 
In [33]: %timeit flaviusPyth(7,400)
1000 loops, best of 3: 1.69 ms per loop
 
In [34]: %timeit flaviusPyth3(7,400)
10000 loops, best of 3: 170 µs per loop

Le déroulement de l'exécution[/url]:


Avec caml version light, on écrit la même chose:

OCaml
let rec supprime i liste = match liste with
    []    -> raise (Failure "Empty list")
   |t::q  -> match i with
               0 -> q
             | _ -> t:: (supprime (i - 1) q);;
 
let rec numero i liste = match liste with
    []    -> raise (Failure "Empty list")
   |t::q  -> match i with
               0 -> t
             | _ -> numero (i - 1) q;;
  
let rec fold_left loi acc = function
  | []          -> acc
  | tete::queue -> fold_left loi (loi acc tete) queue;;
  
let rec construit k acc = match k with
    0 -> acc
  | _ -> construit (k-1) (k::acc);;
  
let soldats n =
  map  (fun x -> "No" ^ (string_of_int x) ^ "\n ") (construit n []);;
 
let flavius nSinistre nbPers =
  fold_left  (fun (surv,noVict) nbTues -> print_string (numero noVict surv);
                   (supprime noVict surv,  ((noVict + nSinistre - 1) mod (nbPers - nbTues))))
                  (soldats nbPers, nSinistre - 1)
                  (construit (nbPers - 1) []);;

Qui donne:

OCaml
#flavius 6 20;;
No6
 No12
 No18
 No4
 No11
 No19
 No7
 No15
 No3
 No14
 No5
 No17
 No10
 No8
 No2
 No9
 No16
 No13
 No1
 - : string list * int = ["No20\n "], 0

Et pour le fun une version Haskell:

Haskell
supprime _ []    = error "liste vide"
supprime 0 (t:q) = q
supprime i (t:q) = t:(supprime (i-1) q)
 
soldats n = ["No" ++ (show k) ++ " " | k <- [1 .. n]]
 
flavius nSinistre nbPers =
    let massacre ( surv, noVict ) nbTues =
            ( supprime noVict surv,  ((noVict + nSinistre - 1) `mod` (nbPers - nbTues)) )
    in head $ fst $ foldl massacre ( soldats nbPers, nSinistre - 1 ) [1.. (nbPers - 1)]

qui donne:

Haskell
λ> flavius 6 20
"No20 "

Tags

courtesy of webmatter.de