Se consideran las N primeras potencias de 2 (donde N es un n\u00famero par). Por ejemplo, para N = 4, las potencias de 2 son 1, 2, 4 y 8. Las biparticiones de dichas potencias en dos conjuntos de igual tama\u00f1o son<\/p>\n
\n ([1,2],[4,8]), ([1,4],[2,8]), ([1,8],[2,4])\n<\/pre>\nLas sumas de los elementos de las biparticiones son<\/p>\n
\n (3,12), (5,10), (9,6)\n<\/pre>\nLos valores absolutos de las diferencias de dichas sumas son<\/p>\n
\n 9, 5, 3\n<\/pre>\nEl m\u00ednimo de dichas diferencias es 3.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n minimaDiferencia :: Integer -> Integer\n<\/pre>\ntal que (minimaDiferencia n) es la m\u00ednima diferencia de las sumas las biparticiones de las n (donde n es un n\u00famero par) primeras potencias de dos conjuntos con igual n\u00famero de elementos. Por ejemplo,<\/p>\n
\n minimaDiferencia 4 == 3\n minimaDiferencia 6 == 7\n minimaDiferencia (10^9) `mod` (10^9) == 787109375\n<\/pre>\nSoluciones<\/h4>\n\nimport Test.QuickCheck\nimport Data.List ((\\\\))\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nminimaDiferencia :: Integer -> Integer\nminimaDiferencia n =\n minimum [abs (sum xs - sum ys) | (xs,ys) <- particiones n]\n\n-- (particiones n) es la lista de las particiones de las n (donde n es\n-- un n\u00famero par) de las n primeras potencias de 2 en dos conjuntos de\n-- igual tama\u00f1o. Por ejemplo,\n-- \u03bb> particiones 4\n-- [([1,2],[4,8]),([1,4],[2,8]),([1,8],[2,4]),\n-- ([2,4],[1,8]),([2,8],[1,4]),([4,8],[1,2])]\nparticiones :: Integer -> [([Integer],[Integer])]\nparticiones n =\n [(as,xs \\\\ as) | as <- kSubconjuntos xs (n `div` 2)]\n where xs = [2^k | k <- [0..n-1]]\n\n-- (kSubconjuntos xs k) es la lista de los subconjuntos de xs con k\n-- elementos. Por ejemplo,\n-- \u03bb> kSubconjuntos \"bcde\" 2\n-- [\"bc\",\"bd\",\"be\",\"cd\",\"ce\",\"de\"]\n-- \u03bb> kSubconjuntos \"bcde\" 3\n-- [\"bcd\",\"bce\",\"bde\",\"cde\"]\n-- \u03bb> kSubconjuntos \"abcde\" 3\n-- [\"abc\",\"abd\",\"abe\",\"acd\",\"ace\",\"ade\",\"bcd\",\"bce\",\"bde\",\"cde\"]\nkSubconjuntos :: [a] -> Integer -> [[a]]\nkSubconjuntos _ 0 = [[]]\nkSubconjuntos [] _ = []\nkSubconjuntos (x:xs) k =\n [x:ys | ys <- kSubconjuntos xs (k-1)] ++ kSubconjuntos xs k\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- Nota: La suma de las primeras (n-1) potencias de 2 es\n-- sum [2^i | i <- [0..n-2]] = 2^(n-1) - 1\n-- que es menor que la n-\u00e9sima potencia de 2 (es decir, 2^(n-1) porque\n-- se empieza a contar en 0). Por tanto, para que la diferencia de las\n-- suma sea m\u00ednima hay que agrupar la \u00faltima (2^(n-1) con las menores\n-- (es decir, desde 0 hasta n\/2-2).\n\nminimaDiferencia2 :: Integer -> Integer\nminimaDiferencia2 n =\n 2^(n-1) + sum [2^i | i <- [0..n `div` 2 - 2]] -\n sum [2^i | i <- [n `div` 2 - 1.. n-2]]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\n-- Nota: Sea m = n\/2 - 2. Entonces la suma de la mayor con las menores\n-- es\n-- s1 = 2^(n-1) + sum [2^i | i <- [0..m]]\n-- = 2^(n-1) + (2^(m+1)-1)\n-- y, puesto que la suma de las n primeras potencias es 2^n-1, la suma\n-- de las restantes es\n-- s2 = (2^n-1) - s1\n\nminimaDiferencia3 :: Integer -> Integer\nminimaDiferencia3 n = s1 - s2\n where m = n `div` 2 - 2\n s1 = 2^(n-1) + (2^(m+1)-1)\n s2 = (2^n-1) - s1\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\n-- Nota: Con la notaci\u00f3n de la soluci\u00f3n anterior, la m\u00ednima diferencia es\n-- s1 - s2\n-- = s1 - ((2^n-1) - s1)\n-- = 2*s1 - (2^n-1)\n-- = 2*(2^(n-1) + (2^(m+1)-1)) - (2^n-1)\n-- = 2^n + 2^(m+2) - 2 - 2^n + 1\n-- = 2^(m+2) - 1\n\nminimaDiferencia4 :: Integer -> Integer\nminimaDiferencia4 n = 2^(m+2) - 1\n where m = n `div` 2 - 2\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> minimaDiferencia 22\n-- 2047\n-- (7.75 secs, 6,597,330,816 bytes)\n-- \u03bb> minimaDiferencia2 22\n-- 2047\n-- (0.00 secs, 126,344 bytes)\n-- \u03bb> minimaDiferencia3 22\n-- 2047\n-- (0.01 secs, 107,192 bytes)\n-- \u03bb> minimaDiferencia4 22\n-- 2047\n-- (0.01 secs, 102,544 bytes)\n--\n-- \u03bb> minimaDiferencia2 (10^5) `mod` (10^50)\n-- 9602443968201967760613102289456131085235835109375\n-- (8.18 secs, 2,915,200,064 bytes)\n-- \u03bb> minimaDiferencia3 (10^5) `mod` (10^50)\n-- 9602443968201967760613102289456131085235835109375\n-- (0.01 secs, 293,640 bytes)\n-- \u03bb> minimaDiferencia4 (10^5) `mod` (10^50)\n-- 9602443968201967760613102289456131085235835109375\n-- (0.03 secs, 167,176 bytes)\n--\n-- \u03bb> minimaDiferencia3 (10^8) `mod` (10^50)\n-- 30521751870548886367615394702753936894129787109375\n-- (2.08 secs, 149,075,824 bytes)\n-- \u03bb> minimaDiferencia4 (10^8) `mod` (10^50)\n-- 30521751870548886367615394702753936894129787109375\n-- (0.41 secs, 24,929,696 bytes)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- Como la primera s\u00f3lo calcula hasta 22, se compara la primera con la\n-- cuarta para dichos valores.\nprop_equivalencia1 :: Bool\nprop_equivalencia1 =\n and [minimaDiferencia n == minimaDiferencia4 n | n <- [0,2..22]]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> prop_equivalencia1\n-- True\n\n-- La propiedad de la equivalencia de las definiciones 2, 3 y 4 es\nprop_equivalencia :: Integer -> Bool\nprop_equivalencia n =\n all (== (minimaDiferencia2 n'))\n [minimaDiferencia3 n',\n minimaDiferencia4 n']\n where n' = 2 + abs n\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_equivalencia\n-- +++ OK, passed 100 tests.\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":"
Se consideran las N primeras potencias de 2 (donde N es un n\u00famero par). Por ejemplo, para N = 4, las potencias de 2 son 1, 2, 4 y 8. Las biparticiones de dichas potencias en dos conjuntos de igual tama\u00f1o son ([1,2],[4,8]), ([1,4],[2,8]), ([1,8],[2,4]) Las sumas de los elementos de las biparticiones son (3,12),…<\/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":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6115"}],"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=6115"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6115\/revisions"}],"predecessor-version":[{"id":6168,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6115\/revisions\/6168"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6115"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6115"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6115"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}