0votos

Suma de números monótonos crecientes en Haskell

por josejuan hace 6 años

Basta ver, que para un nuevo dígito que ponemos a la izquierda, podemos tener ya calculadas todas las sumas de las combinaciones de los dígitos que hemos ido agrupando a la derecha. Por ejemplo, si hemos acumulado 45, 56, 67, 78, tan sólo nos hace falta saber que son 4 nºs de 2 dígitos que suman 246; entonces, al añadir el 3, tendremos ahora 3 * 10^2 * 4 + 246 sin necesidad de ir generando y acumulando todas las combinaciones previas.

Calcular, de forma eficiente, la suma de todos los enteros positivos cuyos dígitos forman una sucesión estrictamente creciente.

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
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 -> [( 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  
                            )]  
  
-- La única forma de sumar el último dígito de la base es él mismo.  
suma 9 = [(1, 1, 9)]  
  
-- Las sumas parciales de 1, 2, ..., N dígitos se obtienen de las anteriores  
suma x = 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 (x + 1)  
        combina (p, n, q) = (p + 1, n, x * 10^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  
  
{--  
  
El algoritmo es polinómico en N-base porque a cada paso hay un máximo de N-1 grupos y como  
se realizan sólo N-1 pasos, tenemos coste O(N^2).  
  
--} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.