{"id":3304,"date":"2017-05-15T08:15:04","date_gmt":"2017-05-15T06:15:04","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3304"},"modified":"2023-08-02T13:51:19","modified_gmt":"2023-08-02T11:51:19","slug":"el-algoritmo-de-damm","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/el-algoritmo-de-damm\/","title":{"rendered":"El algoritmo de Damm"},"content":{"rendered":"<p>El <a href=\"http:\/\/bit.ly\/1SyWhFZ\">algoritmo de Damm<\/a> se usa en la detecci\u00f3n de errores en c\u00f3digos num\u00e9ricos. Es un procedimiento para obtener un d\u00edgito de control, usando la siguiente matriz, como describimos en los ejemplos<\/p>\n<pre lang=\"text\">\n     |  0   1   2   3   4   5   6   7   8   9\n   --+---------------------------------------\n   0 |  0   3   1   7   5   9   8   6   4   2\n   1 |  7   0   9   2   1   5   4   8   6   3\n   2 |  4   2   0   6   8   7   1   3   5   9\n   3 |  1   7   5   0   9   8   3   4   2   6\n   4 |  6   1   2   3   0   4   5   9   7   8\n   5 |  3   6   7   4   2   0   9   5   8   1\n   6 |  5   8   6   9   7   2   0   1   3   4\n   7 |  8   9   4   5   3   6   2   0   1   7\n   8 |  9   4   3   8   6   1   7   2   0   5\n   9 |  2   5   8   1   4   3   6   7   9   0\n<\/pre>\n<p><em>Ejemplo 1<\/em>: c\u00e1lculo del d\u00edgito de control de 572<\/p>\n<ul>\n<li>se comienza con la fila 0 y columna 5 de la matriz -> 9<\/li>\n<li>a continuaci\u00f3n, la fila 9 y columna 7 de la matriz -> 7<\/li>\n<li>a continuaci\u00f3n, la fila 7 y columna 2 de la matriz -> 4<\/li>\n<\/ul>\n<p>con lo que se llega al final del proceso. Entonces, el d\u00edgito de control de 572 es 4.<\/p>\n<p><em>Ejemplo 2<\/em>: c\u00e1lculo del d\u00edgito de control de 57260<\/p>\n<ul>\n<li>se comienza con la fila 0 y columna 5 de la matriz -> 9<\/li>\n<li>a continuaci\u00f3n, la fila 9 y columna 7 de la matriz -> 7<\/li>\n<li>a continuaci\u00f3n, la fila 9 y columna 2 de la matriz -> 4<\/li>\n<li>a continuaci\u00f3n, la fila 6 y columna 4 de la matriz -> 5<\/li>\n<li>a continuaci\u00f3n, la fila 5 y columna 0 de la matriz -> 3<\/li>\n<\/ul>\n<p>con lo que se llega al final del proceso. Entonces, el d\u00edgito de control de 57260 es 3.<\/p>\n<p>Representamos las matrices como tablas cuyos \u00edndices son pares de n\u00fameros naturales.<\/p>\n<pre lang=\"text\">\n   type Matriz a = Array (Int,Int) a\n<\/pre>\n<p>Definimos la matriz:<\/p>\n<pre lang=\"text\">\n   mDamm :: Matriz Int\n   mDamm = listArray ((0,0),(9,9)) [0,3,1,7,5,9,8,6,4,2,\n                                    7,0,9,2,1,5,4,8,6,3,\n                                    4,2,0,6,8,7,1,3,5,9,\n                                    1,7,5,0,9,8,3,4,2,6,\n                                    6,1,2,3,0,4,5,9,7,8,\n                                    3,6,7,4,2,0,9,5,8,1,\n                                    5,8,6,9,7,2,0,1,3,4,\n                                    8,9,4,5,3,6,2,0,1,7,\n                                    9,4,3,8,6,1,7,2,0,5,\n                                    2,5,8,1,4,3,6,7,9,0]\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   digitoControl :: Int -> Int\n<\/pre>\n<p>tal que (digitoControl n) es el d\u00edgito de control de n. Por ejemplo:<\/p>\n<pre lang=\"text\">\n   digitoControl 572          == 4\n   digitoControl 57260        == 3\n   digitoControl 12345689012  == 6\n   digitoControl 5724         == 0\n   digitoControl 572603       == 0\n   digitoControl 123456890126 == 0\n<\/pre>\n<p>Comprobar con QuickCheck que si a\u00f1adimos al final de un n\u00famero n su d\u00edgito de control, el d\u00edgito de control del n\u00famero que resulta siempre es 0.<\/p>\n<h4>Soluciones<\/h4>\n<p>[schedule expon=&#8217;2017-05-22&#8242; expat=\u00bb06:00&#8243;]<\/p>\n<ul>\n<li>Las soluciones se pueden escribir en los comentarios hasta el 22 de mayo.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=\u00bbhaskell\u00bb&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<p>[\/schedule]<\/p>\n<p>[schedule on=&#8217;2017-05-22&#8242; at=\u00bb06:00&#8243;]<\/p>\n<pre lang=\"haskell\">\r\n\r\nimport Data.Array\r\nimport Test.QuickCheck\r\n\r\ntype Matriz a = Array (Int,Int) a\r\n\r\nmDamm :: Matriz Int\r\nmDamm = listArray ((0,0),(9,9)) [0,3,1,7,5,9,8,6,4,2,\r\n                                 7,0,9,2,1,5,4,8,6,3,\r\n                                 4,2,0,6,8,7,1,3,5,9,\r\n                                 1,7,5,0,9,8,3,4,2,6,\r\n                                 6,1,2,3,0,4,5,9,7,8,\r\n                                 3,6,7,4,2,0,9,5,8,1,\r\n                                 5,8,6,9,7,2,0,1,3,4,\r\n                                 8,9,4,5,3,6,2,0,1,7,\r\n                                 9,4,3,8,6,1,7,2,0,5,\r\n                                 2,5,8,1,4,3,6,7,9,0]\r\n\r\n-- 1\u00aa soluci\u00f3n\r\ndigitoControl :: Int -> Int\r\ndigitoControl n = aux (digitos n) 0\r\n    where aux [] d = d\r\n          aux (x:xs) d = aux xs (mDamm ! (d,x))\r\n\r\ndigitos :: Int -> [Int]\r\ndigitos n = [read [x] | x <- show n]\r\n\r\n-- 2\u00aa soluci\u00f3n:\r\ndigitoControl2 :: Int -> Int\r\ndigitoControl2 n = last (scanl f 0 (digitos n))\r\n    where f d x = mDamm ! (d,x)\r\n\r\n-- La propiedad es\r\nprop_DC :: Int -> Property\r\nprop_DC n = n >= 0 ==> digitoControl m == 0\r\n    where m = read (show n ++ show (digitoControl n))\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_DC\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- 2\u00aa expresi\u00f3n de la propiedad\r\nprop_DC2 :: Int -> Bool\r\nprop_DC2 n = digitoControl m == 0\r\n    where m = read (show (abs n) ++ show (digitoControl (abs n)))\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_DC2\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- 3\u00aa expresi\u00f3n de la propiedad\r\nprop_DC3 :: Int -> Bool\r\nprop_DC3 n = digitoControl (10 * n1 + digitoControl n1) == 0\r\n    where n1 = abs n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_DC3\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- 4\u00aa expresi\u00f3n de la propiedad\r\nprop_DC4 :: (Positive Int) -> Bool\r\nprop_DC4 (Positive n) = \r\n    digitoControl2 (10 * n + digitoControl2 n) == 0\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci > quickCheck prop_DC4\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n<p>[\/schedule]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>El algoritmo de Damm se usa en la detecci\u00f3n de errores en c\u00f3digos num\u00e9ricos. Es un procedimiento para obtener un d\u00edgito de control, usando la siguiente matriz, como describimos en los ejemplos | 0 1 2 3 4 5 6 7 8 9 &#8211;+&#8212;&#8212;&#8212;&#8212;&#8212;&#8212;&#8212;&#8212;&#8212;&#8212;&#8212;&#8212;&#8212; 0 | 0 3 1 7 5 9 8 6 4&#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":[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\/3304"}],"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=3304"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3304\/revisions"}],"predecessor-version":[{"id":8261,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3304\/revisions\/8261"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3304"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3304"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3304"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}