{"id":7102,"date":"2022-06-28T06:00:52","date_gmt":"2022-06-28T04:00:52","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7102"},"modified":"2022-06-21T13:08:30","modified_gmt":"2022-06-21T11:08:30","slug":"codificacion-de-fibonacci","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/codificacion-de-fibonacci\/","title":{"rendered":"Codificaci\u00f3n de Fibonacci"},"content":{"rendered":"<p>La codificaci\u00f3n de Fibonacci http:\/\/bit.ly\/1Lllqjv de un n\u00famero n es una cadena d = d(0)d(1)&#8230;d(k-1)d(k) de ceros y unos tal que<\/p>\n<pre lang=\"text\">\n   n = d(0)\u00b7F(2) + d(1)\u00b7F(3) +...+ d(k-1)\u00b7F(k+1) \n   d(k-1) = d(k) = 1\n<\/pre>\n<p>donde F(i) es el i-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci<\/p>\n<pre lang=\"text\">\n   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...\n<\/pre>\n<p>Por ejemplo, la codificaci\u00f3n de Fibonacci de 4 es \u00ab1011\u00bb ya que los dos \u00faltimos elementos son iguales a 1 y<\/p>\n<pre lang=\"text\">\n   1\u00b7F(2) + 0\u00b7F(3) + 1\u00b7F(4) = 1\u00b71 + 0\u00b72 + 1\u00b73 = 4\n<\/pre>\n<p>La codificaci\u00f3n de Fibonacci de los primeros n\u00fameros se muestra en la siguiente tabla<\/p>\n<pre lang=\"text\">\n    1  = 1     = F(2)           \u2261       11\n    2  = 2     = F(3)           \u2261      011\n    3  = 3     = F(4)           \u2261     0011\n    4  = 1+3   = F(2)+F(4)      \u2261     1011\n    5  = 5     = F(5)           \u2261    00011\n    6  = 1+5   = F(2)+F(5)      \u2261    10011\n    7  = 2+5   = F(3)+F(5)      \u2261    01011\n    8  = 8     = F(6)           \u2261   000011\n    9  = 1+8   = F(2)+F(6)      \u2261   100011\n   10  = 2+8   = F(3)+F(6)      \u2261   010011\n   11  = 3+8   = F(4)+F(6)      \u2261   001011\n   12  = 1+3+8 = F(2)+F(4)+F(6) \u2261   101011\n   13  = 13    = F(7)           \u2261  0000011\n   14  = 1+13  = F(2)+F(7)      \u2261  1000011\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   codigoFib :: Integer -> String\n<\/pre>\n<p>tal que <code>(codigoFib n)<\/code> es la codificaci\u00f3n de Fibonacci del n\u00famero <code>n<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> codigoFib 65\n   \"0100100011\"\n   \u03bb> [codigoFib n | n <- [1..7]]\n   [\"11\",\"011\",\"0011\",\"1011\",\"00011\",\"10011\",\"01011\"]\n<\/pre>\n<p>Comprobar con QuickCheck las siguientes propiedades:<\/p>\n<ul>\n<li>Todo entero positivo se puede descomponer en suma de n\u00fameros de la sucesi\u00f3n de Fibonacci.<\/li>\n<li>Las codificaciones de Fibonacci tienen como m\u00ednimo 2 elementos.<\/li>\n<li>En las codificaciones de Fibonacci, la cadena \"11\" s\u00f3lo aparece una vez y la \u00fanica vez que aparece es al final.<\/li>\n<\/ul>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (isInfixOf)\nimport Data.Array (Array, accumArray, elems)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ncodigoFib1 :: Integer -> String\ncodigoFib1 = concatMap show . codificaFibLista\n\n-- (codificaFibLista n) es la lista correspondiente a la codificaci\u00f3n de\n-- Fibonacci del n\u00famero n. Por ejemplo,\n--    \u03bb> codificaFibLista 65\n--    [0,1,0,0,1,0,0,0,1,1]\n--    \u03bb> [codificaFibLista n | n <- [1..7]]\n--    [[1,1],[0,1,1],[0,0,1,1],[1,0,1,1],[0,0,0,1,1],[1,0,0,1,1],[0,1,0,1,1]]\ncodificaFibLista :: Integer -> [Integer]\ncodificaFibLista n = map f [2..head xs] ++ [1]\n  where xs = map fst (descomposicion n)\n        f i | i `elem` xs = 1\n            | otherwise = 0\n\n-- (descomposicion n) es la lista de pares (i,f) tales que f es el\n-- i-\u00e9simo n\u00famero de Fibonacci y las segundas componentes es una\n-- sucesi\u00f3n decreciente de n\u00fameros de Fibonacci cuya suma es n. Por\n-- ejemplo, \n--    descomposicion 65  ==  [(10,55),(6,8),(3,2)]\n--    descomposicion 66  ==  [(10,55),(6,8),(4,3)]\ndescomposicion :: Integer -> [(Integer, Integer)]\ndescomposicion 0 = []\ndescomposicion 1 = [(2,1)]\ndescomposicion n = (i,x) : descomposicion (n-x)\n  where (i,x) = fibAnterior n\n\n-- (fibAnterior n) es el mayor n\u00famero de Fibonacci menor o igual que\n-- n. Por ejemplo,\n--    fibAnterior 33  ==  (8,21)\n--    fibAnterior 34  ==  (9,34)\nfibAnterior :: Integer -> (Integer, Integer)\nfibAnterior n = last (takeWhile p fibsConIndice)\n  where p (_,x) = x <= n\n\n-- fibsConIndice es la sucesi\u00f3n de los n\u00fameros de Fibonacci junto con\n-- sus \u00edndices. Por ejemplo,\n--    \u03bb> take 10 fibsConIndice\n--    [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13),(8,21),(9,34)]\nfibsConIndice :: [(Integer, Integer)]\nfibsConIndice = zip [0..] fibs\n\n-- fibs es la sucesi\u00f3n de Fibonacci. Por ejemplo, \n--    take 10 fibs  ==  [0,1,1,2,3,5,8,13,21,34]\nfibs :: [Integer]\nfibs = 0 : 1 : zipWith (+) fibs (tail fibs)\n\n--- 2\u00aa soluci\u00f3n\n-- ============\n\ncodigoFib2 :: Integer -> String\ncodigoFib2 = concatMap show . elems . codificaFibVec\n\n-- (codificaFibVec n) es el vector correspondiente a la codificaci\u00f3n de\n-- Fibonacci del n\u00famero n. Por ejemplo,\n--    \u03bb> codificaFibVec 65\n--    array (0,9) [(0,0),(1,1),(2,0),(3,0),(4,1),(5,0),(6,0),(7,0),(8,1),(9,1)]\n--    \u03bb> [elems (codificaFibVec n) | n <- [1..7]]\n--    [[1,1],[0,1,1],[0,0,1,1],[1,0,1,1],[0,0,0,1,1],[1,0,0,1,1],[0,1,0,1,1]]\ncodificaFibVec :: Integer -> Array Integer Integer\ncodificaFibVec n = accumArray (+) 0 (0,a+1) ((a+1,1):is) \n  where is = [(i-2,1) | (i,_) <- descomposicion n]\n        a  = fst (head is)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_codigoFib :: Positive Integer -> Bool \nprop_codigoFib (Positive n) =\n  codigoFib1 n == codigoFib2 n\n  \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_codigoFib\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> head [n | n <- [1..], length (codigoFib1 n) > 25]\n--    121393\n--    (4.30 secs, 3,031,108,104 bytes)\n--    \u03bb> head [n | n <- [1..], length (codigoFib2 n) > 25]\n--    121393\n--    (3.46 secs, 2,505,869,616 bytes)\n\n-- Propiedades\n-- ===========\n\n-- Usaremos la 2\u00aa definici\u00f3n\ncodigoFib :: Integer -> String\ncodigoFib = codigoFib2\n\n-- Prop.: La funci\u00f3n descomposicion es correcta:\nprop_descomposicion_correcta :: Positive Integer -> Bool\nprop_descomposicion_correcta (Positive n) =\n  n == sum (map snd (descomposicion n))\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_descomposicion_correcta\n--    +++ OK, passed 100 tests.\n\n-- Prop.: Todo entero positivo se puede descomponer en suma de n\u00fameros de\n-- la sucesi\u00f3n de Fibonacci.\nprop_descomposicion :: Positive Integer -> Bool\nprop_descomposicion (Positive n) =\n  not (null (descomposicion n))\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_descomposicion\n--    +++ OK, passed 100 tests.\n\n-- Prop.: Las codificaciones de Fibonacci tienen como m\u00ednimo 2 elementos.\nprop_length_codigoFib :: Positive Integer -> Bool\nprop_length_codigoFib (Positive n) =\n  length (codigoFib n) >= 2\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_length_codigoFib\n--    +++ OK, passed 100 tests.\n\n-- Prop.: En las codificaciones de Fibonacci, la cadena \"11\" s\u00f3lo\n-- aparece una vez y la \u00fanica vez que aparece es al final.\nprop3_cadena_11_en_codigoFib :: Positive Integer -> Bool\nprop3_cadena_11_en_codigoFib (Positive n) = \n  take 2 xs == \"11\" && not (\"11\" `isInfixOf` drop 2 xs)\n  where xs = reverse (codigoFib n)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop3_cadena_11_en_codigoFib\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Codificacion_de_Fibonacci.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La codificaci\u00f3n de Fibonacci http:\/\/bit.ly\/1Lllqjv de un n\u00famero n es una cadena d = d(0)d(1)&#8230;d(k-1)d(k) de ceros y unos tal que n = d(0)\u00b7F(2) + d(1)\u00b7F(3) +&#8230;+ d(k-1)\u00b7F(k+1) d(k-1) = d(k) = 1 donde F(i) es el i-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, &#8230;&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[2],"tags":[521],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7102"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7102"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7102\/revisions"}],"predecessor-version":[{"id":7103,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7102\/revisions\/7103"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7102"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7102"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7102"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}