Menu Close

Suma de segmentos iniciales

Los segmentos iniciales de [3,1,2,5] son [3], [3,1], [3,1,2] y [3,1,2,5]. Sus sumas son 3, 4, 6 y 9, respectivamente. La suma de dichas sumas es 24.

Definir la función

   sumaSegmentosIniciales :: [Integer] -> Integer

tal que (sumaSegmentosIniciales xs) es la suma de las sumas de los segmentos iniciales de xs. Por ejemplo,

   sumaSegmentosIniciales [3,1,2,5]     ==  24
   sumaSegmentosIniciales3 [1..3*10^6]  ==  4500004500001000000

Comprobar con QuickCheck que la suma de las sumas de los segmentos iniciales de la lista formada por n veces el número uno es el n-ésimo número triangular; es decir que

   sumaSegmentosIniciales (genericReplicate n 1)

es igual a

   n * (n + 1) `div` 2

Soluciones

import Data.List (genericLength, genericReplicate)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
sumaSegmentosIniciales :: [Integer] -> Integer
sumaSegmentosIniciales xs =
  sum [sum (take k xs) | k <- [1.. length xs]]
 
-- 2ª solución
-- ===========
 
sumaSegmentosIniciales2 :: [Integer] -> Integer
sumaSegmentosIniciales2 xs =
  sum (zipWith (*) [n,n-1..1] xs)
  where n = genericLength xs
 
-- 3ª solución
-- ===========
 
sumaSegmentosIniciales3 :: [Integer] -> Integer
sumaSegmentosIniciales3 xs =
  sum (scanl1 (+) xs)
 
-- Comprobación de la equivalencia
-- ===============================
 
-- La propiedad es
prop_sumaSegmentosInicialesEquiv :: [Integer] -> Bool
prop_sumaSegmentosInicialesEquiv xs =
  all (== sumaSegmentosIniciales xs) [f xs | f <- [ sumaSegmentosIniciales2
                                                  , sumaSegmentosIniciales3]]
 
-- La comprobación es
--   λ> quickCheck prop_sumaSegmentosInicialesEquiv
--   +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--   λ> sumaSegmentosIniciales [1..10^4]
--   166716670000
--   (2.42 secs, 7,377,926,824 bytes)
--   λ> sumaSegmentosIniciales2 [1..10^4]
--   166716670000
--   (0.01 secs, 4,855,176 bytes)
--   
--   λ> sumaSegmentosIniciales2 [1..3*10^6]
--   4500004500001000000
--   (2.68 secs, 1,424,404,168 bytes)
--   λ> sumaSegmentosIniciales3 [1..3*10^6]
--   4500004500001000000
--   (1.54 secs, 943,500,384 bytes)
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es
prop_sumaSegmentosIniciales :: Positive Integer -> Bool
prop_sumaSegmentosIniciales (Positive n) =
  sumaSegmentosIniciales3 (genericReplicate n 1) ==
  n * (n + 1) `div` 2
 
-- La compronación es
--   λ> quickCheck prop_sumaSegmentosIniciales
--   +++ OK, passed 100 tests.

Pensamiento

Al andar se hace camino,
y al volver la vista atrás
se ve la senda que nunca
se ha de volver a pisar.

Antonio Machado

Inicial

5 soluciones de “Suma de segmentos iniciales

  1. frahidzam
    import Data.List (inits, genericReplicate)
    import Test.QuickCheck
     
    sumaSegmentosIniciales :: [Integer] -> Integer
    sumaSegmentosIniciales xs = sum $! map sum $! inits xs
     
    sumaSegmentosIniciales2 :: [Integer] -> Integer
    sumaSegmentosIniciales2 xs = sum $! scanl1 (+) xs
     
    prop_sumaSegmentos :: Integer -> Property
    prop_sumaSegmentos n =
      n >= 0 ==>
      sumaSegmentosIniciales2 (genericReplicate n 1) ==
      div (n * (n + 1))  2
  2. adogargon
    import Data.List (genericReplicate, genericLength)
    import Test.QuickCheck
     
    sumaSegmentosIniciales :: [Integer] -> Integer
    sumaSegmentosIniciales [] = 0
    sumaSegmentosIniciales xs =
      sum [x * (s - k) | (x,k) <- zip xs [0..s]]
      where s = genericLength xs
     
    -- Calcula el último ejemplo 
    --   λ> sumaSegmentosIniciales [1..3*10^6] 
    --   4500004500001000000
    --   (16.28 secs, 1,905,578,496 bytes)
     
    prop_sumaSegmentos :: Integer -> Property
    prop_sumaSegmentos n =
      n >= 0 ==>
      sumaSegmentosIniciales (genericReplicate n 1) ==
      (n * (n + 1)) `div` 2
     
    -- La comprobacion es:
    --   λ> quickCheck prop_sumaSegmentos
    --   +++ OK, passed 100 tests.
    --   (1.20 secs, 3,339,528 bytes)
  3. Sermurgar
    import Test.QuickCheck
    import Data.List (genericReplicate)
     
    sumaSegmentosIniciales :: [Integer] -> Integer
    sumaSegmentosIniciales xs =
      sum (map sum (separaSegmentos 1 xs))
     
    separaSegmentos :: Int -> [Integer] -> [[Integer]]
    separaSegmentos 0 _  = [[]]
    separaSegmentos _ [] = [[]]
    separaSegmentos m (xs)
      | length xs > m = [take m xs] ++ separaSegmentos (m+1) xs
      | otherwise     = [xs]  
     
    prop_sumaSegmentos :: Integer -> Property 
    prop_sumaSegmentos n =
      n >= 0 ==>
      sumaSegmentosIniciales (genericReplicate n 1) == n * (n + 1) `div` 2
     
    -- La comprobación es : 
    --   λ> quickCheck prop_sumaSegmentos
    --   +++ OK, passed 100 tests.
  4. luipromor
    import Test.QuickCheck
    import Data.List (genericReplicate, genericLength)
     
    sumaSegmentosIniciales :: [Integer] -> Integer
    sumaSegmentosIniciales xs =
      aux xs (genericLength xs)
      where aux []     _ = 0
            aux (x:xs) n = n * x + aux xs (n - 1)
     
    prop_sumaSegmentosIniciales :: Integer -> Property
    prop_sumaSegmentosIniciales n =
      n >= 0 ==>
      sumaSegmentosIniciales (genericReplicate n 1) == n * (n + 1) `div` 2
  5. frahidzam

    Solución en Maxima

    suma (xs) := lreduce (“+”,xs)$
    inits (xs) := (makelist ((rest((reverse (xs)),k)),k,0,(length(xs)-1)))$
    sumaSegmentosIniciales (xs) := (lreduce (“+” ,(map((lambda([ys],suma(ys))),inits (xs)))))$

Escribe tu solución

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