Mayor capicúa producto de dos números de n cifras
Un capicúa es un número que es igual leído de izquierda a derecha que de derecha a izquierda.
Definir la función
1 |
mayorCapicuaP :: Integer -> Integer |
tal que (mayorCapicuaP n) es el mayor capicúa que es el producto de dos números de n cifras. Por ejemplo,
1 2 3 4 |
mayorCapicuaP 2 == 9009 mayorCapicuaP 3 == 906609 mayorCapicuaP 4 == 99000099 mayorCapicuaP 5 == 9966006699 |
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 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 |
-- 1ª solución -- =========== mayorCapicuaP1 :: Integer -> Integer mayorCapicuaP1 n = head (capicuasP n) -- (capicuasP n) es la lista de las capicúas de 2*n cifras que -- pueden escribirse como productos de dos números de n cifras. Por -- ejemplo, Por ejemplo, -- ghci> capicuasP 2 -- [9009,8448,8118,8008,7227,7007,6776,6336,6006,5775,5445,5335, -- 5225,5115,5005,4884,4774,4664,4554,4224,4004,3773,3663,3003, -- 2992,2772,2552,2442,2332,2112,2002,1881,1771,1551,1221,1001] capicuasP n = [x | x <- capicuas n, not (null (productosDosNumerosCifras n x))] -- (capicuas n) es la lista de las capicúas de 2*n cifras de mayor a -- menor. Por ejemplo, -- capicuas 1 == [99,88,77,66,55,44,33,22,11] -- take 7 (capicuas 2) == [9999,9889,9779,9669,9559,9449,9339] capicuas :: Integer -> [Integer] capicuas n = [capicua x | x <- numerosCifras n] -- (numerosCifras n) es la lista de los números de n cifras de mayor a -- menor. Por ejemplo, -- numerosCifras 1 == [9,8,7,6,5,4,3,2,1] -- take 7 (numerosCifras 2) == [99,98,97,96,95,94,93] -- take 7 (numerosCifras 3) == [999,998,997,996,995,994,993] numerosCifras :: Integer -> [Integer] numerosCifras n = [a,a-1..b] where a = 10^n-1 b = 10^(n-1) -- (capicua n) es la capicúa formada añadiendo el inverso de n a -- continuación de n. Por ejemplo, -- capicua 93 == 9339 capicua :: Integer -> Integer capicua n = read (xs ++ (reverse xs)) where xs = show n -- (productosDosNumerosCifras n x) es la lista de los números y de n -- cifras tales que existe un z de n cifras y x es el producto de y por -- z. Por ejemplo, -- productosDosNumerosCifras 2 9009 == [99,91] productosDosNumerosCifras n x = [y | y <- numeros, mod x y == 0, div x y `elem` numeros] where numeros = numerosCifras n -- 2ª solución -- =========== mayorCapicuaP2 :: Integer -> Integer mayorCapicuaP2 n = maximum [x*y | x <- [a,a-1..b], y <- [a,a-1..b], esCapicua (x*y)] where a = 10^n-1 b = 10^(n-1) -- (esCapicua x) se verifica si x es capicúa. Por ejemplo, -- esCapicua 353 == True -- esCapicua 357 == False esCapicua :: Integer -> Bool esCapicua n = xs == reverse xs where xs = show n -- 3ª solución -- =========== mayorCapicuaP3 :: Integer -> Integer mayorCapicuaP3 n = maximum [x*y | (x,y) <- pares a b, esCapicua (x*y)] where a = 10^n-1 b = 10^(n-1) -- (pares a b) es la lista de los pares de números entre a y b de forma -- que su suma es decreciente. Por ejemplo, -- pares 9 7 == [(9,9),(8,9),(8,8),(7,9),(7,8),(7,7)] pares a b = [(x,z-x) | z <- [a1,a1-1..b1], x <- [a,a-1..b], x <= z-x, z-x <= a] where a1 = 2*a b1 = 2*b -- 4ª solución -- =========== mayorCapicuaP4 :: Integer -> Integer mayorCapicuaP4 n = maximum [x | y <- [a..b], z <- [y..b], let x = y * z, let s = show x, s == reverse s] where a = 10^(n-1) b = 10^n-1 -- 5ª solución -- =========== mayorCapicuaP5 :: Integer -> Integer mayorCapicuaP5 n = maximum [x*y | (x,y) <- pares2 b a, esCapicua (x*y)] where a = 10^(n-1) b = 10^n-1 -- (pares2 a b) es la lista de los pares de números entre a y b de forma -- que su suma es decreciente. Por ejemplo, -- pares2 9 7 == [(9,9),(8,9),(8,8),(7,9),(7,8),(7,7)] pares2 a b = [(x,y) | x <- [a,a-1..b], y <- [a,a-1..x]] -- 6ª solución -- =========== mayorCapicuaP6 :: Integer -> Integer mayorCapicuaP6 n = maximum [x*y | x <- [a..b], y <- [x..b] , esCapicua (x*y)] where a = 10^(n-1) b = 10^n-1 -- (cifras n) es la lista de las cifras de n en orden inverso. Por -- ejemplo, -- cifras 325 == [5,2,3] cifras :: Integer -> [Integer] cifras n | n < 10 = [n] | otherwise = (ultima n) : (cifras (quitarUltima n)) -- (ultima n) es la última cifra de n. Por ejemplo, -- ultima 325 == 5 ultima :: Integer -> Integer ultima n = n - (n `div` 10)*10 -- (quitarUltima n) es el número obtenido al quitarle a n su última -- cifra. Por ejemplo, -- quitarUltima 325 => 32 quitarUltima :: Integer -> Integer quitarUltima n = (n - (ultima n)) `div` 10 -- 7ª solución -- =========== mayorCapicuaP7 :: Integer -> Integer mayorCapicuaP7 n = head [x | x <- capicuas n, esFactorizable x n] -- (esFactorizable x n) se verifica si x se puede escribir como producto -- de dos números de n dígitos. Por ejemplo, -- esFactorizable 1219 2 == True -- esFactorizable 1217 2 == False esFactorizable x n = aux i x where b = 10^n-1 i = floor (sqrt (fromIntegral x)) aux i x | i > b = False | x `mod` i == 0 = x `div` i < b | otherwise = aux (i+1) x -- --------------------------------------------------------------------- -- Comparación de soluciones -- -- --------------------------------------------------------------------- -- Tiempo (en segundos) de cálculo de (mayorCapicuaP n) con las 7 -- definiciones -- +------+------+------+------+ -- | Def. | 2 | 3 | 4 | -- |------+------+------+------| -- | 1 | 0.01 | 0.13 | 1.39 | -- | 2 | 0.03 | 2.07 | | -- | 3 | 0.05 | 3.86 | | -- | 4 | 0.01 | 0.89 | | -- | 5 | 0.03 | 1.23 | | -- | 6 | 0.02 | 1.03 | | -- | 7 | 0.01 | 0.02 | 0.02 | -- +------+------+------+------+ |
https://gist.github.com/joseanpg/c254aa60adba32f8a829