Mínima diferencia de las sumas de las biparticiones de las N primeras potencias de dos
Se consideran las N primeras potencias de 2 (donde N es un número 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ño son
1 |
([1,2],[4,8]), ([1,4],[2,8]), ([1,8],[2,4]) |
Las sumas de los elementos de las biparticiones son
1 |
(3,12), (5,10), (9,6) |
Los valores absolutos de las diferencias de dichas sumas son
1 |
9, 5, 3 |
El mínimo de dichas diferencias es 3.
Definir la función
1 |
minimaDiferencia :: Integer -> Integer |
tal que (minimaDiferencia n) es la mínima diferencia de las sumas las biparticiones de las n (donde n es un número par) primeras potencias de dos conjuntos con igual número de elementos. Por ejemplo,
1 2 3 |
minimaDiferencia 4 == 3 minimaDiferencia 6 == 7 minimaDiferencia (10^9) `mod` (10^9) == 787109375 |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
import Test.QuickCheck import Data.List ((\\)) -- 1ª solución -- =========== minimaDiferencia :: Integer -> Integer minimaDiferencia n = minimum [abs (sum xs - sum ys) | (xs,ys) <- particiones n] -- (particiones n) es la lista de las particiones de las n (donde n es -- un número par) de las n primeras potencias de 2 en dos conjuntos de -- igual tamaño. Por ejemplo, -- λ> particiones 4 -- [([1,2],[4,8]),([1,4],[2,8]),([1,8],[2,4]), -- ([2,4],[1,8]),([2,8],[1,4]),([4,8],[1,2])] particiones :: Integer -> [([Integer],[Integer])] particiones n = [(as,xs \\ as) | as <- kSubconjuntos xs (n `div` 2)] where xs = [2^k | k <- [0..n-1]] -- (kSubconjuntos xs k) es la lista de los subconjuntos de xs con k -- elementos. Por ejemplo, -- λ> kSubconjuntos "bcde" 2 -- ["bc","bd","be","cd","ce","de"] -- λ> kSubconjuntos "bcde" 3 -- ["bcd","bce","bde","cde"] -- λ> kSubconjuntos "abcde" 3 -- ["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"] kSubconjuntos :: [a] -> Integer -> [[a]] kSubconjuntos _ 0 = [[]] kSubconjuntos [] _ = [] kSubconjuntos (x:xs) k = [x:ys | ys <- kSubconjuntos xs (k-1)] ++ kSubconjuntos xs k -- 2ª solución -- =========== -- Nota: La suma de las primeras (n-1) potencias de 2 es -- sum [2^i | i <- [0..n-2]] = 2^(n-1) - 1 -- que es menor que la n-ésima potencia de 2 (es decir, 2^(n-1) porque -- se empieza a contar en 0). Por tanto, para que la diferencia de las -- suma sea mínima hay que agrupar la última (2^(n-1) con las menores -- (es decir, desde 0 hasta n/2-2). minimaDiferencia2 :: Integer -> Integer minimaDiferencia2 n = 2^(n-1) + sum [2^i | i <- [0..n `div` 2 - 2]] - sum [2^i | i <- [n `div` 2 - 1.. n-2]] -- 3ª solución -- =========== -- Nota: Sea m = n/2 - 2. Entonces la suma de la mayor con las menores -- es -- s1 = 2^(n-1) + sum [2^i | i <- [0..m]] -- = 2^(n-1) + (2^(m+1)-1) -- y, puesto que la suma de las n primeras potencias es 2^n-1, la suma -- de las restantes es -- s2 = (2^n-1) - s1 minimaDiferencia3 :: Integer -> Integer minimaDiferencia3 n = s1 - s2 where m = n `div` 2 - 2 s1 = 2^(n-1) + (2^(m+1)-1) s2 = (2^n-1) - s1 -- 4ª solución -- =========== -- Nota: Con la notación de la solución anterior, la mínima diferencia es -- s1 - s2 -- = s1 - ((2^n-1) - s1) -- = 2*s1 - (2^n-1) -- = 2*(2^(n-1) + (2^(m+1)-1)) - (2^n-1) -- = 2^n + 2^(m+2) - 2 - 2^n + 1 -- = 2^(m+2) - 1 minimaDiferencia4 :: Integer -> Integer minimaDiferencia4 n = 2^(m+2) - 1 where m = n `div` 2 - 2 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> minimaDiferencia 22 -- 2047 -- (7.75 secs, 6,597,330,816 bytes) -- λ> minimaDiferencia2 22 -- 2047 -- (0.00 secs, 126,344 bytes) -- λ> minimaDiferencia3 22 -- 2047 -- (0.01 secs, 107,192 bytes) -- λ> minimaDiferencia4 22 -- 2047 -- (0.01 secs, 102,544 bytes) -- -- λ> minimaDiferencia2 (10^5) `mod` (10^50) -- 9602443968201967760613102289456131085235835109375 -- (8.18 secs, 2,915,200,064 bytes) -- λ> minimaDiferencia3 (10^5) `mod` (10^50) -- 9602443968201967760613102289456131085235835109375 -- (0.01 secs, 293,640 bytes) -- λ> minimaDiferencia4 (10^5) `mod` (10^50) -- 9602443968201967760613102289456131085235835109375 -- (0.03 secs, 167,176 bytes) -- -- λ> minimaDiferencia3 (10^8) `mod` (10^50) -- 30521751870548886367615394702753936894129787109375 -- (2.08 secs, 149,075,824 bytes) -- λ> minimaDiferencia4 (10^8) `mod` (10^50) -- 30521751870548886367615394702753936894129787109375 -- (0.41 secs, 24,929,696 bytes) -- Comprobación de equivalencia -- ============================ -- Como la primera sólo calcula hasta 22, se compara la primera con la -- cuarta para dichos valores. prop_equivalencia1 :: Bool prop_equivalencia1 = and [minimaDiferencia n == minimaDiferencia4 n | n <- [0,2..22]] -- La comprobación es -- λ> prop_equivalencia1 -- True -- La propiedad de la equivalencia de las definiciones 2, 3 y 4 es prop_equivalencia :: Integer -> Bool prop_equivalencia n = all (== (minimaDiferencia2 n')) [minimaDiferencia3 n', minimaDiferencia4 n'] where n' = 2 + abs n -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>