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

1	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

1 2	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)

1	sumaSegmentosIniciales (genericReplicate n 1)

es igual a

   n * (n + 1) `div` 2

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

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

5 Comentarios

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

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

Responder

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)

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)

Responder

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.

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.

Responder

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

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

Responder

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)))))$

Responder

Suma de segmentos iniciales

Soluciones

Pensamiento

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico