Suma de números de Fibonacci con índice impar
La sucesión de Fibonacci, F(n), es la siguiente sucesión infinita de números naturales:
|
1 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... |
La sucesión comienza con los números 0 y 1. A partir de estos, cada término es la suma de los dos anteriores.
Definir la función
|
1 |
sumaFibsIndiceImpar :: Int -> Integer |
tal que (sumaFibsIndiceImpar n) es la suma de los n primeros términos de la sucesión de Fibonacci no índice impar; es decir,
|
1 |
sumaFibsIndiceImpar n = F(1) + F(3) + ... + F(2*n-1) |
Por ejemplo,
|
1 2 3 4 5 6 |
sumaFibsIndiceImpar 1 == 1 sumaFibsIndiceImpar 2 == 3 sumaFibsIndiceImpar 3 == 8 sumaFibsIndiceImpar 4 == 21 sumaFibsIndiceImpar 5 == 55 sumaFibsIndiceImpar (10^4) `rem` (10^9) == 213093125 |
En los ejemplos anteriores se observa que
|
1 2 3 4 5 |
sumaFibsIndiceImpar 1 == F(2) sumaFibsIndiceImpar 2 == F(4) sumaFibsIndiceImpar 3 == F(6) sumaFibsIndiceImpar 4 == F(8) sumaFibsIndiceImpar 5 == F(10) |
Comprobar con QuickCheck que (sumaFibsIndiceImpar n) es F(2n); es decir, el 2n-ésimo número de Fibonacci
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 |
import Test.QuickCheck -- 1ª solución -- =========== sumaFibsIndiceImpar :: Int -> Integer sumaFibsIndiceImpar n = sum [fib (2*k-1) | k <- [1..n]] -- (fib n) es el n-ésimo término de la sucesión de Fibonacci. Por -- ejemplo, -- fib 6 == 8 fib :: Int -> Integer fib n = fibs !! n -- fibs es la lista de términos de la sucesión de Fibonacci. Por ejemplo, -- λ> take 20 fibs -- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181] fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) -- 2ª solución -- ============ sumaFibsIndiceImpar2 :: Int -> Integer sumaFibsIndiceImpar2 n = sum [a | (a,b) <- zip fibs [0..2*n], odd b] -- Comparación de eficiencia -- ========================= -- λ> sumaFibsIndiceImpar (10^4) `rem` (10^9) -- 213093125 -- (0.98 secs, 13,889,312 bytes) -- λ> sumaFibsIndiceImpar2 (10^4) `rem` (10^9) -- 213093125 -- (0.05 secs, 18,047,720 bytes) -- Comprobación -- ============ -- La propiedad es prop_sumaFibsIndiceImpar :: Int -> Property prop_sumaFibsIndiceImpar n = n >= 0 ==> sumaFibsIndiceImpar n == fib (2*n) -- La comprobación es -- λ> quickCheck prop_sumaFibsIndiceImpar -- +++ OK, passed 100 tests. |
Referencia
- Sum of sequence of odd index Fibonacci numbers en ProofWiki.
Pensamiento
El corazón del poeta, tan rico en sonoridades, es casi un insulto a la afonía cordial de la masa.
Antonio Machado
2 Comentarios