Menu Close

Suma de segmentos iniciales

José A. Alonso,

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. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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

Escribe tu solución

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