{"id":6011,"date":"2021-01-27T06:00:42","date_gmt":"2021-01-27T04:00:42","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6011"},"modified":"2021-02-03T09:25:36","modified_gmt":"2021-02-03T07:25:36","slug":"arboles_acotados","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/arboles_acotados\/","title":{"rendered":"\u00c1rboles acotados"},"content":{"rendered":"

Los \u00e1rboles binarios se pueden representar mediante el tipo Arbol definido por<\/p>\n

\n   data Arbol a = H a\n                | N a (Arbol a) (Arbol a)\n     deriving Show\n<\/pre>\n
Por ejemplo, el \u00e1rbol<\/p>\n
\n         7\n        \/ \\\n       \/   \\\n      \/     \\\n     4       9\n    \/ \\     \/ \\\n   1   3   5   6\n<\/pre>\n
se puede representar por<\/p>\n
\n   N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))\n<\/pre>\n
Un \u00e1rbol est\u00e1 acotado por un conjunto ys si todos los valores de sus hojas y sus nodos pertenecen a ys. Por ejemplo, el \u00e1rbol anterior est\u00e1 acotado por [1..10] pero no lo est\u00e1 por [1..7].<\/p>\n
Un \u00e1rbol es monovalorado si todos sus elementos son iguales. Por ejemplo, de los siguientes \u00e1rboles s\u00f3lo son monovalorados los dos primeros<\/p>\n
\n    5          9           5          9\n   \/ \\        \/ \\         \/ \\        \/ \\\n  5   5      9   9       5   6      9   7\n                \/ \\                    \/ \\\n               9   9                  9   9\n<\/pre>\n
Definir las funciones<\/p>\n
\n   acotado :: Eq a => Arbol a -> [a] -> Bool\n   monovalorados :: Arbol -> [Arbol]\n<\/pre>\n
tales que<\/p>\n
    \n
  • (acotado a ys) se verifica si a est\u00e1 acotado por ys. Por ejemplo,<\/li>\n<\/ul>\n
    \n     acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..10] == True\n     acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..7]  == False\n<\/pre>\n
      \n
    • (monovalorado a) se verifica si a es monovalorado. Por ejemplo,<\/li>\n<\/ul>\n
      \n     monovalorado (N 5 (H 5) (H 5))              ==  True\n     monovalorado (N 5 (H 5) (H 6))              ==  False\n     monovalorado (N 9 (H 9) (N 9 (H 9) (H 9)))  ==  True\n     monovalorado (N 9 (H 9) (N 7 (H 9) (H 9)))  ==  False\n     monovalorado (N 9 (H 9) (N 9 (H 7) (H 9)))  ==  False\n<\/pre>\n
      Soluciones<\/h4>\n
      \ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a)\n  deriving Show\n\nacotado :: Eq a => Arbol a -> [a] -> Bool\nacotado (H x) ys     = x `elem` ys\nacotado (N x i d) ys = x `elem` ys && acotado i ys && acotado d ys\n\nmonovalorado :: Eq a => Arbol a -> Bool\nmonovalorado (H _) = True\nmonovalorado (N x i d) = acotado i [x] && acotado d [x]\n<\/pre>\n
      Nuevas soluciones<\/h4>\n
        \n
      • En los comentarios se pueden escribir nuevas soluciones.\n
      • El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
        Los \u00e1rboles binarios se pueden representar mediante el tipo Arbol definido por data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show Por ejemplo, el \u00e1rbol 7 \/ \\ \/ \\ \/ \\ 4 9 \/ \\ \/ \\ 1 3 5 6 se puede representar por N 7 (N…<\/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":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6011"}],"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=6011"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6011\/revisions"}],"predecessor-version":[{"id":6049,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6011\/revisions\/6049"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6011"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6011"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6011"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}