{"id":5259,"date":"2019-12-18T05:30:59","date_gmt":"2019-12-18T03:30:59","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5259"},"modified":"2019-12-25T07:59:55","modified_gmt":"2019-12-25T05:59:55","slug":"arbol-binario-de-divisores","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/arbol-binario-de-divisores\/","title":{"rendered":"\u00c1rbol binario de divisores"},"content":{"rendered":"<p>El \u00e1rbol binario de los divisores de 24 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 (isPrime, primeFactors)\n\ndata Arbol = H Int\n           | N Int Arbol Arbol\n  deriving (Eq, Show)\n\n-- 1\u00aa soluci\u00f3n\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\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 soluci\u00f3n\n-- ===========\n\narbolDivisores2 :: Int -> Arbol\narbolDivisores2 x\n  | y == x    = H x\n  | otherwise = N x (H y) (arbolDivisores (x `div` y))\n  where (y:_) = primeFactors x\n\nhojasArbolDivisores2 :: Int -> [Int]\nhojasArbolDivisores2 = primeFactors\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\nCuando el Ser que se es hizo la nada<br \/>\ny repos\u00f3 que bien lo merec\u00eda,<br \/>\nya tuvo el d\u00eda noche, y compa\u00f1\u00eda<br \/>\ntuvo el amante en la ausencia de la amada.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>El \u00e1rbol binario de los divisores de 24 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\/5259"}],"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=5259"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5259\/revisions"}],"predecessor-version":[{"id":5300,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5259\/revisions\/5300"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5259"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5259"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5259"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}