Descomposiciones de N como sumas de 1, 3 ó 4.
El número 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 ó 4:
5 = 1 + 1 + 1 + 1 + 1 5 = 1 + 1 + 3 5 = 1 + 3 + 1 5 = 3 + 1 + 1 5 = 1 + 4 5 = 4 + 1
Definir las funciones
descomposiciones :: Integer -> [[Integer]] nDescomposiciones :: Integer -> Integer
tales que
- (descomposiciones n) es la lista de las descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,
λ> descomposiciones1 4 [[4],[3,1],[1,3],[1,1,1,1]] λ> descomposiciones1 5 [[4,1],[1,4],[3,1,1],[1,3,1],[1,1,3],[1,1,1,1,1]] λ> descomposiciones1 6 [[3,3],[4,1,1],[1,4,1],[1,1,4],[3,1,1,1],[1,3,1,1],[1,1,3,1], [1,1,1,3],[1,1,1,1,1,1]]
- (nDescomposiciones n) es el número de descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,
nDescomposiciones 5 == 6 nDescomposiciones 10 == 64 nDescomposiciones 20 == 7921 nDescomposiciones 30 == 974169 length (show (nDescomposiciones (10^5))) == 20899
Nota: Se puede usar programación dinámica.
import Data.List (genericLength) import Data.Array -- 1ª definición de descomposiciones (espacios de estado) -- ====================================================== descomposiciones1 :: Integer -> [[Integer]] descomposiciones1 n = busca [inicial] where busca [] = [] busca (e:es) | esFinal n e = e : busca es | otherwise = busca (es ++ sucesores n e) -- Un estado es la lista de monedas usadas hasta ahora. type Estado = [Integer] -- inicial es el estado inicial del problema; es decir, cuando no se -- ha usado ninguna moneda. inicial :: Estado inicial = [] -- (esFinal n e) es verifica si e es un estado final del problema n. Por -- ejemplo, -- esFinal (8,5,3) (4,4,0) == True -- esFinal (8,5,3) (4,0,4) == False esFinal :: Integer -> Estado -> Bool esFinal n xs = sum xs == n -- (sucesores n e) es la lista de los sucesores del estado e en el -- problema n. Por ejemplo, -- sucesores (8,5,3) (8,0,0) == [(3,5,0),(5,0,3)] -- sucesores (8,5,3) (3,5,0) == [(0,5,3),(8,0,0),(3,2,3)] sucesores :: Integer -> Estado -> [Estado] sucesores n xs = [1:xs | 1 + k <= n] ++ [3:xs | 3 + k <= n] ++ [4:xs | 4 + k <= n] where k = sum xs -- 2ª definición de descomposiciones (espacios de estado) -- ====================================================== descomposiciones2 :: Integer -> [[Integer]] descomposiciones2 n = busca [inicial2 n] where busca [] = [] busca (e:es) | esFinal2 e = snd e : busca es | otherwise = busca (es ++ sucesores2 n e) -- Un estado es una par formado por la cantidad a conseguir y la lista -- de monedas usadas hasta ahora. type Estado2 = (Integer,[Integer]) -- (inicial2 n) es el estado inicial del problema; es decir, cuando no se -- ha usado ninguna moneda. inicial2 :: Integer -> Estado2 inicial2 n = (n,[]) -- (esFinal2 e) es verifica si e es un estado final del problema. Por -- ejemplo, -- esFinal (8,5,3) (4,4,0) == True -- esFinal (8,5,3) (4,0,4) == False esFinal2 :: Estado2 -> Bool esFinal2 (k,_) = k == 0 -- (sucesores2 n e) es la lista de los sucesores del estado e en el -- problema n. Por ejemplo, -- sucesores (8,5,3) (8,0,0) == [(3,5,0),(5,0,3)] -- sucesores (8,5,3) (3,5,0) == [(0,5,3),(8,0,0),(3,2,3)] sucesores2 :: Integer -> Estado2 -> [Estado2] sucesores2 n (k,xs) = [(k-1, 1:xs) | k >= 1] ++ [(k-3, 3:xs) | k >= 3] ++ [(k-4, 4:xs) | k >= 4] -- 3ª definición de descomposiciones -- ================================= descomposiciones3 :: Integer -> [[Integer]] descomposiciones3 0 = [[]] descomposiciones3 1 = [[1]] descomposiciones3 2 = [[1,1]] descomposiciones3 3 = [[1,1,1],[3]] descomposiciones3 n = [1:xs | xs <- descomposiciones3 (n-1)] ++ [3:xs | xs <- descomposiciones3 (n-3)] ++ [4:xs | xs <- descomposiciones3 (n-4)] -- 4ª definición de descomposiciones (dinámica) -- ============================================ descomposiciones4 :: Integer -> [[Integer]] descomposiciones4 n = v!n where v = array (0,n) [(i,aux v i) | i <- [0..n]] aux v 0 = [[]] aux v 1 = [[1]] aux v 2 = [[1,1]] aux v 3 = [[1,1,1],[3]] aux v k = map (1:) (v!(k-1)) ++ map (3:) (v!(k-3)) ++ map (4:) (v!(k-4)) -- 1ª definición de nDescomposiciones -- ================================== nDescomposiciones1 :: Integer -> Integer nDescomposiciones1 = genericLength . descomposiciones1 -- 2ª definición de nDescomposiciones -- ================================== nDescomposiciones2 :: Integer -> Integer nDescomposiciones2 = genericLength . descomposiciones2 -- 3ª definición de nDescomposiciones -- ================================== nDescomposiciones3 :: Integer -> Integer nDescomposiciones3 = genericLength . descomposiciones3 -- 4ª definición de nDescomposiciones -- ================================== nDescomposiciones4 :: Integer -> Integer nDescomposiciones4 = genericLength . descomposiciones4 -- 5ª definición de nDescomposiciones (dinámica) -- ============================================= nDescomposiciones5 :: Integer -> Integer nDescomposiciones5 n = v!n where v = array (0,n) [(i,aux v i) | i <- [0..n]] aux v 0 = 1 aux v 1 = 1 aux v 2 = 1 aux v 3 = 2 aux v k = v!(k-1) + v!(k-3) + v!(k-4) -- Comparación de eficiencia -- ========================= -- λ> nDescomposiciones1 20 -- 7921 -- (3.21 secs, 3,199,383,064 bytes) -- λ> nDescomposiciones2 20 -- 7921 -- (3.17 secs, 3,176,666,880 bytes) -- λ> nDescomposiciones3 20 -- 7921 -- (0.08 secs, 17,714,152 bytes) -- -- λ> nDescomposiciones3 27 -- 229970 -- (3.73 secs, 628,730,968 bytes) -- λ> nDescomposiciones4 27 -- 229970 -- (0.45 secs, 111,518,016 bytes) -- -- λ> nDescomposiciones4 30 -- 974169 -- (2.02 secs, 454,484,992 bytes) -- λ> nDescomposiciones5 30 -- 974169 -- (0.00 secs, 0 bytes) -- λ> nDescomposiciones2 30 -- 974169 -- (2.10 secs, 441,965,208 bytes) -- λ> nDescomposiciones3 30 -- 974169 -- (0.00 secs, 0 bytes) -- -- λ> length (show (nDescomposiciones5 (10^5))) -- 20899 -- (3.00 secs, 1,050,991,880 bytes)