Menu Close

Descomposición de N en K sumandos pares distintos

Definir las funciones

   sumas  :: Integer -> Integer -> [[Integer]]
   esSuma :: Integer -> Integer -> Bool

tales que

  • (sumas n k) es la lista de las descomposiones de n en k sumandos pares y distintos. Por ejemplo,
     sumas 16 3  ==  [[2,4,10],[2,6,8]]
     sumas 18 4  ==  []
  • (esSuma n k) se verifica si n se puede escribir como suma de k sumandos pares y distintos. Por ejemplo,
     esSuma 16 3  ==  True
     esSuma 18 4  ==  False
     esSuma (10^5000) (10^7)  ==  True
     esSuma (11^5000) (10^7)  ==  False

Soluciones

import Test.QuickCheck
 
sumas :: Integer -> Integer -> [[Integer]]
sumas n k = sumasLista n k [2,4..n]
 
-- (sumasLista n k xs) es la lista de las descomposiciones de n como k
-- elementos de xs (cada uno una vez como máximo). Por ejemplo,
--    sumasLista 16 3 [2,4..15]  ==  [[2,4,10],[2,6,8]]
--    sumasLista 18 4 [2,4..15]  ==  []
sumasLista :: Integer -> Integer -> [Integer] -> [[Integer]]
sumasLista _ _ [] = []
sumasLista n 1 xs
  | n `elem` xs = [[n]]
  | otherwise   = []
sumasLista n k (x:xs)
  | x > n     = []
  | otherwise = [x:ys | ys <- sumasLista (n-x) (k-1) xs] ++
                sumasLista n k xs
 
-- 1ª definición de esSuma
-- =======================
 
esSuma :: Integer -> Integer -> Bool
esSuma n k = not (null (sumas n k))
 
-- 2ª definición de esSuma
-- =======================
 
-- Se observan las siguientes propiedades:
-- 1. Si n es impar, no se puede escribir como suma de pares.
-- 2. El menor número que se puede escribir como suma de k sumandos
--    impares distintos es 2 * sum [1..k] y su descomposición es
--    [2,4..2*k] (es decir, map (*2) [1..k]).
-- 3. Si n es un número par mayor o igual que (2 * sum [1..k])
--    entonces se puede escribir como suma de k sumandos pares distintos;
--    en efecto,
--       x = 2 + 4 + ··· + 2*(k-1) + (x - (2 + 4 + ··· + 2*(k-1))
 
esSuma2 :: Integer -> Integer -> Bool
esSuma2 n k
  | odd n               = False
  | 2 * sum [1..k] <= n = True
  | otherwise           = False
 
-- 3ª definición de esSuma
-- =======================
 
esSuma3 :: Integer -> Integer -> Bool
esSuma3 n k
  | odd n            = False
  | k * (k + 1) <= n = True
  | otherwise        = False
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_equiv_esSuma :: Integer -> Integer -> Property
prop_equiv_esSuma n k =
  n > 0 && k > 0 ==>
  all (== (esSuma3 n k)) [esSuma n k, esSuma2 n k]
 
-- La comprobación es
--    λ> quickCheck prop_equiv_esSuma
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> esSuma 200 20
--    False
--    (6.12 secs, 3,079,059,560 bytes)
--    λ> esSuma2 200 20
--    False
--    (0.00 secs, 102,800 bytes)
--    λ> esSuma3 200 20
--    False
--    (0.01 secs, 102,760 bytes)
--
--    λ> esSuma2 (10^5000) (10^7)
--    True
--    (2.55 secs, 1,612,412,664 bytes)
--    λ> esSuma3 (10^5000) (10^7)
--    True
--    (0.03 secs, 109,200 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

3 soluciones de “Descomposición de N en K sumandos pares distintos

  1. Mercedes Vega Gallo
    import Data.List
     
    sumas  :: Integer -> Integer -> [[Integer]]
    sumas n k = sumlength n k (subsequences (listapares n))
     
    -- La función "sumlength n k xs" nos devuelve una lista formada por listas cuya longitud
    -- es k y cuya suma de elementos es n.
     
    sumlength :: Integer -> Integer -> [[Integer]]-> [[Integer]]
    sumlength n k [] = []
    sumlength n k (xs:xss) |sum xs == n && length xs == (fromIntegral k) = xs: (sumlength n k xss)
                           |otherwise = sumlength n k xss
     
    -- La función "listapares x" nos devuelve la lista de números pares del 1 hasta
    -- el x.
     
    listapares :: Integer -> [Integer]
    listapares x = [y | y<- [1..x], mod y 2 == 0]
     
     
    esSuma :: Integer -> Integer -> Bool
    esSuma n k  |(sumas n k) == [] = False
                |otherwise = True
    • Mercedes Vega Gallo
      -- Una solución más breve:
       
      import Data.List
       
      sumas  :: Integer -> Integer -> [[Integer]]
      sumas n k = filter p (subsequences (listapares n))
                   where p xs = length xs == (fromIntegral k) && sum xs == n
                         listapares x = [y | y<- [1..x], mod y 2 == 0]
       
       
      esSuma :: Integer -> Integer -> Bool
      esSuma n k  |sumas n k == [] = False
                  |otherwise = True
  2. Rubén Muñoz Mkrtchian
    sumas :: Integer -> Integer -> [[Integer]]
    sumas n k = aux n m m
      where m = fromIntegral k
     
    -- aux n m k funciona al igual que sumas n k; sin embargo, al introducir el
    -- factor m en esta función nos podemos asegurar de que si el elemento que
    -- ocupa la posición i en una lista de k elementos con suma n es un determinado
    -- número par, entonces el elemento de la posición (i+1) debe ser, como mínimo,
    -- el número par siguiente al anterior.
     
    aux :: Integer -> Int -> Int -> [[Integer]]
    aux n m k
      | k <= 0 = [[]]
      | k == 1 = [[n]]
      | odd n  = [[]]
      | otherwise = filter creciente (concat
          [map (x:) (aux (n-x) m (k-1)) | x <- drop (m-k) [2,4..p]])
            where p = div n q - div q 2
                  q = fromIntegral k
     
    -- creciente xs se verifica si xs es estrictamente creciente. Con esta función
    -- podemos eliminar las listas de k elementos con suma n que no son válidas de
    -- acuerdo a la definición de sumas n k.
     
    creciente :: [Integer] -> Bool
    creciente []  = True
    creciente [x] = True
    creciente (x:y:zs) = x < y && creciente (y:zs)
     
    esSuma :: Integer -> Integer -> Bool
    esSuma n k = not (null (sumas n k))

Leave a Reply

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