{"id":2411,"date":"2016-05-05T06:00:58","date_gmt":"2016-05-05T04:00:58","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2411"},"modified":"2016-05-12T06:51:13","modified_gmt":"2016-05-12T04:51:13","slug":"numero-de-divisiones-en-el-algoritmo-de-euclides","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numero-de-divisiones-en-el-algoritmo-de-euclides\/","title":{"rendered":"N\u00famero de divisiones en el algoritmo de Euclides"},"content":{"rendered":"<p>Dados dos n\u00fameros naturales, a y b, es posible calcular su m\u00e1ximo com\u00fan divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente f\u00f3rmula:<\/p>\n<pre lang=\"text\">\n   mcd(a,b) = a,                   si b = 0\n            = b,                   si a = 0               \n            = mcd (a m\u00f3dulo b, b), si a > b\n            = mcd (a, b m\u00f3dulo a), si b >= a\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   mcdYdivisiones :: Int -> Int -> (Int,Int)\n<\/pre>\n<p>tal que (mcdYdivisiones a b) es el n\u00famero de divisiones usadas en el c\u00e1lculo del m\u00e1ximo com\u00fan divisor de a y b mediante el algoritmo de Euclides. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   mcdYdivisiones 252 198 == (18,4)\n<\/pre>\n<p>ya que los 4 divisiones del c\u00e1lculo son<\/p>\n<pre lang=\"text\">\n     mcd 252 198\n   = mcd  54 198\n   = mcd  54  36\n   = mcd  18  36\n   = mcd  18   0\n<\/pre>\n<p>Comprobar con QuickCheck que el n\u00famero de divisiones requeridas por el algoritmo de Euclides para calcular el MCD de a y b es igual o menor que cinco veces el n\u00famero de d\u00edgitos de menor de los n\u00fameros a y b.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\nimport Debug.Trace \n\nmcdYdivisiones :: Int -> Int -> (Int,Int)\nmcdYdivisiones a b = mcd a b 0\n    where mcd a 0 n = (a,n)\n          mcd 0 b n = (b,n)\n          mcd a b n | a > b     = mcd (a `mod` b) b (n+1)\n                    | otherwise = mcd a (b `mod` a) (n+1) \n\n-- La propiedad es\nprop_mcdYdivisiones :: Int -> Int -> Property\nprop_mcdYdivisiones a b =\n    a > 0 && b > 0 ==>\n      n < 5 * length (show (min a b))  \n    where (_,n) = mcdYdivisiones a b\n                 \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_mcdYdivisiones\n--    +++ OK, passed 100 tests.\n\n-- 2\u00aa definici\u00f3n (con traza)\nmcdYdivisiones2 :: Int -> Int -> (Int,Int)\nmcdYdivisiones2 a b = mcd a b 0\n    where mcd a b n\n              | trace (show a ++ \", \" ++ show b) False = undefined\n          mcd a 0 n = (a,n)\n          mcd 0 b n = (b,n)\n          mcd a b n | a > b     = mcd (a `mod` b) b (n+1)\n                    | otherwise = mcd a (b `mod` a) (n+1) \n\n-- Por ejemplo,\n--    \u03bb> mcdYdivisiones2 252 198\n--    252, 198\n--    54, 198\n--    54, 36\n--    18, 36\n--    18, 0\n--    (18,4)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Dados dos n\u00fameros naturales, a y b, es posible calcular su m\u00e1ximo com\u00fan divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente f\u00f3rmula: mcd(a,b) = a, si b = 0 = b, si a = 0 = mcd (a m\u00f3dulo b, b), si a > b = mcd (a, b&#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":[4],"tags":[89,6,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2411"}],"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=2411"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2411\/revisions"}],"predecessor-version":[{"id":2439,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2411\/revisions\/2439"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2411"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2411"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2411"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}