2votos

El problema de Josefo en Haskell

por josejuan hace 5 años

El único coste problemático es el del cálculo de la posición para saltos entre desdichados grandes (ej. 10000 o así). Para valores pequeños, el número de desdichados puede ser escandalosamente grande (ej. 10^1000) y el cálculo se hace en pocos milisegundos. De hecho, da igual el número de desdichados, pues el coste viene a ser O(k + log n), por lo que el segundo sumando carece de importancia.

El problema de Josefo es el siguiente: n personas están en un círculo, y son ejecutadas en orden contando cada m personas; el que queda solo al final es el sobreviviente. Definir la función josefo tal que josefo(n,m) es el superviviente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
-- La forma trivial es ir eliminando uno a uno 
josefo' 1 _ = 1 
josefo' n s = (j + s - 1) `mod` n + 1 
              where j = josefo' (n - 1) s 
 
-- Eso requiere tantas operaciones como elementos, pero puede 
-- hacerse, si el número de pasos es menor al número de elementos, 
-- n / s eliminaciones simultáneamente. 
 
-- Como en cada iteración quitamos n/s elementos, el número de operaciones  
-- está acotado por arriba por: 
 
--      n / s / s / s ... = 1 
 
-- Es decir 
 
--       n ~ s^ops 
 
-- Es decir 
 
--       log n ~ ops log s 
 
-- Es decir 
 
--      ops = log n / log s 
 
-- Pero para el último paso debemos resolver `s`, quedando el coste total 
 
--      s + log n / log s 
 
-- Supongamos que tenemos implementada la función `josefo` tal que 
-- dado el número de elementos `n` (1, 2, ...) y el salto `s` (1, 2, ...) 
-- nos indica el que se salva. 
 
-- En una ronda, se van a matar a `k = n / s` elementos y por tanto se 
-- salvarán `n - k` elementos, el primero de los cuales es el 
-- siguiente al último eliminado. 
 
-- Así, tenemos la cosa de la siguiente forma: 
-- 
--   1, 2, ... (s1) ... (s2) ... ... (sK) ... 
-- 
 
-- Basta por tanto, mirar si se salva alguno del residuo o bien 
-- de los intervalados entre los desdichados. 
 
josefo n s = 
  if n <= s 
    then josefo' n s 
    else 
      if v <= r 
        then n - r + v 
        else s * k' + if r' == 0 then (-1) else r' 
  where (k, r) = n `divMod` s 
        v = josefo (n - k) s 
        (k', r') = (v - r) `divMod` (s - 1) 
                          
 
 
-- De este modo, podemos calcular rondas de asesinatos ridículamente grandes, 
-- en el que el mayor coste es el cálculo residual del tamaño del paso. 
main = do 
  (n:s:_) <- getArgs >>= return . map read 
  print $ josefo n s 
 
 
{- 
 
-- En mi siempre humilde Atom D510 
 
solveet$ time -f "%E, %M" ./josefo 10^1000 27 +RTS -K100M 
3774886680062446534659260680535595133141432149930447561814087436081419890534140740472921488326050815362498263005934872746502208265491955424107567698060435515505237672100963650858329145390101913927911066510793758502169959302653873885063939189990477743820572883122991669273112564271622388549071758835701950622223529450378334314461850367650150238292864292128922842042509064426162922612670408761015976332056604313581298455319048765645163801092179357297488386275258296152582085906350140505379237543548866604745580495008139421727312151114804228120929015557713523187956589760178969518706761376690369493532592838303220371450005288872732594272874503730249659673336997251049259293755816470269793494326416507167694646132002122731248580072430709191377195098803725635371800598217538362893410044356476874952594036310681050016425166531468381378445629729413845626883310580040815626813802194501843353071336801792265484483155871616112580053057233501292309449109278258127983084674905811477057589688688779864405884696193 
0:00.54, 31572 
 
solveet$ time -f "%E, %M" ./josefo 1000000000000000000000000 27 +RTS -K100M 
384399837388165502206825 
0:00.01, 2448 
 
solveet$ time -f "%E, %M" ./josefo 1000000000000000000000 12345 +RTS -K100M 
848792346224325036488 
0:02.71, 112620 
 
 
-} 
1 comentario
0votos

Escrito por josejuan hace 5 años

NOTA: josefo(10^10,2) es 2820130817 (no 672647169)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.