Menu Close

Números como suma de sus dígitos

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. 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. 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)
    • 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.