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
Una solución muy ineficiente
-- He utilizado 9^100 para representar Infinito