Menor no expresable como suma
Definir la función
|
1 |
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,
|
1 2 3 4 5 |
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,
|
1 |
menorNoSuma [1..n] == 1 + sum [1..n] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
-- 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. |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>