{"id":5649,"date":"2020-03-06T05:30:53","date_gmt":"2020-03-06T03:30:53","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5649"},"modified":"2020-03-17T08:25:04","modified_gmt":"2020-03-17T06:25:04","slug":"producto-de-fibonaccis-consecutivos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/producto-de-fibonaccis-consecutivos\/","title":{"rendered":"Producto de Fibonaccis consecutivos"},"content":{"rendered":"

Los n\u00fameros de Fibonacci son los n\u00fameros F(n) de la siguiente sucesi\u00f3n<\/p>\n

\n   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...\n<\/pre>\n
que comienza con 0 y 1 y los siguientes t\u00e9rminos son las sumas de los dos anteriores.<\/p>\n
Un n\u00famero x es el producto de dos n\u00fameros de Fibonacci consecutivos si existe un n tal que<\/p>\n
\n   F(n) * F(n+1) = x\n<\/pre>\n
y su prueba es (F(n),F(n+1),True). Por ejemplo, 714 es el producto de dos n\u00fameros de Fibonacci consecutivos ya que<\/p>\n
\nF(8) = 21, F(9) = 34 y 714 = 21 * 34. \n<\/pre>\n
Su prueba es (21, 34, True).<\/p>\n
Un n\u00famero x no es el producto de dos n\u00fameros de Fibonacci consecutivos si no existe un n tal que<\/p>\n
\n   F(n) * F(n+1) = x\n<\/pre>\n
y su prueba es (F(m),F(m+1),False) donde m es el menor n\u00famero tal que<\/p>\n
\n   F(m) * F(m+1) > x\n<\/pre>\n
Por ejemplo, 800 no es el producto de dos n\u00fameros de Fibonacci consecutivos, ya que<\/p>\n
 \n F(8) = 21, F(9) = 34, F(10) = 55 y 21 * 34 < 800 < 34 * 55. \n<\/pre>\n
Su prueba es (34, 55, False),<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n   productoFib :: Integer -> (Integer, Integer, Bool)\n<\/pre>\n
tal que (productoFib x) es la prueba de que es, o no es, el producto de dos n\u00fameros de Fibonacci consecutivos. Por ejemplo,<\/p>\n
\n   productoFib 714  == (21,  34, True)\n   productoFib 800  == (34,  55, False)\n   productoFib 4895 == (55,  89, True)\n   productoFib 5895 == (89, 144, False)\n<\/pre>\n
Soluciones<\/h4>\n
\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nproductoFib :: Integer -> (Integer, Integer, Bool)\nproductoFib n\n  | c == n    = (a,b,True)\n  | otherwise = (a,b,False)\n  where (a,b,c) = head (dropWhile (\\(x,y,z) -> z < n) productos) \n\n-- fibs es la sucesi\u00f3n de n\u00fameros de Fibonacci. Por ejemplo,\n--    take 14 fibs  ==  [0,1,1,2,3,5,8,13,21,34,55,89,144,233]\nfibs :: [Integer]\nfibs = 0 : 1 : zipWith (+) fibs (tail fibs)\n\n-- productos es la lista de las ternas (a,b,c) tales que a y b son dos\n-- n\u00fameros de Fibonacci consecutivos y c es su producto. Por ejemplo,\n--    \u03bb> take 7 productos\n--    [(0,1,0),(1,1,1),(1,2,2),(2,3,6),(3,5,15),(5,8,40),(8,13,104)]\nproductos :: [(Integer,Integer,Integer)]\nproductos = [(x,y,x*y) | (x,y) <- zip fibs (tail fibs)] \n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nproductoFib2 :: Integer -> (Integer, Integer, Bool)\nproductoFib2 n = aux 0 1 n\n  where\n    aux a b c\n        | a * b >= c = (a, b, a * b == c)\n        | otherwise  = aux b (a + b) c\n           \n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nproductoFib3 :: Integer -> (Integer, Integer, Bool)\nproductoFib3 x = aux 0 1\n  where\n    aux a b | a * b >= x = (a, b, x == a * b)\n            | otherwise  = aux b (a + b)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> let (x,_,_) = productoFib (10^20000) in length (show x)\n--    10000\n--    (1.15 secs, 323,396,360 bytes)\n--    \u03bb> let (x,_,_) = productoFib2 (10^20000) in length (show x)\n--    10000\n--    (1.10 secs, 317,268,672 bytes)\n--    \u03bb> let (x,_,_) = productoFib3 (10^20000) in length (show x)\n--    10000\n--    (1.08 secs, 314,972,440 bytes)\n<\/pre>\n
Otras soluciones<\/h4>\n