1votos

Problema de las Olimpiadas rusas en Haskell

por josejuan hace 3 años

Aunque el problema deja claro que se trata de los números en base 10, como dice Fernando, puede generalizarse a cualquier base. Esta implementación en Haskell es la más eficiente (asintóticamente es, al menos, exponencialmente más rápida) de todas las otras soluciones (salvo omisión). Claro que no importa mucho si tenemos O(log n) que O(log log n)... Pero por optimizar que no quede :P

Calcular el elemento n-ésimo de la sucesión 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, ...

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
-- longitud de: {1..9}{10..99}{100..999}... donde g=1,2,... grupo g-ésimo 
sgroup b g = (b^g * (g * (b - 1) - 1) + 1) `div` (b - 1) 
 
-- busca el grupo en el que está el dígito n-ésimo, n=1,2,3,... 
fgroup b n = u 1 
             where u j = if sgroup b j < n then u (j + j) else d 0 j 
                   d i j = if i == j then i else m' 
                           where m = (i + j) `div` 2 
                                 m' = if sgroup b m < n then d (m + 1) j else d i m 
 
 
-- devuelve el nº en el que está el dígito y su posición (0,1,... empezando en el LSD) 
dgroup b n = (b^(g - 1) + p, g - r - 1) 
             where g = fgroup b n 
                   (p, r) = (n - sgroup b (g - 1) - 1) `divMod` g 
 
-- obtiene el dígito en cuestión 
digit b = d . dgroup b 
        where d (z, 0) = z `mod` b 
              d (z, n) = d (z `div` b, n - 1) 
 
 
 
 
 
 
 
 
 
{- 
 
  Por ejemplo: 
   
  *Main> digit 10 206788 
  *Main> digit 10 (10^(10^5)) 
   
-} 
1 comentario
0votos

Escrito por AverageUser hace 4 meses

Mirando soluciones antiguas, esta me parece mejor que las anteriores y parece que nadie se molesto en leerla, a mi me parece genial.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.