Mayor producto de n dígitos consecutivos de un número
Definir la función
1 |
mayorProducto :: Int -> Integer -> Integer |
tal que (mayorProducto n x) es el mayor producto de n dígitos consecutivos del número x (suponiendo que x tiene al menos n dígitos). Por ejemplo,
1 2 3 4 5 6 7 |
mayorProducto 2 325 == 10 mayorProducto 5 11111 == 1 mayorProducto 5 113111 == 3 mayorProducto 5 110111 == 0 mayorProducto 5 10151112 == 10 mayorProducto 5 101511124 == 10 mayorProducto 5 (product [1..1000]) == 41472 |
Nota: Este ejercicio está basado en el problema 8 del Proyecto Euler
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 |
import Data.List (inits, tails) import Data.Char (digitToInt) -- 1ª solución -- =========== mayorProducto :: Int -> Integer -> Integer mayorProducto n x = maximum [product xs | xs <- segmentos n (digitos x)] -- (digitos x) es la lista de las digitos del número x. Por ejemplo, -- digitos 325 == [3,2,5] digitos :: Integer -> [Integer] digitos x = map (toInteger . digitToInt) (show x) -- (segmentos n xs) es la lista de los segmentos de longitud n de la -- lista xs. Por ejemplo, -- segmentos 2 [3,5,4,6] == [[3,5],[5,4],[4,6]] segmentos :: Int -> [Integer] -> [[Integer]] segmentos n xs = take (length xs - n + 1) (map (take n) (tails xs)) -- 2ª solución -- =========== mayorProducto2 :: Int -> Integer -> Integer mayorProducto2 n x = maximum (aux ns) where ns = [read [d] | d <- show x] aux xs | length xs < n = [] | otherwise = product (take n xs) : aux (tail xs) -- 3ª solución -- =========== mayorProducto3 :: Int -> Integer -> Integer mayorProducto3 n = maximum . map (product . take n) . filter ((>=n) . length) . tails . digitos -- 4ª solución -- =========== mayorProducto4 :: Int -> Integer -> Integer mayorProducto4 n = maximum . map (product . map (fromIntegral . digitToInt)) . filter ((==n) . length) . concatMap inits . tails . show -- Comparación de eficiencia -- ========================= -- λ> mayorProducto 5 (product [1..500]) -- 28224 -- (0.01 secs, 1,645,256 bytes) -- λ> mayorProducto2 5 (product [1..500]) -- 28224 -- (0.03 secs, 5,848,416 bytes) -- λ> mayorProducto3 5 (product [1..500]) -- 28224 -- (0.03 secs, 1,510,640 bytes) -- λ> mayorProducto4 5 (product [1..500]) -- 28224 -- (1.85 secs, 10,932,551,216 bytes) -- -- λ> mayorProducto 5 (product [1..7000]) -- 46656 -- (0.10 secs, 68,590,808 bytes) -- λ> mayorProducto2 5 (product [1..7000]) -- 46656 -- (1.63 secs, 157,031,432 bytes) -- λ> mayorProducto3 5 (product [1..7000]) -- 46656 -- (1.55 secs, 65,727,176 bytes) |
Pensamiento
«El control de la complejidad es la esencia de la programación.» ~ B.W. Kernigan