{"id":6972,"date":"2022-04-25T10:12:10","date_gmt":"2022-04-25T08:12:10","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6972"},"modified":"2022-05-01T11:15:09","modified_gmt":"2022-05-01T09:15:09","slug":"representacion-de-zeckendorf","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/representacion-de-zeckendorf\/","title":{"rendered":"Representaci\u00f3n de Zeckendorf"},"content":{"rendered":"

Los primeros n\u00fameros de Fibonacci son<\/p>\n

\n   1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...\n<\/pre>\n
tales que los dos primeros son iguales a 1 y los siguientes se obtienen sumando los dos anteriores.<\/p>\n
El teorema de Zeckendorf<\/a> establece que todo entero positivo n se puede representar, de manera \u00fanica, como la suma de n\u00fameros de Fibonacci no consecutivos decrecientes. Dicha suma se llama la representaci\u00f3n de Zeckendorf de n. Por ejemplo, la representaci\u00f3n de Zeckendorf de 100 es<\/p>\n
\n   100 = 89 + 8 + 3\n<\/pre>\n
Hay otras formas de representar 100 como sumas de n\u00fameros de Fibonacci; por ejemplo,<\/p>\n
\n   100 = 89 +  8 + 2 + 1\n   100 = 55 + 34 + 8 + 3\n<\/pre>\n
pero no son representaciones de Zeckendorf porque 1 y 2 son n\u00fameros de Fibonacci consecutivos, al igual que 34 y 55.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n   zeckendorf :: Integer -> [Integer]\n<\/pre>\n
tal que (zeckendorf n)<\/code> es la representaci\u00f3n de Zeckendorf de n<\/code>. Por ejemplo,<\/p>\n
\n   zeckendorf 100 == [89,8,3]\n   zeckendorf 200 == [144,55,1]\n   zeckendorf 300 == [233,55,8,3,1]\n   length (zeckendorf (10^50000)) == 66097\n<\/pre>\n
Soluciones<\/h4>\n
\nmodule Representacion_de_Zeckendorf where\n\nimport Data.List (subsequences)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nzeckendorf1 :: Integer -> [Integer]\nzeckendorf1 = head . zeckendorf1Aux\n\nzeckendorf1Aux :: Integer -> [[Integer]]\nzeckendorf1Aux n =\n  [xs | xs <- subsequences (reverse (takeWhile (<= n) (tail fibs))),\n        sum xs == n,\n        sinFibonacciConsecutivos xs]\n\n-- fibs es la la sucesi\u00f3n de los n\u00fameros de Fibonacci. Por ejemplo,\n--    take 14 fibs  == [1,1,2,3,5,8,13,21,34,55,89,144,233,377]\nfibs :: [Integer]\nfibs = 1 : scanl (+) 1 fibs\n-- (sinFibonacciConsecutivos xs) se verifica si en la sucesi\u00f3n\n-- decreciente de n\u00famero de Fibonacci xs no hay dos consecutivos. Por\n-- ejemplo, \n\n-- (sinFibonacciConsecutivos xs) se verifica si en la sucesi\u00f3n\n-- decreciente de n\u00famero de Fibonacci xs no hay dos consecutivos. Por\n-- ejemplo, \n--    sinFibonacciConsecutivos [89, 8, 3]      ==  True\n--    sinFibonacciConsecutivos [55, 34, 8, 3]  ==  False\nsinFibonacciConsecutivos :: [Integer] -> Bool\nsinFibonacciConsecutivos xs =\n  and [x \/= siguienteFibonacci y | (x,y) <- zip xs (tail xs)]\n\n-- (siguienteFibonacci n) es el menor n\u00famero de Fibonacci mayor que\n-- n. Por ejemplo, \n--    siguienteFibonacci 34  ==  55\nsiguienteFibonacci :: Integer -> Integer\nsiguienteFibonacci n =\n  head (dropWhile (<= n) fibs)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nzeckendorf2 :: Integer -> [Integer]\nzeckendorf2 = head . zeckendorf2Aux\n\nzeckendorf2Aux :: Integer -> [[Integer]]\nzeckendorf2Aux n = map reverse (aux n (tail fibs))\n  where aux 0 _ = [[]]\n        aux m (x:y:zs)\n            | x <= m     = [x:xs | xs <- aux (m-x) zs] ++ aux m (y:zs)\n            | otherwise  = []\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nzeckendorf3 :: Integer -> [Integer]\nzeckendorf3 0 = []\nzeckendorf3 n = x : zeckendorf3 (n - x)\n  where x = last (takeWhile (<= n) fibs)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nzeckendorf4 :: Integer -> [Integer]\nzeckendorf4 n = aux n (reverse (takeWhile (<= n) fibs))\n  where aux 0 _      = []\n        aux m (x:xs) = x : aux (m-x) (dropWhile (>m-x) xs)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_zeckendorf :: Positive Integer -> Bool\nprop_zeckendorf (Positive n) =\n  all (== zeckendorf1 n)\n      [zeckendorf2 n,\n       zeckendorf3 n,\n       zeckendorf4 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_zeckendorf\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> zeckendorf1 (7*10^4)\n--    [46368,17711,4181,1597,89,34,13,5,2]\n--    (1.49 secs, 2,380,707,744 bytes)\n--    \u03bb> zeckendorf2 (7*10^4)\n--    [46368,17711,4181,1597,89,34,13,5,2]\n--    (0.07 secs, 21,532,008 bytes)\n--\n--    \u03bb> zeckendorf2 (10^6)\n--    [832040,121393,46368,144,55]\n--    (1.40 secs, 762,413,432 bytes)\n--    \u03bb> zeckendorf3 (10^6)\n--    [832040,121393,46368,144,55]\n--    (0.01 secs, 542,488 bytes)\n--    \u03bb> zeckendorf4 (10^6)\n--    [832040,121393,46368,144,55]\n--    (0.01 secs, 536,424 bytes)\n--\n--    \u03bb> length (zeckendorf3 (10^3000))\n--    3947\n--    (3.02 secs, 1,611,966,408 bytes)\n--    \u03bb> length (zeckendorf4 (10^2000))\n--    2611\n--    (0.02 secs, 10,434,336 bytes)\n--\n--    \u03bb> length (zeckendorf4 (10^50000))\n--    66097\n--    (2.84 secs, 3,976,483,760 bytes)\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n