El m\u00ednimo n\u00famero de divisiones por 2, 3 \u00f3 5 que hay que realizar igualar 15 y 20 es 6. En efecto, 15 se reduce a 5 dividi\u00e9ndolo por 3 y 20 se reduce a 5 divi\u00e9ndolo dos veces por 2.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n minimoNumeroDivisiones :: Integer -> Integer -> Maybe Int\n<\/pre>\ntal que (minimoNumeroDivisiones x y) es justamente el m\u00ednimo n\u00famero de divisiones por 2, 3 \u00f3 5 que hay que realizar para igualar x e y, o Nothing si no se pueden igualar. Por ejemplo,<\/p>\n
\n minimoNumeroDivisiones 15 20 == Just 3\n minimoNumeroDivisiones 15 15 == Just 0\n minimoNumeroDivisiones 15 16 == Just 6\n minimoNumeroDivisiones 15 17 == Nothing\n minimoNumeroDivisiones (10^99) 21 == Nothing\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (group, intersect, nub, sort)\nimport Data.Maybe (fromJust, isNothing, listToMaybe)\nimport Data.Numbers.Primes (primeFactors)\nimport Data.Tree (Tree (Node), flatten, levels)\nimport Test.QuickCheck (Property, (==>), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nminimoNumeroDivisiones :: Integer -> Integer -> Maybe Int\nminimoNumeroDivisiones x y\n | isNothing a = Nothing\n | otherwise = Just (fst (fromJust a))\n where a = minimoNumeroDivisionesAux x y\n\n-- La definici\u00f3n anterior se puede simplificar\nminimoNumeroDivisiones' :: Integer -> Integer -> Maybe Int\nminimoNumeroDivisiones' x y =\n Just fst <*> minimoNumeroDivisionesAux x y\n\n-- (minimoNumeroDivisiones x y) es justamente el par formado por el\n-- m\u00ednimo n\u00famero de divisiones por 2, 3 \u00f3 5 que hay que realizar para\n-- igualar x e y junto con el n\u00famero al que se reducen, o Nothing si no\n-- se pueden igualar. Por ejemplo,\n-- minimoNumeroDivisionesAux 15 20 == Just (3,5)\n-- minimoNumeroDivisionesAux 15 15 == Just (0,15)\n-- minimoNumeroDivisionesAux 15 16 == Just (6,1)\n-- minimoNumeroDivisionesAux 15 17 == Nothing\nminimoNumeroDivisionesAux :: Integer -> Integer -> Maybe (Int,Integer)\nminimoNumeroDivisionesAux x y\n | null as = Nothing\n | otherwise = Just (head as)\n where as = sort [(m+n,z) | (z,(m,n)) <- minimasProfundidadesComunes x y]\n\n-- La definici\u00f3n anterior se puede simplificar\nminimoNumeroDivisionesAux2 :: Integer -> Integer -> Maybe (Int,Integer)\nminimoNumeroDivisionesAux2 x y =\n listToMaybe (sort [(m+n,z) | (z,(m,n)) <- minimasProfundidadesComunes x y])\n\n-- (arbolDivisiones x) es el \u00e1rbol de las divisiones enteras de x entre\n-- 2, 3 \u00f3 5. Por ejemplo,\n-- \u03bb> putStrLn (drawTree (fmap show (arbolDivisiones 30)))\n-- 30\n-- |\n-- +- 15\n-- | |\n-- | +- 5\n-- | | |\n-- | | `- 1\n-- | |\n-- | `- 3\n-- | |\n-- | `- 1\n-- |\n-- +- 10\n-- | |\n-- | +- 5\n-- | | |\n-- | | `- 1\n-- | |\n-- | `- 2\n-- | |\n-- | `- 1\n-- |\n-- `- 6\n-- |\n-- +- 3\n-- | |\n-- | `- 1\n-- |\n-- `- 2\n-- |\n-- `- 1\narbolDivisiones :: Integer -> Tree Integer\narbolDivisiones x =\n Node x (map arbolDivisiones (divisiones x))\n\n-- (divisiones x) es la lista de las divisiones enteras de x entre 2, 3\n-- y 5. Por ejemplo,\n-- divisiones 30 == [15,10,6]\n-- divisiones 15 == [5,3]\ndivisiones :: Integer -> [Integer]\ndivisiones x =\n [x `div` y | y <- [2,3,5], x `mod` y == 0]\n\n-- (nodos a) es el conjunto de nodos del \u00e1rbol a. Por ejemplo,\n-- nodos (Node 2 [Node 2 [], Node 5 []]) == [2,5]\n-- nodos (arbolDivisiones 30) == [30,15,5,1,3,10,2,6]\nnodos :: Tree Integer -> [Integer]\nnodos = nub . flatten\n\n-- (divisionesComunes x y) es la lista de los nodos comunes de los\n-- \u00e1rboles de las divisiones de x e y entre 2, 3 \u00f3 5. Por ejemplo,\n-- divisionesComunes 15 20 == [5,1]\ndivisionesComunes :: Integer -> Integer -> [Integer]\ndivisionesComunes x y =\n nodos (arbolDivisiones x) `intersect` nodos (arbolDivisiones y)\n\n-- (minimaProfundidad x ns) es justamente la m\u00ednima produndidad\n-- donde aparece x en el \u00e1rbol ns, si aparece y Nothing, en caso\n-- contrario. Por ejemplo,minimaProfundidad :: Ord a => a -> Tree a -> Maybe Int\n-- \u03bb> minimaProfundidad 3 (Node 1 [Node 6 [],Node 3 [Node 1 []]])\n-- Just 1\n-- \u03bb> minimaProfundidad 4 (Node 1 [Node 6 [],Node 3 [Node 1 []]])\n-- Nothing\nminimaProfundidad :: Ord a => a -> Tree a -> Maybe Int\nminimaProfundidad x ns =\n listToMaybe [z | (z,ys) <- zip [0..] (levels ns), x `elem` ys]\n\n-- (minimasProfundidadesComunes x e y) es la lista de pares formadas por\n-- los nodos comunes de los \u00e1rboles de las divisiones de x e y entre 2,\n-- 3 \u00f3 5 junto con las m\u00ednimas profundidades en cada uno de los\n-- \u00e1rboles. Por ejemplo,\n-- minimasProfundidadesComunes 15 20 == [(5,(1,2)),(1,(2,3))]\n-- minimasProfundidadesComunes 15 22 == []\nminimasProfundidadesComunes :: Integer -> Integer -> [(Integer,(Int,Int))]\nminimasProfundidadesComunes x1 x2 =\n [(c,(fromJust (minimaProfundidad c a1), fromJust (minimaProfundidad c a2)))\n | c <- cs]\n where a1 = arbolDivisiones x1\n a2 = arbolDivisiones x2\n cs = divisionesComunes x1 x2\n\n-- Propiedad\n-- =========\n\n-- El m\u00ednimo n\u00famero de divisiones se alcanza en el m\u00e1ximo com\u00fan divisor.\nprop_minimoNumeroDivisiones :: Integer -> Integer -> Property\nprop_minimoNumeroDivisiones x y =\n x > 0 && y > 0 ==>\n isNothing a || snd (fromJust a) == gcd x y\n where a = minimoNumeroDivisionesAux x y\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_minimoNumeroDivisiones\n-- +++ OK, passed 100 tests.\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nminimoNumeroDivisiones2 :: Integer -> Integer -> Maybe Int\nminimoNumeroDivisiones2 x y\n | as' == bs' = Just (sum [abs (a - b) | (a,b) <- zip as bs])\n | otherwise = Nothing\n where (as,as') = factorizacion x\n (bs,bs') = factorizacion y\n\n-- (factorizaci\u00f3n n) es la lista de pares cuya primera componente es la\n-- lista de los exponentes de 2, 3 y 5 en la factorizaci\u00f3n de n y la\n-- segunda esla lista delos restantes divisores primos. Por ejemplo,\n-- factorizacion 15 == ([0,1,1],[])\n-- factorizacion 20 == ([2,0,1],[])\n-- factorizacion 17 == ([0,0,0],[17])\n-- factorizacion 147 == ([0,1,0],[7,7])\nfactorizacion :: Integer -> ([Int],[Integer])\nfactorizacion n =\n (map length [bs,cs,ds], es)\n where as = primeFactors n\n (bs,bs') = span (==2) as\n (cs,cs') = span (==3) bs'\n (ds,es) = span (==5) cs'\n\n-- Equivalencia\n-- ============\n\n-- La propies de la equivalencia de las dos definiciones es\nprop_equivalencia :: Integer -> Integer -> Property\nprop_equivalencia x y =\n x > 0 && y > 0 ==>\n minimoNumeroDivisiones x y == minimoNumeroDivisiones2 x y\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_equivalencia\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> minimoNumeroDivisiones (10^11) (3^10*7)\n-- Nothing\n-- (6.08 secs, 2,725,931,872 bytes)\n-- \u03bb> minimoNumeroDivisiones2(10^11) (3^10*7)\n-- Nothing\n-- (0.01 secs, 128,944 bytes)\n<\/pre>\nNuevas 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":"
El m\u00ednimo n\u00famero de divisiones por 2, 3 \u00f3 5 que hay que realizar igualar 15 y 20 es 6. En efecto, 15 se reduce a 5 dividi\u00e9ndolo por 3 y 20 se reduce a 5 divi\u00e9ndolo dos veces por 2. Definir la funci\u00f3n minimoNumeroDivisiones :: Integer -> Integer -> Maybe Int tal que (minimoNumeroDivisiones…<\/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":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6203"}],"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=6203"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6203\/revisions"}],"predecessor-version":[{"id":6248,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6203\/revisions\/6248"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6203"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6203"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6203"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}