{"id":4896,"date":"2019-04-01T07:56:19","date_gmt":"2019-04-01T05:56:19","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4896"},"modified":"2021-04-25T16:04:01","modified_gmt":"2021-04-25T14:04:01","slug":"arbol-binario-de-divisores-2019a","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/arbol-binario-de-divisores-2019a\/","title":{"rendered":"\u00c1rbol binario de divisores"},"content":{"rendered":"<p>El \u00e1rbol binario de los divisores de 90 es<\/p>\n<pre lang=\"text\"> \n    90\n    \/\\\n   2  45\n      \/\\\n     3  15\n        \/\\\n       3  5\n<\/pre>\n<p>Se puede representar por<\/p>\n<pre lang=\"text\"> \n   N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))\n<\/pre>\n<p>usando el tipo de dato definido por<\/p>\n<pre lang=\"text\"> \n   data Arbol = H Int\n              | N Int Arbol Arbol\n     deriving (Eq, Show)\n<\/pre>\n<p>An\u00e1logamente se obtiene el \u00e1rbol binario de cualquier n\u00famero x: se comienza en x y en cada paso se tiene dos hijos (su menor divisor y su cociente) hasta obtener n\u00fameros primos en las hojas.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\"> \n   arbolDivisores      :: Int -> Arbol\n   hojasArbolDivisores :: Int -> [Int]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(arbolDivisores x) es el \u00e1rbol binario de los divisores de x. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">   \n     \u03bb> arbolDivisores 90\n     N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))\n     \u03bb> arbolDivisores 24\n     N 24 (H 2) (N 12 (H 2) (N 6 (H 2) (H 3)))\n     \u03bb> arbolDivisores 300\n     N 300 (H 2) (N 150 (H 2) (N 75 (H 3) (N 25 (H 5) (H 5))))\n<\/pre>\n<ul>\n<li>(hojasArbolDivisores x) es la lista de las hohas del \u00e1rbol binario de los divisores de x. Por ejemplo<\/li>\n<\/ul>\n<pre lang=\"text\"> \n     hojasArbolDivisores 90   ==  [2,3,3,5]\n     hojasArbolDivisores 24   ==  [2,2,2,3]\n     hojasArbolDivisores 300  ==  [2,2,3,5,5]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primeFactors)\n\ndata Arbol = H Int\n           | N Int Arbol Arbol\n  deriving (Eq, Show)\n\n-- Definici\u00f3n de arbolDivisores\n-- ============================\n\narbolDivisores :: Int -> Arbol\narbolDivisores x\n  | y == x    = H x\n  | otherwise = N x (H y) (arbolDivisores (x `div` y))\n  where y = menorDivisor x\n\n-- (menorDivisor x) es el menor divisor primo de x. Por ejemplo,\n--    menorDivisor 45  ==  3\n--    menorDivisor 5   ==  5\nmenorDivisor :: Int -> Int\nmenorDivisor x =\n  head [y | y <- [2..x], x `mod` y == 0]\n\n-- 1\u00aa definici\u00f3n de hojasArbolDivisores\n-- ====================================\n\nhojasArbolDivisores :: Int -> [Int]\nhojasArbolDivisores = hojas . arbolDivisores\n\n-- (hojas a) es la lista de las hojas del \u00e1rbol a. Por ejemplo,\n--    hojas (N 3 (H 4) (N 5 (H 7) (H 2)))  ==  [4,7,2]\nhojas :: Arbol -> [Int]\nhojas (H x)     = [x]\nhojas (N _ i d) = hojas i ++ hojas d\n\n-- 2\u00aa definici\u00f3n de hojasArbolDivisores\n-- ====================================\n\nhojasArbolDivisores2 :: Int -> [Int]\nhojasArbolDivisores2 = primeFactors\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\nEntre las brevas soy blando;<br \/>\nentre las rocas, de piedra.<br \/>\n\u00a1Malo!<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>El \u00e1rbol binario de los divisores de 90 es 90 \/\\ 2 45 \/\\ 3 15 \/\\ 3 5 Se puede representar por N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5))) usando el tipo de dato definido por data Arbol = H Int | N Int Arbol Arbol deriving&#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":[269,8,71,28,11,247,6],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4896"}],"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=4896"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4896\/revisions"}],"predecessor-version":[{"id":4924,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4896\/revisions\/4924"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4896"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4896"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4896"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}