Producto de Fibonaccis consecutivos
Los números de Fibonacci son los números F(n) de la siguiente sucesión
|
1 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... |
que comienza con 0 y 1 y los siguientes términos son las sumas de los dos anteriores.
Un número x es el producto de dos números de Fibonacci consecutivos si existe un n tal que
|
1 |
F(n) * F(n+1) = x |
y su prueba es (F(n),F(n+1),True). Por ejemplo, 714 es el producto de dos números de Fibonacci consecutivos ya que
|
1 |
F(8) = 21, F(9) = 34 y 714 = 21 * 34. |
Su prueba es (21, 34, True).
Un número x no es el producto de dos números de Fibonacci consecutivos si no existe un n tal que
|
1 |
F(n) * F(n+1) = x |
y su prueba es (F(m),F(m+1),False) donde m es el menor número tal que
|
1 |
F(m) * F(m+1) > x |
Por ejemplo, 800 no es el producto de dos números de Fibonacci consecutivos, ya que
|
1 |
F(8) = 21, F(9) = 34, F(10) = 55 y 21 * 34 < 800 < 34 * 55. |
Su prueba es (34, 55, False),
Definir la función
|
1 |
productoFib :: Integer -> (Integer, Integer, Bool) |
tal que (productoFib x) es la prueba de que es, o no es, el producto de dos números de Fibonacci consecutivos. Por ejemplo,
|
1 2 3 4 |
productoFib 714 == (21, 34, True) productoFib 800 == (34, 55, False) productoFib 4895 == (55, 89, True) productoFib 5895 == (89, 144, False) |
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 |
-- 1ª solución -- =========== productoFib :: Integer -> (Integer, Integer, Bool) productoFib n | c == n = (a,b,True) | otherwise = (a,b,False) where (a,b,c) = head (dropWhile (\(x,y,z) -> z < n) productos) -- fibs es la sucesión de números de Fibonacci. Por ejemplo, -- take 14 fibs == [0,1,1,2,3,5,8,13,21,34,55,89,144,233] fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) -- productos es la lista de las ternas (a,b,c) tales que a y b son dos -- números de Fibonacci consecutivos y c es su producto. Por ejemplo, -- λ> take 7 productos -- [(0,1,0),(1,1,1),(1,2,2),(2,3,6),(3,5,15),(5,8,40),(8,13,104)] productos :: [(Integer,Integer,Integer)] productos = [(x,y,x*y) | (x,y) <- zip fibs (tail fibs)] -- 2ª solución -- =========== productoFib2 :: Integer -> (Integer, Integer, Bool) productoFib2 n = aux 0 1 n where aux a b c | a * b >= c = (a, b, a * b == c) | otherwise = aux b (a + b) c -- 3ª solución -- =========== productoFib3 :: Integer -> (Integer, Integer, Bool) productoFib3 x = aux 0 1 where aux a b | a * b >= x = (a, b, x == a * b) | otherwise = aux b (a + b) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> let (x,_,_) = productoFib (10^20000) in length (show x) -- 10000 -- (1.15 secs, 323,396,360 bytes) -- λ> let (x,_,_) = productoFib2 (10^20000) in length (show x) -- 10000 -- (1.10 secs, 317,268,672 bytes) -- λ> let (x,_,_) = productoFib3 (10^20000) in length (show x) -- 10000 -- (1.08 secs, 314,972,440 bytes) |
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>
Pensamiento
«El placer que obtenemos de la música proviene de contar, pero contando inconscientemente. La música no es más que aritmética inconsciente.»