Menu Close

Números como suma de sus dígitos

José A. Alonso,

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

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

Definir las funciones

   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]
  • (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]]

Pensamiento

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

Antonio Machado

Avanzado
, , , , , , , , , ,

3 soluciones de “Números como suma de sus dígitos”

  1. Responder
    frahidzam

    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)))
  2. Responder
    javmarcha1 
    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 
      -- He utilizado 9^100 para representar Infinito

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.