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
|
1 |
sumaSegmentosIniciales :: [Integer] -> Integer |
tal que (sumaSegmentosIniciales xs) es la suma de las sumas de los segmentos iniciales de xs. Por ejemplo,
|
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
|
1 |
sumaSegmentosIniciales (genericReplicate n 1) |
es igual a
|
1 |
n * (n + 1) `div` 2 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
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