Menu Close

Menor no expresable como suma

Definir la función

   menorNoSuma :: [Integer] -> Integer

tal que (menorNoSuma xs) es el menor número que no se puede escribir como suma de un subconjunto de xs, donde se supone que xs es un conjunto de números enteros positivos. Por ejemplo,

   menorNoSuma [6,1,2]    ==  4
   menorNoSuma [1,2,3,9]  ==  7
   menorNoSuma [5]        ==  1
   menorNoSuma [1..20]    ==  211
   menorNoSuma [1..10^6]  ==  500000500001

Comprobar con QuickCheck que para todo n,

   menorNoSuma [1..n] == 1 + sum [1..n]

Soluciones

-- 1ª definición
-- =============
 
import Data.List (sort, subsequences)
import Test.QuickCheck
 
menorNoSuma1 :: [Integer] -> Integer
menorNoSuma1 xs =
  head [n | n <- [1..], n `notElem` sumas xs]
 
-- (sumas xs) es la lista de las sumas de los subconjuntos de xs. Por ejemplo,
--    sumas [1,2,6]  ==  [0,1,2,3,6,7,8,9]
--    sumas [6,1,2]  ==  [0,6,1,7,2,8,3,9]
sumas :: [Integer] -> [Integer]
sumas xs = map sum (subsequences xs)
 
-- 2ª definición
-- =============
 
menorNoSuma2 :: [Integer] -> Integer
menorNoSuma2  = menorNoSumaOrd . reverse . sort 
 
-- (menorNoSumaOrd xs) es el menor número que no se puede escribir como
-- suma de un subconjunto de xs, donde xs es una lista de números
-- naturales ordenada de mayor a menor. Por ejemplo,
--    menorNoSumaOrd [6,2,1]  ==  4
menorNoSumaOrd [] = 1
menorNoSumaOrd (x:xs) | x > y     = y
                      | otherwise = y+x
    where y = menorNoSumaOrd xs
 
-- Comparación de eficiencia
-- =========================
 
--    λ> menorNoSuma1 [1..20]
--    211
--    (20.40 secs, 28,268,746,320 bytes)
--    λ> menorNoSuma2 [1..20]
--    211
--    (0.01 secs, 0 bytes)
 
-- Propiedad
-- =========
 
-- La propiedad es
prop_menorNoSuma :: (Positive Integer) -> Bool
prop_menorNoSuma (Positive n) =
    menorNoSuma2 [1..n] == 1 + sum [1..n]
 
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_menorNoSuma
--    +++ OK, passed 100 tests.
Medio

8 soluciones de “Menor no expresable como suma

  1. alvalvdom1

    import Data.List
    import Test.QuickCheck

    --Definición muy ineficiente.
     
    menorNoSuma :: [Integer] -> Integer
    menorNoSuma xs = head [x | x <- [1..], not (any (==x) (map sum (subsequences xs)))]
     
    prop_menorNoSuma :: Integer -> Bool
    prop_menorNoSuma n = menorNoSuma [1..n] == 1 + sum [1..n]
  2. blaruiher
    -- Definición ineficiente. 
     
    menorNoSuma :: [Integer] -> Integer
    menorNoSuma []= 0
    menorNoSuma xs = head [y | y <- [1..], notElem y ys]
                      where  ys = [sum  x | x <- subsequences xs]
     
    prop_menorNoSuma :: Integer -> Bool
    prop_menorNoSuma n = menorNoSuma [1..n] == 1 + sum [1..n]
  3. manvermor
    import Data.List
    import Test.QuickCheck
     
    menorNoSuma :: [Integer] -> Integer
    menorNoSuma xs | [1..genericLength xs] == xs = 1 + sum xs
                   | otherwise = head [ x | x <- [1..], notElem x (map sum (subsequences xs))]
     
    prop_menorNoSuma :: Integer -> Bool
    prop_menorNoSuma n = menorNoSuma [1..n] ==  1 + sum [1..n]
  4. erisan
    import Data.List
     
    menorNoSuma :: [Integer] -> Integer
    menorNoSuma xs =
        if (sort xs) `isPrefixOf` [1..]
        then 1 + sum xs
        else head [y | y <- [1..], y `notElem` (sumas xs)]
     
    sumas :: [Integer] -> [Integer]
    sumas xs = tail $ sort $ nub  $ map sum (subsequences xs)
     
    propiedad :: Integer -> Bool
    propiedad n = menorNoSuma [1..n] == 1 + sum [1..n]
  5. Chema Cortés
    import Data.List
    import Test.QuickCheck
     
    menorNoSuma :: [Integer] -> Integer
    menorNoSuma = aux . sortBy (flip compare)
        where aux [] = 1
              aux (x:xs) | x > m     = m
                         | otherwise = m + x
                    where m = aux xs
     
    prop_menorNoSuma :: Positive Integer -> Bool
    prop_menorNoSuma pn = menorNoSuma [1..n] == 1 + sum [1..n]
        where n = getPositive pn
    • Chema Cortés

      Una reformulación mejorada:

      menorNoSuma :: [Integer] -> Integer
      menorNoSuma xs = aux (sort xs) 1
          where aux [] m = m
                aux (y:ys) m | y > m     = m
                             | otherwise = aux ys (m + y)
  6. isrbelnun
    import Data.List
     
    sumas xs = nub (map sum (subsequences xs))
     
    menorNoSuma :: [Integer] -> Integer
    menorNoSuma xs = aux (sort (sumas xs)) [0..]
                     where aux [] (y:ys)     = y
                           aux (x:xs) (y:ys) | x == y    = aux xs ys
                                             | otherwise = y
    • isrbelnun
      prop_menorNoSuma :: Positive Integer -> Bool
      prop_menorNoSuma n = menorNoSuma [1..p] == 1 + sum [1..p]
                           where p = getPositive n

Escribe tu solución

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