Números como suma de sus dígitos

PorJosé A. Alonso 6-marzo-201925-abril-2021

El número 23 se puede escribir de 4 formas como suma de sus dígitos

   2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3
   2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3
   2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3
   2 + 3 + 3 + 3 + 3 + 3 + 3 + 3

2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3

2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3

2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3

2 + 3 + 3 + 3 + 3 + 3 + 3 + 3

La de menor número de sumando es la última, que tiene 8 sumandos.

Definir las funciones

   minimoSumandosDigitos        :: Integer -> Integer
   graficaMinimoSumandosDigitos :: Integer -> IO ()

1 2	minimoSumandosDigitos :: Integer -> Integer graficaMinimoSumandosDigitos :: Integer -> IO ()

tales que

(minimoSumandosDigitos n) es el menor número de dígitos de n cuya suma es n. Por ejemplo,

     minimoSumandosDigitos 23    ==  8
     minimoSumandosDigitos 232   ==  78
     minimoSumandosDigitos 2323  ==  775
     map minimoSumandosDigitos [10..20] == [10,11,6,5,5,3,6,5,4,3,10]

minimoSumandosDigitos 23 == 8

minimoSumandosDigitos 232 == 78

minimoSumandosDigitos 2323 == 775

map minimoSumandosDigitos [10..20] == [10,11,6,5,5,3,6,5,4,3,10]

(graficaMinimoSumandosDigitos n) dibuja la gráfica de (minimoSumandosDigitos k) par los k primeros números naturales. Por ejemplo, (graficaMinimoSumandosDigitos 300) dibuja

Soluciones

import Data.List (nub, genericLength, sort)
import Graphics.Gnuplot.Simple

minimoSumandosDigitos :: Integer -> Integer
minimoSumandosDigitos n =
  minimoSumandos (digitos n) n

-- (digitos n) es el conjunto de los dígitos no nulos de n. Por ejemplo,
--    digitos 2032  ==  [2,3]
digitos :: Integer -> [Integer]
digitos n =
  nub [read [c] | c <- show n, c /= '0']

-- (minimoSumandos xs n) es el menor número de elementos de la lista de
-- enteros positivos xs (con posibles repeticiones) cuya suma es n. Por
-- ejemplo, 
--    minimoSumandos [7,2,4] 11  ==  2
minimoSumandos :: [Integer] -> Integer -> Integer
minimoSumandos xs n =
  minimum (mapo genericLength (sumas xs n))

-- (sumas xs n) es la lista de elementos de la lista de enteros
-- positivos xs (con posibles repeticiones) cuya suma es n. Por ejemplo,  
--    sumas [7,2,4] 11  ==  [[7,2,2],[7,4]]
sumas :: [Integer] -> Integer -> [[Integer]]
sumas [] 0 = [[]]
sumas [] _ = []
sumas (x:xs) n
  | x <= n    = map (x:) (sumas (x:xs) (n-x)) ++ sumas xs n
  | otherwise = sumas xs n

graficaMinimoSumandosDigitos :: Integer -> IO ()
graficaMinimoSumandosDigitos n =
  plotList [ Key Nothing
           , PNG "Numero_como_suma_de_sus_digitos.png"
           ]
           [minimoSumandosDigitos k | k <- [0..n-1]]

import Data.List (nub, genericLength, sort)

import Graphics.Gnuplot.Simple

minimoSumandosDigitos :: Integer -> Integer

minimoSumandosDigitos n =

minimoSumandos (digitos n) n

-- (digitos n) es el conjunto de los dígitos no nulos de n. Por ejemplo,

-- digitos 2032 == [2,3]

digitos :: Integer -> [Integer]

digitos n =

nub [read [c] | c <- show n, c /= '0']

-- (minimoSumandos xs n) es el menor número de elementos de la lista de

-- enteros positivos xs (con posibles repeticiones) cuya suma es n. Por

-- ejemplo,

-- minimoSumandos [7,2,4] 11 == 2

minimoSumandos :: [Integer] -> Integer -> Integer

minimoSumandos xs n =

minimum (mapo genericLength (sumas xs n))

-- (sumas xs n) es la lista de elementos de la lista de enteros

-- positivos xs (con posibles repeticiones) cuya suma es n. Por ejemplo,

-- sumas [7,2,4] 11 == [[7,2,2],[7,4]]

sumas :: [Integer] -> Integer -> [[Integer]]

sumas [] 0 = [[]]

sumas [] _ = []

sumas (x:xs) n

| x <= n = map (x:) (sumas (x:xs) (n-x)) ++ sumas xs n

| otherwise = sumas xs n

graficaMinimoSumandosDigitos :: Integer -> IO ()

graficaMinimoSumandosDigitos n =

plotList [ Key Nothing

, PNG "Numero_como_suma_de_sus_digitos.png"

]

[minimoSumandosDigitos k | k <- [0..n-1]]

Pensamiento

Caminante, son tus huellas
el camino, y nada más;
caminante no hay camino,
se hace camino al andar.

Antonio Machado

3 Comentarios

Una solución muy ineficiente

import Control.Monad (replicateM)
import Data.List (nub)
minimoSumandosDigitos :: Integer -> Integer
minimoSumandosDigitos n = aux (div n (maxDig n))
  where aux a | elem n (posiblesSumas n a) = a
              | otherwise = aux (a+1)

maxDig :: Integer -> Integer
maxDig n = maximum (digitos n)

digitos :: Integer -> [Integer]
digitos n =  [read [x] | x <- show n]

