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