{"id":7764,"date":"2023-01-03T06:00:06","date_gmt":"2023-01-03T04:00:06","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7764"},"modified":"2022-12-28T18:30:59","modified_gmt":"2022-12-28T16:30:59","slug":"03-ene-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/03-ene-23\/","title":{"rendered":"\u00c1rbol de factorizaci\u00f3n"},"content":{"rendered":"<p>Los divisores medios de un n\u00famero son los que ocupan la  media entre los divisores de n, ordenados de menor a mayor. Por ejemplo, los divisores de 60 son [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60] y sus divisores medios son 6 y 10. Para los n\u00fameros que son cuadrados perfectos, sus divisores medios de son sus ra\u00edces cuadradas; por ejemplos, los divisores medios de 9 son 3 y 3.<\/p>\n<p>El \u00e1rbol de factorizaci\u00f3n de un n\u00famero compuesto n se construye de la siguiente manera:<\/p>\n<ul>\n<li>la ra\u00edz es el n\u00famero n,<\/li>\n<li>la rama izquierda es el \u00e1rbol de factorizaci\u00f3n de su divisor medio menor y<\/li>\n<li>la rama derecha es el \u00e1rbol de factorizaci\u00f3n de su divisor medio mayor<\/li>\n<\/ul>\n<p>Si el n\u00famero es primo, su \u00e1rbol de factorizaci\u00f3n s\u00f3lo tiene una hoja con dicho n\u00famero. Por ejemplo, el \u00e1rbol de factorizaci\u00f3n de 60 es<\/p>\n<pre lang=\"text\">\n       60\n      \/  \\\n     6    10\n    \/ \\   \/ \\\n   2   3 2   5\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   arbolFactorizacion :: Int -> Arbol\n<\/pre>\n<p>tal que <code>arbolFactorizacion n<\/code> es el \u00e1rbol de factorizaci\u00f3n de <code>n<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   arbolFactorizacion 60 == N 60 (N 6 (H 2) (H 3)) (N 10 (H 2) (H 5))\n   arbolFactorizacion 45 == N 45 (H 5) (N 9 (H 3) (H 3))\n   arbolFactorizacion 7  == H 7\n   arbolFactorizacion 9  == N 9 (H 3) (H 3)\n   arbolFactorizacion 14 == N 14 (H 2) (H 7)\n   arbolFactorizacion 28 == N 28 (N 4 (H 2) (H 2)) (H 7)\n   arbolFactorizacion 84 == N 84 (H 7) (N 12 (H 3) (N 4 (H 2) (H 2)))\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ndata Arbol = H Int\n           | N Int Arbol Arbol\n  deriving (Eq, Show)\n\narbolFactorizacion1 :: Int -> Arbol\narbolFactorizacion1 n\n  | esPrimo n = H n\n  | otherwise = N n (arbolFactorizacion1 x) (arbolFactorizacion1 y)\n  where (x,y) = divisoresMedio n\n\n-- (esPrimo n) se verifica si n es primo. Por ejemplo,\n--    esPrimo 7  ==  True\n--    esPrimo 9  ==  False\nesPrimo :: Int -> Bool\nesPrimo n = divisores n == [1,n]\n\n-- (divisoresMedio n) es el par formado por los divisores medios de\n-- n. Por ejemplo,\n--    divisoresMedio 30  ==  (5,6)\n--    divisoresMedio  7  ==  (1,7)\n--    divisoresMedio 16  ==  (4,4)\ndivisoresMedio :: Int -> (Int,Int)\ndivisoresMedio n = (n `div` x,x)\n  where xs = divisores n\n        x  = xs !! (length xs `div` 2)\n\n-- (divisores n) es la lista de los divisores de n. Por ejemplo,\n--    divisores 30  ==  [1,2,3,5,6,10,15,30]\ndivisores :: Int -> [Int]\ndivisores n = [x | x <- [1..n], n `rem` x == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\narbolFactorizacion2 :: Int -> Arbol\narbolFactorizacion2 n\n  | x == 1    = H n\n  | otherwise = N n (arbolFactorizacion2 x) (arbolFactorizacion2 y)\n  where (x,y) = divisoresMedio n\n\n-- (divisoresMedio2 n) es el par formado por los divisores medios de\n-- n. Por ejemplo,\n--    divisoresMedio2 30  ==  (5,6)\n--    divisoresMedio2  7  ==  (1,7)\ndivisoresMedio2 :: Int -> (Int,Int)\ndivisoresMedio2 n = (n `div` x,x)\n  where m = ceiling (sqrt (fromIntegral n))\n        x = head [y | y <- [m..n], n `rem` y == 0]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_arbolFactorizacion :: Int -> Property\nprop_arbolFactorizacion n =\n  n > 1 ==> arbolFactorizacion1 n == arbolFactorizacion2 n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_arbolFactorizacion\n--    +++ OK, passed 100 tests; 162 discarded.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom dataclasses import dataclass\nfrom math import ceil, sqrt\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n@dataclass\nclass Arbol:\n    pass\n\n@dataclass\nclass H(Arbol):\n    x: int\n\n@dataclass\nclass N(Arbol):\n    x: int\n    i: Arbol\n    d: Arbol\n\n# divisores(n) es la lista de los divisores de n. Por ejemplo,\n#    divisores(30)  ==  [1,2,3,5,6,10,15,30]\ndef divisores(n: int) -> list[int]:\n    return [x for x in range(1, n + 1) if n % x == 0]\n\n# divisoresMedio(n) es el par formado por los divisores medios de\n# n. Por ejemplo,\n#    divisoresMedio(30)  ==  (5,6)\n#    divisoresMedio(7)   ==  (1,7)\n#    divisoresMedio(16)  ==  (4,4)\ndef divisoresMedio(n: int) -> tuple[int, int]:\n    xs = divisores(n)\n    x = xs[len(xs) \/\/ 2]\n    return (n \/\/ x, x)\n\n# esPrimo(n) se verifica si n es primo. Por ejemplo,\n#    esPrimo(7)  ==  True\n#    esPrimo(9)  ==  False\ndef esPrimo(n: int) -> bool:\n    return divisores(n) == [1, n]\n\ndef arbolFactorizacion1(n: int) -> Arbol:\n    if esPrimo(n):\n        return H(n)\n    (x, y) = divisoresMedio(n)\n    return N(n, arbolFactorizacion1(x), arbolFactorizacion1(y))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# divisoresMedio2(n) es el par formado por los divisores medios de\n# n. Por ejemplo,\n#    divisoresMedio2(30) ==  (5,6)\n#    divisoresMedio2(7)  ==  (1,7)\n#    divisoresMedio2(16) ==  (4,4)\ndef divisoresMedio2(n: int) -> tuple[int, int]:\n    m = ceil(sqrt(n))\n    x = [y for y in range(m, n + 1) if n % y == 0][0]\n    return (n \/\/ x, x)\n\ndef arbolFactorizacion2(n: int) -> Arbol:\n    if esPrimo(n):\n        return H(n)\n    (x, y) = divisoresMedio2(n)\n    return N(n, arbolFactorizacion2(x), arbolFactorizacion2(y))\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=2, max_value=200))\ndef test_arbolFactorizacion(n: int) -> None:\n    assert arbolFactorizacion1(n) == arbolFactorizacion2(n)\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q arbol_de_factorizacion.py\n#    1 passed in 0.14s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Los divisores medios de un n\u00famero son los que ocupan la media entre los divisores de n, ordenados de menor a mayor. Por ejemplo, los divisores de 60 son [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60] y sus divisores medios son 6 y 10. Para los n\u00fameros que son cuadrados&#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":[581],"tags":[269],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7764"}],"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=7764"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7764\/revisions"}],"predecessor-version":[{"id":7766,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7764\/revisions\/7766"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7764"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7764"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7764"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}