{"id":2062,"date":"2016-02-01T06:00:30","date_gmt":"2016-02-01T04:00:30","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2062"},"modified":"2016-02-08T08:11:49","modified_gmt":"2016-02-08T06:11:49","slug":"el-algoritmo-binario-del-mcd","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/el-algoritmo-binario-del-mcd\/","title":{"rendered":"El algoritmo binario del mcd"},"content":{"rendered":"<p>El m\u00e1ximo com\u00fan divisor (mcd) de dos n\u00fameros enteros no negativos se puede calcular mediante un <a href=\"http:\/\/bit.ly\/1JAsWsu\">algoritmo binario<\/a> basado en las siguientes propiedades:<\/p>\n<ol>\n<li>Si a,b son pares, entonces mcd(a,b) = 2*mcd(a\/2,b\/2)<\/li>\n<li>Si a es par y b impar, entonces mcd(a,b) = mcd(a\/2,b)<\/li>\n<li>Si a es impar y b par, entonces mcd(a,b) = mcd(a,b\/2)<\/li>\n<li>Si a y b son impares y a > b, entonces mcd(a,b) = mcd((a-b)\/2,b)<\/li>\n<li>Si a y b son impares y a &lt; b, entonces mcd(a,b) = mcd(a,(b-a)\/2)<\/li>\n<li>mcd(a,0) = a<\/li>\n<li>mcd(0,b) = b<\/li>\n<li>mcd(a,a) = a<\/li>\n<\/ol>\n<p>Por ejemplo, el c\u00e1lculo del mcd(660,420) es<\/p>\n<pre lang=\"text\">\n   mcd(660,420)\n   = 2*mcd(330,210)    [por 1]\n   = 2*2*mcd(165,105)  [por 1]\n   = 2*2*mcd(30,105)   [por 4]\n   = 2*2*mcd(15,105)   [por 2]\n   = 2*2*mcd(15,45)    [por 4]\n   = 2*2*mcd(15,15)    [por 4]\n   = 2*2*15            [por 8]\n   = 60\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   mcd :: Integer -> Integer -> Integer\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<p>tal que (mcd a b) es el m\u00e1ximo com\u00fan divisor de a y b calculado mediante el algoritmo binario del mcd. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   mcd 660 420  ==  60\n   mcd 3 0      ==  3\n   mcd 0 3      ==  3\n<\/pre>\n<p>Comprobar con QuickCheck que, para los enteros no negativos, las funciones mcd y gcd son equivalentes.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\nmcd :: Integer -> Integer -> Integer\nmcd a 0 = a\nmcd 0 b = b\nmcd a b | a == b           = a\n        | even a && even b = 2 * mcd (a `div` 2) (b `div` 2)\n        | even a           = mcd (a `div` 2)     b\n        | even b           = mcd a               (b `div` 2)\n        | a > b            = mcd ((a-b) `div` 2) b\n        | otherwise        = mcd a               ((b-a) `div` 2)\n\n-- Propiedad de equivalencia \nprop_mcd :: Integer -> Integer -> Bool\nprop_mcd a b = mcd a1 b1 == gcd a1 b1\n    where a1 = abs a\n          b1 = abs b\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_mcd\n--    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El m\u00e1ximo com\u00fan divisor (mcd) de dos n\u00fameros enteros no negativos se puede calcular mediante un algoritmo binario basado en las siguientes propiedades: Si a,b son pares, entonces mcd(a,b) = 2*mcd(a\/2,b\/2) Si a es par y b impar, entonces mcd(a,b) = mcd(a\/2,b) Si a es impar y b par, entonces mcd(a,b) = mcd(a,b\/2) Si a&#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":[5],"tags":[30,91,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\/2062"}],"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=2062"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2062\/revisions"}],"predecessor-version":[{"id":2089,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2062\/revisions\/2089"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2062"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2062"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2062"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}