posiblesSumas :: Integer -> Integer -> [Integer]
posiblesSumas n a = nub (map sum (replicateM (fromIntegral a) (digitos n)))

import Control.Monad (replicateM)

import Data.List (nub)

minimoSumandosDigitos :: Integer -> Integer

minimoSumandosDigitos n = aux (div n (maxDig n))

where aux a | elem n (posiblesSumas n a) = a

| otherwise = aux (a+1)

maxDig :: Integer -> Integer

maxDig n = maximum (digitos n)

digitos :: Integer -> [Integer]

digitos n = [read [x] | x <- show n]

posiblesSumas :: Integer -> Integer -> [Integer]

posiblesSumas n a = nub (map sum (replicateM (fromIntegral a) (digitos n)))

Responder

import System.Timeout
import Graphics.Gnuplot.Simple
import Data.List

minimoSumandosDigitos :: Integer -> Integer
minimoSumandosDigitos x | minimum(longitudesN x) < (9^100) =
                          minimum(longitudesN x)
                        | otherwise = (minimum xs) + (posicion (minimum xs) xs)
                          where xs = longitudesExtra2 x

posicion :: Integer -> [Integer] -> Integer
posicion x xs = fromIntegral (head (elemIndices x xs))

longitudesExtra2 :: Integer -> [Integer]
longitudesExtra2 x = [longitudesExtra x a |a <- [0..(div x(maximum(digitos x)))]]

longitudesExtra :: Integer -> Integer -> Integer  
longitudesExtra x a = minimum[longitudes y (init(digitos x)) n |
                       n <- [0..(maximum((init(digitos x))))]
                       ,y <- [x-(maximum(digitos x))*a]]

longitudesN :: Integer -> [Integer]
longitudesN x = [longitudes x (digitos x) n | n <- [0..(div x (maximum(digitos x))) ]]

longitudes :: Integer -> [Integer] -> Integer -> Integer
longitudes 0 [] n = 0
longitudes x [] n | x > 0 = 9^100
longitudes x xs n | maximum xs > x = longitudes x (init xs) n
                  | rem x (maximum xs) == 0 = div x (maximum xs)
                  | otherwise = (div x (maximum xs))-n + longitudes
                  ((rem x (maximum xs))+(n*(maximum xs))) (init xs) 0

digitos :: Integer -> [Integer]
digitos n = [ x | x <- (sort(nub [read [x] | x <- show n])) , x > 0]

graficaMinimoSumandosDigitos :: Integer -> IO ()
graficaMinimoSumandosDigitos n =
  plotList [Key Nothing] [minimoSumandosDigitos a | a <- [1..n]]

-- COMPARACIÓN DE EFICIENCIA CON OTRAS SOLUCIONES
--λ> timeout (10*10^6) (return $! minimoSumandosDigitos 2323)
--Just 775
--(0.03 secs, 31,581,384 bytes)
--λ> timeout (10*10^6) (return $! minimoSumandosDigitos2 2323)
--Nothing
--(10.33 secs, 7,476,223,216 bytes)

import System.Timeout

import Graphics.Gnuplot.Simple

import Data.List

minimoSumandosDigitos :: Integer -> Integer

minimoSumandosDigitos x | minimum(longitudesN x) < (9^100) =

minimum(longitudesN x)

| otherwise = (minimum xs) + (posicion (minimum xs) xs)

where xs = longitudesExtra2 x

posicion :: Integer -> [Integer] -> Integer

posicion x xs = fromIntegral (head (elemIndices x xs))

longitudesExtra2 :: Integer -> [Integer]

longitudesExtra2 x = [longitudesExtra x a |a <- [0..(div x(maximum(digitos x)))]]

longitudesExtra :: Integer -> Integer -> Integer

longitudesExtra x a = minimum[longitudes y (init(digitos x)) n |

n <- [0..(maximum((init(digitos x))))]

,y <- [x-(maximum(digitos x))*a]]

longitudesN :: Integer -> [Integer]

longitudesN x = [longitudes x (digitos x) n | n <- [0..(div x (maximum(digitos x))) ]]

longitudes :: Integer -> [Integer] -> Integer -> Integer

longitudes 0 [] n = 0

longitudes x [] n | x > 0 = 9^100

longitudes x xs n | maximum xs > x = longitudes x (init xs) n

| rem x (maximum xs) == 0 = div x (maximum xs)

| otherwise = (div x (maximum xs))-n + longitudes

((rem x (maximum xs))+(n*(maximum xs))) (init xs) 0

digitos :: Integer -> [Integer]

digitos n = [ x | x <- (sort(nub [read [x] | x <- show n])) , x > 0]

graficaMinimoSumandosDigitos :: Integer -> IO ()

graficaMinimoSumandosDigitos n =

plotList [Key Nothing] [minimoSumandosDigitos a | a <- [1..n]]

-- COMPARACIÓN DE EFICIENCIA CON OTRAS SOLUCIONES

--λ> timeout (10*10^6) (return $! minimoSumandosDigitos 2323)

--Just 775

--(0.03 secs, 31,581,384 bytes)

--λ> timeout (10*10^6) (return $! minimoSumandosDigitos2 2323)

--Nothing

--(10.33 secs, 7,476,223,216 bytes)

Responder

javmarcha1 dice:

11-marzo-2019 a las 21:48

Haskell

-- He utilizado 9^100 para representar Infinito

1

-- He utilizado 9^100 para representar Infinito

Responder

Números como suma de sus dígitos

Soluciones

Pensamiento

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico