{"id":3909,"date":"2018-03-27T06:00:18","date_gmt":"2018-03-27T04:00:18","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3909"},"modified":"2022-03-26T11:30:57","modified_gmt":"2022-03-26T09:30:57","slug":"numeros-tetranacci","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-tetranacci\/","title":{"rendered":"N\u00fameros tetranacci"},"content":{"rendered":"<p>Los <strong>n\u00fameros tetranacci<\/strong> son una generalizaci\u00f3n de los n\u00fameros de Fibonacci definidos por<\/p>\n<pre lang=\"text\">\n   T(0) = 0,\n   T(1) = 1,\n   T(2) = 1,\n   T(3) = 2, \n   T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4), para n > 3.\n<\/pre>\n<p>Los primeros n\u00fameros tetranacci son<\/p>\n<pre lang=\"text\">\n   0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   tetranacci        :: Int -> Integer\n   graficaTetranacci :: Int -> IO ()\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(tetranacci n) es el n-\u00e9simo n\u00famero tetranacci. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> tetranacci 10\n     208\n     \u03bb> map tetranacci [0..10]\n     [0,1,1,2,4,8,15,29,56,108,208]\n     \u03bb> length (show (tetranacci5 (10^5)))\n     28501\n<\/pre>\n<ul>\n<li>(graficaTetranacci n) dibuja la gr\u00e1fica de los cocientes de n primeros pares de n\u00famero tetranacci. Por ejemplo, (graficaTetranacci 300) dibuja<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Numeros_tetranacci_200.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Numeros_tetranacci_200.png?resize=640%2C480\" alt=\"Numeros_tetranacci_200\" width=\"640\" height=\"480\" class=\"aligncenter size-full wp-image-3910\" srcset=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Numeros_tetranacci_200.png?w=640&amp;ssl=1 640w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Numeros_tetranacci_200.png?resize=300%2C225&amp;ssl=1 300w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Numeros_tetranacci_200.png?resize=100%2C75&amp;ssl=1 100w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Numeros_tetranacci_200.png?resize=150%2C112&amp;ssl=1 150w\" sizes=\"(max-width: 640px) 100vw, 640px\" data-recalc-dims=\"1\" \/><\/a><\/li>\n<\/ul>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (zipWith4)\nimport Data.Array\nimport Graphics.Gnuplot.Simple\n\n-- 1\u00aa soluci\u00f3n (por recursi\u00f3n) \n-- ===========================\n\ntetranacci :: Int -> Integer\ntetranacci 0 = 0\ntetranacci 1 = 1\ntetranacci 2 = 1\ntetranacci 3 = 2\ntetranacci n =\n  tetranacci (n-1) + tetranacci (n-2) + tetranacci (n-3) + tetranacci (n-4) \n\n-- 2\u00aa soluci\u00f3n (programaci\u00f3n din\u00e1mica con zipWith4)\n-- ================================================\n\ntetranacci2 :: Int -> Integer\ntetranacci2 n = tetranaccis2 !! n\n\ntetranaccis2 :: [Integer]\ntetranaccis2 = \n    0 : 1 : 1 : 2 : zipWith4 f (r 0) (r 1) (r 2) (r 3)\n    where f a b c d = a+b+c+d\n          r n       = drop n tetranaccis2\n\n-- 3\u00aa soluci\u00f3n (con acumuladores)\n-- ==============================\n\ntetranacci3 :: Int -> Integer\ntetranacci3 n = tetranaccis3 !! n\n\ntetranaccis3 :: [Integer]\ntetranaccis3 = p (0, 1, 1, 2)\n    where p (a, b, c, d) = a : p (b, c, d, a + b + c + d)\n\n-- 4\u00aa soluci\u00f3n\n-- =============\n\ntetranacci4 :: Int -> Integer\ntetranacci4 n = tetranaccis4 !! n\n\ntetranaccis4 :: [Integer]\ntetranaccis4 = 0 : 1 : 1 : 2 : p tetranaccis4\n   where p (a:b:c:d:xs) = (a+b+c+d): p (b:c:d:xs)\n\n-- 5\u00aa soluci\u00f3n (programaci\u00f3n din\u00e1mica con vectores)\n-- ================================================\n\ntetranacci5 :: Int -> Integer\ntetranacci5 n = v ! n where\n  v = array (0,n) [(i,f i) | i <- [0..n]]\n  f 0 = 0\n  f 1 = 1\n  f 2 = 1\n  f 3 = 2\n  f k = v!(k-1) + v!(k-2) + v!(k-3) + v!(k-4) \n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> tetranacci 26\n--    7555935\n--    (3.04 secs, 1,649,520,064 bytes)\n--    \u03bb> tetranacci2 26\n--    7555935\n--    (0.00 secs, 148,064 bytes)\n-- \n--    \u03bb> length (show (tetranacci2 (10^5)))\n--    28501\n--    (1.22 secs, 1,844,457,288 bytes)\n--    \u03bb> length (show (tetranacci3 (10^5)))\n--    28501\n--    (0.88 secs, 1,860,453,968 bytes)\n--    \u03bb> length (show (tetranacci4 (10^5)))\n--    28501\n--    (0.77 secs, 1,882,852,168 bytes)\n--    \u03bb> length (show (tetranacci5 (10^5)))\n--    28501\n--    (0.72 secs, 1,905,707,408 bytes)\n\n-- Gr\u00e1fica\n-- =======\n\ngraficaTetranacci :: Int -> IO ()\ngraficaTetranacci n =\n  plotList [ Key Nothing\n           , Title \"Tasa de crecimiento de los numeros tetranacci\"\n           , PNG (\"Numeros_tetranacci_\" ++ show n ++ \".png\")\n           ]\n           (take n (zipWith (\/) (tail xs) xs))\n  where xs = (map fromIntegral tetranaccis4) :: [Double]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Los n\u00fameros tetranacci son una generalizaci\u00f3n de los n\u00fameros de Fibonacci definidos por T(0) = 0, T(1) = 1, T(2) = 1, T(3) = 2, T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4), para n > 3. Los primeros n\u00fameros tetranacci son 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208 Definir&#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":[5],"tags":[250,286,183,376,10,11,309,6,45,47,76,443],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3909"}],"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=3909"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3909\/revisions"}],"predecessor-version":[{"id":3976,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3909\/revisions\/3976"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3909"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3909"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3909"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}