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 "