Mayor prefijo con suma acotada
Definir la función
|
1 |
mayorPrefijoAcotado :: [Int] -> Int -> [Int] |
tal que (mayorPrefijoAcotado xs y) es el mayor prefijo de la lista de los números enteros positivos xs cuya suma es menor o igual que y. Por ejemplo,
|
1 2 3 4 |
mayorPrefijoAcotado [45,30,55,20,80,20] 75 == [45,30] mayorPrefijoAcotado [45,30,55,20,80,20] 140 == [45,30,55] mayorPrefijoAcotado [45,30,55,20,80,20] 180 == [45,30,55,20] length (mayorPrefijoAcotado (repeat 1) (8*10^6)) == 8000000 |
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
import Data.List (inits) -- 1ª solución -- =========== mayorPrefijoAcotado :: [Int] -> Int -> [Int] mayorPrefijoAcotado [] _ = [] mayorPrefijoAcotado (x:xs) y | x > y = [] | otherwise = x : mayorPrefijoAcotado xs (y-x) -- 2ª solución -- =========== mayorPrefijoAcotado2 :: [Int] -> Int -> [Int] mayorPrefijoAcotado2 xs y = take (longitudMayorPrefijoAcotado2 xs y) xs longitudMayorPrefijoAcotado2 :: [Int] -> Int -> Int longitudMayorPrefijoAcotado2 xs y = length (takeWhile (<=y) (map sum (inits xs))) - 1 -- 3ª solución -- =========== mayorPrefijoAcotado3 :: [Int] -> Int -> [Int] mayorPrefijoAcotado3 xs y = take (longitudMayorPrefijoAcotado3 xs y) xs longitudMayorPrefijoAcotado3 :: [Int] -> Int -> Int longitudMayorPrefijoAcotado3 xs y = length (takeWhile (<= y) (scanl1 (+) xs)) -- Equivalencia -- ============ -- La propiedad es prop_equiv :: [Int] -> Int -> Bool prop_equiv xs y = mayorPrefijoAcotado xs' y' == mayorPrefijoAcotado2 xs' y' && mayorPrefijoAcotado xs' y' == mayorPrefijoAcotado3 xs' y' where xs' = map abs xs y' = abs y -- La comprobación es -- λ> quickCheck prop_equiv -- +++ OK, passed 100 tests. -- (0.01 secs, 2,463,688 bytes) -- Comparación de eficiencia -- ========================= -- λ> length (mayorPrefijoAcotado (repeat 1) (2*10^4)) -- 20000 -- (0.04 secs, 5,086,544 bytes) -- λ> length (mayorPrefijoAcotado2 (repeat 1) (2*10^4)) -- 20000 -- (11.22 secs, 27,083,980,168 bytes) -- λ> length (mayorPrefijoAcotado3 (repeat 1) (2*10^4)) -- 20000 -- (0.02 secs, 4,768,992 bytes) -- -- λ> length (mayorPrefijoAcotado (repeat 1) (8*10^6)) -- 8000000 -- (3.19 secs, 1,984,129,832 bytes) -- λ> length (mayorPrefijoAcotado3 (repeat 1) (8*10^6)) -- 8000000 -- (1.02 secs, 1,856,130,936 bytes) |
Pensamiento
Sed hombres de mal gusto. Yo os aconsejo el mal gusto para combatir los excesos de la moda.
Antonio Machado