{"id":3492,"date":"2017-12-07T06:00:37","date_gmt":"2017-12-07T04:00:37","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3492"},"modified":"2021-04-25T17:02:24","modified_gmt":"2021-04-25T15:02:24","slug":"caminos-minimales-en-un-arbol-numerico-2017","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/caminos-minimales-en-un-arbol-numerico-2017\/","title":{"rendered":"Caminos minimales en un \u00e1rbol num\u00e9rico"},"content":{"rendered":"<p>En la librer\u00eda <a href=\"http:\/\/bit.ly\/2mLEVg4\">Data.Tree<\/a> se definen los \u00e1rboles y los bosques como sigue<\/p>\n<pre lang=\"text\">\n   data Tree a   = Node a (Forest a)\n   type Forest a = [Tree a]\n<\/pre>\n<p>Se pueden definir \u00e1rboles. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]\n<\/pre>\n<p>Y se pueden dibujar con la funci\u00f3n drawTree. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> putStrLn (drawTree (fmap show ej))\n   3\n   |\n   +- 5\n   |  |\n   |  `- 9\n   |\n   `- 7\n<\/pre>\n<p>Los <strong>mayores divisores<\/strong> de un n\u00famero x son los divisores u tales que u > 1 y existe un v tal que 1 &lt; v &lt; u y u*v = x.  Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.<\/p>\n<p>El <strong>\u00e1rbol de los predecesores y mayores divisores<\/strong> de un n\u00famero x es el \u00e1rbol cuya ra\u00edz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el \u00e1rbol de los predecesores y mayores divisores del n\u00famero 6 es<\/p>\n<pre lang=\"text\">\n       6\n      \/ \\\n     5   3 \n     |   |\n     4   2\n    \/ \\  |\n   3   2 1 \n   |   | \n   2   1\n   |\n   1\n<\/pre>\n<p>Definir las siguientes funciones<\/p>\n<pre lang=\"text\">\n   mayoresDivisores :: Int -> [Int]\n   arbol            :: Int -> Tree Int\n   caminos          :: Int -> [[Int]]\n   caminosMinimales :: Int -> [[Int]]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     mayoresDivisores 24  ==  [12,8,6]\n     mayoresDivisores 16  ==  [8,4]\n     mayoresDivisores 10  ==  [5]\n     mayoresDivisores 17  ==  []\n<\/pre>\n<ul>\n<li>(arbol x) es el \u00e1rbol de los predecesores y mayores divisores del n\u00famero x. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> putStrLn (drawTree (fmap show (arbol 6)))\n     6\n     |\n     +- 5\n     |  |\n     |  `- 4\n     |     |\n     |     +- 3\n     |     |  |\n     |     |  `- 2\n     |     |     |\n     |     |     `- 1\n     |     |\n     |     `- 2\n     |        |\n     |        `- 1\n     |\n     `- 3\n        |\n        `- 2\n           |\n           `- 1\n<\/pre>\n<ul>\n<li>(caminos x) es la lista de los caminos en el \u00e1rbol de los predecesores y mayores divisores del n\u00famero x. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> caminos 6\n     [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]\n<\/pre>\n<ul>\n<li>(caminosMinimales x) es la lista de los caminos en de menor longitud en el \u00e1rbol de los predecesores y mayores divisores del n\u00famero x. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> caminosMinimales 6\n     [[6,3,2,1]]\n     \u03bb> caminosMinimales 17\n     [[17,16,4,2,1]]\n     \u03bb> caminosMinimales 50\n     [[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Tree\n\nmayoresDivisores :: Int -> [Int]\nmayoresDivisores x =\n  [max u v | u <- [2..floor (sqrt (fromIntegral x))]\n           , x `mod` u == 0\n           , let v = x `div` u]  \n\narbol :: Int -> Tree Int\narbol 1 = Node 1 []\narbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])\n\ncaminos :: Int -> [[Int]]\ncaminos = caminosArbol . arbol\n\n--    \u03bb> caminosArbol (arbol 6)\n--    [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]\ncaminosArbol :: Tree a -> [[a]]\ncaminosArbol (Node x []) = [[x]]\ncaminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]\n\ncaminosBosque :: Forest a -> [[a]]\ncaminosBosque = concatMap caminosArbol\n\ncaminosMinimales :: Int -> [[Int]]\ncaminosMinimales x = [ys | ys <- yss, length ys == m]\n  where yss = caminos x\n        m   = minimum (map length yss)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la librer\u00eda Data.Tree se definen los \u00e1rboles y los bosques como sigue data Tree a = Node a (Forest a) type Forest a = [Tree a] Se pueden definir \u00e1rboles. Por ejemplo, ej = Node 3 [Node 5 [Node 9 []], Node 7 []] Y se pueden dibujar con la funci\u00f3n drawTree. Por ejemplo,&#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":[7],"tags":[269,8,58,30,282,183,28,10,83,340,89,11,6,236],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3492"}],"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=3492"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3492\/revisions"}],"predecessor-version":[{"id":3532,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3492\/revisions\/3532"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3492"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3492"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3492"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}