Menu Close

Etiqueta: Dinámica

Descomposiciones con sumandos 1 ó 2

Definir la funciones

   sumas  :: Int -> [[Int]]
   nSumas :: Int -> Integer

tales que

  • (sumas n) es la lista de las descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,
      sumas 1            ==  [[1]]
      sumas 2            ==  [[1,1],[2]]
      sumas 3            ==  [[1,1,1],[1,2],[2,1]]
      sumas 4            ==  [[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]]
      length (sumas 26)  ==  196418
      length (sumas 33)  ==  5702887
  • (nSumas n) es el número de descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,
      nSumas 4                      ==  5
      nSumas 123                    ==  36726740705505779255899443
      length (show (nSumas 123456)) ==  25801

Soluciones

import Data.List (genericIndex, genericLength)
 
-- 1ª definición de sumas
sumas1 :: Int -> [[Int]]
sumas1 0 = [[]]
sumas1 1 = [[1]]
sumas1 n = [1:xs | xs <- sumas1 (n-1)] ++ [2:xs | xs <- sumas1 (n-2)]
 
-- 2ª definición de sumas
sumas2 :: Int -> [[Int]]
sumas2 n = aux !! n
    where aux     = [[]] : [[1]] : zipWith f (tail aux) aux
          f xs ys = map (1:) xs ++ map (2:) ys
 
-- Comparación de las definiciones e sumas
--    ghci> length (sumas 25)
--    121393
--    (1.84 secs, 378307888 bytes)
--    ghci> length (sumas 26)
--    196418
--    (3.09 secs, 623707712 bytes)
--    ghci> length (sumas2 25)
--    121393
--    (0.11 secs, 39984864 bytes)
--    ghci> length (sumas2 26)
--    196418
--    (0.17 secs, 63880032 bytes)
 
-- La segunda definición es más eficiente y es la que usaremos en lo
-- sucesivo:
sumas :: Int -> [[Int]]
sumas = sumas2
 
-- 1ª definición de nSumas
nSumas1 :: Int -> Integer
nSumas1 = genericLength . sumas2
 
-- 2ª definición de nSumas
nSumas2 :: Int -> Integer
nSumas2 0 = 1
nSumas2 1 = 1
nSumas2 n = nSumas2 (n-1) + nSumas2 (n-2)
 
-- 3ª definición de nSumas
nSumas3 :: Int -> Integer
nSumas3 n = aux `genericIndex` n
    where aux = 1 : 1 : zipWith (+) aux (tail aux) 
 
-- Comparación de las definiciones de nSumas
--    ghci> nSumas1 33
--    5702887
--    (4.33 secs, 1831610456 bytes)
--    ghci> nSumas2 33
--    5702887
--    (12.33 secs, 1871308192 bytes)
--    ghci> nSumas3 33
--    5702887
--    (0.01 secs, 998704 bytes)
 
-- Nota. El valor de (nSumas n) es el n-ésimo término de la sucesión de
-- Fibonacci 1, 1, 2, 3, 5, 8, ...