0votos

Suma de números monótonos crecientes (II) en Haskell

por josejuan hace 6 años

Es exactamente el mismo algoritmo, únicamente se ha generalizado la función para que en lugar de ser siempre base 10, pueda ser base N. Para una base de 300 le lleva a un Intel Atom 3,53 segundos calcular la suma de todos los números.

En el anterior desafío se pidió obtener un algoritmo polinómico y se probó que en base 10 la suma vale 320214537. Ahora se pide utilizar dicho algoritmo para calcular las sumas para las bases 60 y 300.

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
import Data.List 
import Prelude hiding (fst, snd) 
 
-- Calcula las sumas acumuladas agrupadas por el número de digitos de la suma obtenida   
suma :: Integral n => n -> n -> [( Int -- Número de dígitos de los números totalizados en esta suma parcial   
                                 , n   -- Número de elementos totalizados en esta suma parcial   
                                 , n   -- Suma parcial de todos los números totalizados   
                                 )]   
 
suma base x = if x == base - 1 
              then 
                -- La única forma de sumar el último dígito de la base es él mismo.   
                [(1, 1, base - 1)] 
              else 
                -- Las sumas parciales de 1, 2, ..., N dígitos se obtienen de las anteriores   
                map agrega $                                             -- Totalizando   
                groupBy ((.fst).(==).fst) $ sortBy ((.fst).compare.fst)  -- Por grupos de dígitos   
                $ (1, 1, x):suma' ++                                     -- Del nuevo dígito, los anteriores   
                   map combina suma'                                     -- y los nuevos de combinar ambos.   
  where suma' = suma base (x + 1)   
        combina (p, n, q) = (p + 1, n, x * base^p * n + q)   
        agrega rs = (fst $ head rs, sum $ map snd rs, sum $ map thd rs)   
   
 
-- Calcula la suma buscada   
totaliza :: Integral n => [(Int, n, n)] -> n   
totaliza = sum . map thd   
 
   
-- Ternas   
fst (x, _, _) = x   
snd (_, x, _) = x   
thd (_, _, x) = x 
 
{-- 
 
 
-- Calculando el valor solicitado (sin compilar) 
 
*Main> totaliza $ suma 60 1 
37851759964142317188220652810504133160594013322867572968340450725151771862671696140624970292053615487705 
(0.12 secs, 12650824 bytes) 
 
 
-- Calculando para la base 300 
 
*Main> totaliza $ suma 300 1 
4155337482672932072576213220257886445617384918595385732293021247952681918408914569676559298259529669247480342002738441707576599070655889002533629753931100336633443759372467910593665126976985901764826693333351675722893247453010795426694058271454775778791892549775590113952023696002297895871144414538598594840661249819216255672087798550193951009397683845943815142576708460798058897997846718340702751923211906314342765847689263731410764741226185950120549737480717649790687033813067625935018854206673804236018820464885674381032160264373783347583363973804185446955601742582048580305879820303624788182395990389414454054553131720826191526105906639133261924552129654964336151676723792185550889430739280423949328952718565546911248620705970745044025 
(3.53 secs, 371096008 bytes) 
 
 
--} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.