Menu Close

Centro de gravedad de una lista

José A. Alonso,

Se dice que una lista de números xs es equilibrada si existe una posición k tal que la suma de los elementos de xs en las posiciones menores que k es igual a la de los elementos de xs en las posiciones mayores que k. La posición k se llama el centro de gravedad de xs. Por ejemplo, la lista [1,3,4,5,-2,1] es equilibrada, y su centro de gravedad es 2, ya que la suma de [1,3] es igual a la de [5,-2,1]. En cambio, la lista [1,6,4,5,-2,1] no tiene centro de gravedad.

Definir la función

   centro :: (Num a, Eq a) => [a] -> Maybe Int

tal que (centro xs) es justo el centro e gravedad de xs, si la lista xs es equilibrada y Nothing en caso contrario. Por ejemplo,

   centro [1,3,4,5,-2,1]           ==  Just 2
   centro [1,6,4,5,-2,1]           ==  Nothing
   centro [1,2,3,4,3,2,1]          ==  Just 3
   centro [1,100,50,-51,1,1]       ==  Just 1
   centro [1,2,3,4,5,6]            ==  Nothing
   centro [20,10,30,10,10,15,35]   ==  Just 3
   centro [20,10,-80,10,10,15,35]  ==  Just 0
   centro [10,-80,10,10,15,35,20]  ==  Just 6
   centro [0,0,0,0,0]              ==  Just 0
   centro [-1,-2,-3,-4,-3,-2,-1]   ==  Just 3

Soluciones

import Data.List (inits, tails)
import Data.Maybe (listToMaybe)
 
-- 1ª solución
-- ===========
 
centro1 :: (Num a, Eq a) => [a] -> Maybe Int
centro1 xs 
    | null ns   = Nothing
    | otherwise = Just (head ns)
    where ns = [n | n <- [0..length xs - 1],
                    let (ys,_:zs) = splitAt n xs,
                    sum ys == sum zs]
 
-- 2ª solución
-- ===========
 
centro2 :: (Num a, Eq a) => [a] -> Maybe Int
centro2 xs = aux 0 0 (sum xs) xs where
    aux _ _ _ [] = Nothing
    aux k i d (z:zs) | i == d - z = Just k
                     | otherwise  = aux (k + 1) (i + z) (d - z) zs
 
-- 3ª solución
-- ===========
 
centro3 :: (Num a, Eq a) => [a] -> Maybe Int
centro3 xs =
  listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)
                  , sum ys == sum zs]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> let xs = [1..3000] in centro1 (xs ++ (0:xs))
--    Just 3000
--    (2.70 secs, 2,088,881,728 bytes)
--    λ> let xs = [1..3000] in centro2 (xs ++ (0:xs))
--    Just 3000
--    (0.03 secs, 0 bytes)
--    λ> let xs = [1..3000] in centro3 (xs ++ (0:xs))
--    Just 3000
--    (2.34 secs, 1,727,569,688 bytes)
Medio
, , , , , , , , , ,

8 soluciones de “Centro de gravedad de una lista”

  1. Responder
    Chema Cortés 
    import Data.List
import Data.Maybe
 
centro :: (Num a, Eq a) => [a] -> Maybe Int
centro xs =
  listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)
                  , sum ys == sum zs]
  2. Responder
    manpende 
    import Data.List
 
centro :: (Num a, Eq a) => [a] -> Maybe Int
centro xs 
     | null ys = Nothing
     | otherwise = Just $ fst (head ys)
           where l = length xs
                 ys = equilibrios xs
 
equilibrios :: (Num a, Eq a) => [a] -> [(Int,(a,a))]
equilibrios xs = filter ((_,(x,y)) -> x==y) $ sumas xs
 
sumas :: (Num a, Eq a) => [a] -> [(Int,(a,a))]
sumas [] = []
sumas xs = zip ys [(sum $ take (n+1) xs, sum $ take (l-n) (reverse xs)) | n <- ys]
        where l = length xs
              ys = [0..l-1]
  3. Responder
    juanarcon 
     
import Data.List
 
centro :: (Num a, Eq a) => [a] -> Maybe Int
centro xs | null ys = Nothing
          | otherwise = Just (head ys)
                        where ys = [ n | n<- [0..n-1],
                                     sum (take n xs) == sum (drop (n+1) xs)]
                              n = length xs
  4. Responder
    manvermor 
     
-- Mismo fundamento que juanarcon pero usando auxiliar y sin guardas.
 
centro :: (Num a, Eq a) => [a] -> Maybe Int
centro xs = aux ([ n | n <- [0..length xs-1], sum (take n xs) == sum (drop (n+1) xs)])
    where aux [] = Nothing
          aux zs = Just (head zs)
  5. Responder
    fracruzam

    Intentando no repetir la misma suma varias veces:

    centro :: (Num a, Eq a) => [a] -> Maybe Int
centro (x:xs) | null ys   = Nothing
              | otherwise = Just a
  where ys = dropWhile ((_,x,y,_) -> x /= y) $ 
             scanl ((x,y,z,w) n -> (x+1,y+w,z-n,n)) (0,0,sum xs,x) xs
        ((a,_,_,_):_) = ys
centro  _     = Just 0
  6. Responder
    Paola Cabrera Perza 
    centro :: (Num a, Eq a) => [a] -> Maybe Int
centro (x:xs)|x==sum (x:xs)=Just 0
             |cogerHasta (x:xs)==centros (x:xs)=Nothing
             |otherwise = Just(length(cogerHasta (x:xs))+1)
centro1 :: (Eq a, Num a) => [a] -> Int -> Bool
centro1 xs n = sum(take n xs)==sum(take(a-(n+1))(reverse(xs)))
              where a =length xs
centros :: (Eq a, Num a) => [a] -> [Bool]
centros []=[]
centros xs=[centro1 xs n|n<-[1..(length xs)]]
cogerHasta :: (Eq a, Num a) => [a] -> [Bool]
cogerHasta xs=takeWhile(/=(True))(centros xs)
  7. Responder
    carmengar 
    import Data.List
 
centro :: (Num a, Eq a) => [a] -> Maybe Int
centro xs | hayCentro xs = Just $ head [k | (x,y,k) <- pares xs, x == y]
          | otherwise    = Nothing
 
hayCentro :: (Num a, Eq a) => [a] -> Bool
hayCentro = any ((x,y,z) -> x == y) . pares
 
 
pares :: (Num a, Eq a) => [a] -> [(a,a,Int)]
pares xs = (0,sum $ tail xs, 0) : [(s1 k,s2 k,k) | k <- [1..l-1]]
           where l    = length xs
                 s1 k = sum [xs !! i | i <- [0..k-1]]
                 s2 k = sum [xs !! i | i <- [k+1..l-1]]
  8. Responder
    alvalvdom1 
    centro :: (Num a, Eq a) => [a] -> Maybe Int
centro (x:xs) | sum xs == 0 = Just 0
              | otherwise = aux [x] xs 1
          where aux :: (Num a, Eq a) => [a] -> [a] -> Int -> Maybe Int
                aux _ [] _ = Nothing
                aux ys (z:zs) m | sum ys == sum zs = Just m
                                | otherwise = aux (ys++[z]) zs (m+1)

Leave a Reply to fracruzam Cancel reply

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