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
   sumaSegmentosIniciales [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.

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>
Inicial

6 soluciones de “Suma de segmentos iniciales

  1. Enrique Zubiría
    import Data.List
    import Test.QuickCheck
     
    sumaSegmentosIniciales :: [Integer] -> Integer
    sumaSegmentosIniciales xs = sum (zipWith (*) xs [l,l-1..1])
      where l = genericLength xs
     
    prop_sumaSegmentosIniciales :: Integer -> Bool
    prop_sumaSegmentosIniciales n =
      div (m * (m+1)) 2 == sumaSegmentosIniciales (genericReplicate m 1)
      where m = abs n
     
    -- *Main> quickCheck prop_sumaSegmentosIniciales
    -- +++ OK, passed 100 tests.
  2. rebgongor
    import Test.QuickCheck
    import Data.List
     
    sumaSegmentosIniciales :: [Integer] -> Integer
    sumaSegmentosIniciales xs = sum $ concat [take n xs | n <- [1..length xs]]
     
    propiedad :: Positive Integer -> Bool
    propiedad (Positive n) =
      sumaSegmentosIniciales (genericReplicate n 1) == div (n*(n+1)) 2
     
    -- λ> quickCheck propiedad
    -- +++ OK, passed 100 tests.
  3. rebgongor

    Una variante de la forma anterior:

    import Test.QuickCheck
    import Data.List
     
    sumaSegmentosIniciales :: [Integer] -> Integer
    sumaSegmentosIniciales xs = sum $ map sum [take n xs | n <- [1..length xs]]
     
    propiedad :: Positive Integer -> Bool
    propiedad (Positive n) =
      sumaSegmentosIniciales (genericReplicate n 1) == div (n*(n+1)) 2
     
    -- > quickCheck propiedad
    -- +++ OK, passed 100 tests.
  4. fercarnav
    import Data.List
    import Test.QuickCheck
     
    sumaSegmentosIniciales :: [Integer] -> Integer
    sumaSegmentosIniciales = sumaSegAux 0 0
     
    sumaSegAux :: Integer ->Integer -> [Integer] -> Integer
    sumaSegAux n y []     = n
    sumaSegAux n y (x:xs) = sumaSegAux (n+y+x) (y+x) xs
     
    prop_sumaSegmentosIniciales :: Integer -> Bool
    prop_sumaSegmentosIniciales n =
      div (m * (m+1)) 2 == sumaSegmentosIniciales (genericReplicate m 1)
      where m = abs n
  5. anthormol
    import Data.List
    import Test.QuickCheck
     
    sumaSegmentosIniciales :: [Integer] -> Integer
    sumaSegmentosIniciales = sum . scanl1 (+)
     
    prop_sumaSegmentosIniciales :: Integer -> Bool
    prop_sumaSegmentosIniciales n =
      div (m * (m+1)) 2 == sumaSegmentosIniciales (genericReplicate m 1)
      where m = abs n
     
    -- λ> quickCheck prop_sumaSegmentosIniciales
    -- +++ OK, passed 100 tests.
  6. javjimord
    import Data.List (inits, genericReplicate)
    import Test.QuickCheck
     
    sumaSegmentosIniciales :: [Integer] -> Integer
    sumaSegmentosIniciales = sum . map sum . inits
     
    prop_SegmentosIniciales :: Integer -> Property
    prop_SegmentosIniciales n =
      n >= 0
      ==>
      sumaSegmentosIniciales (genericReplicate n 1) == n * (n + 1) `div` 2

Leave a Reply

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