División equitativa
Definir la función
|
1 |
divisionEquitativa :: [Int] -> Maybe ([Int],[Int]) |
tal que (divisionEquitativa xs) determina si la lista de números enteros positivos xs se puede dividir en dos partes (sin reordenar sus elementos) con la misma suma. Si es posible, su valor es el par formado por las dos partes. Si no lo es, su valor es Nothing. Por ejemplo,
|
1 2 3 4 |
divisionEquitativa [1,2,3,4,5,15] == Just ([1,2,3,4,5],[15]) divisionEquitativa [15,1,2,3,4,5] == Just ([15],[1,2,3,4,5]) divisionEquitativa [1,2,3,4,7,15] == Nothing divisionEquitativa [1,2,3,4,15,5] == Nothing |
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 |
import Data.Maybe (isNothing, fromJust, listToMaybe) import Data.List (elemIndex, inits, tails) -- 1ª solución divisionEquitativa1 :: [Int] -> Maybe ([Int],[Int]) divisionEquitativa1 xs = aux (particiones xs) where aux [] = Nothing aux ((as,bs):ys) | sum as == sum bs = Just (as,bs) | otherwise = aux ys particiones xs = [splitAt i xs | i <- [1..length xs-1]] -- 2ª solución divisionEquitativa2 :: [Int] -> Maybe ([Int],[Int]) divisionEquitativa2 xs | 2 * b == suma = Just $ splitAt (length as + 1) xs | otherwise = Nothing where suma = sum xs (as,(b:bs)) = span (<suma `div` 2) $ scanl1 (+) xs -- 3ª solución divisionEquitativa3 :: [Int] -> Maybe ([Int],[Int]) divisionEquitativa3 xs | odd n = Nothing | isNothing p = Nothing | otherwise = Just (splitAt (1 + fromJust p) xs) where n = sum xs ys = scanl1 (+) xs p = elemIndex (n `div` 2) ys -- 4ª solución divisionEquitativa4 :: [Int] -> Maybe ([Int],[Int]) divisionEquitativa4 xs | odd (sum xs) = Nothing | otherwise = aux [] xs where aux as bs@(b:bs') | sum as == sum bs = Just (reverse as, bs) | sum as > sum bs = Nothing | otherwise = aux (b:as) (bs') -- 5ª solución divisionEquitativa5 :: [Int] -> Maybe ([Int],[Int]) divisionEquitativa5 xs = listToMaybe [(ys, zs) | (ys,zs) <- zip (inits xs) (tails xs) , sum ys == sum zs ] |