Ceros finales del factorial
Definir la función
1 |
cerosDelFactorial :: Integer -> Integer |
tal que (cerosDelFactorial n)
es el número de ceros en que termina el factorial de n
. Por ejemplo,
1 2 3 |
cerosDelFactorial 24 == 4 cerosDelFactorial 25 == 6 length (show (cerosDelFactorial (10^70000))) == 70000 |
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 |
import Data.List (genericLength) import Test.QuickCheck (Positive (Positive), quickCheck) -- 1ª solución -- =========== cerosDelFactorial1 :: Integer -> Integer cerosDelFactorial1 n = ceros (factorial n) -- (factorial n) es el factorial n. Por ejemplo, -- factorial 3 == 6 factorial :: Integer -> Integer factorial n = product [1..n] -- (ceros n) es el número de ceros en los que termina el número n. Por -- ejemplo, -- ceros 320000 == 4 ceros :: Integer -> Integer ceros n | rem n 10 /= 0 = 0 | otherwise = 1 + ceros (div n 10) -- 2ª solución -- =========== cerosDelFactorial2 :: Integer -> Integer cerosDelFactorial2 = ceros2 . factorial ceros2 :: Integer -> Integer ceros2 n = genericLength (takeWhile (=='0') (reverse (show n))) -- 3ª solución -- ============= cerosDelFactorial3 :: Integer -> Integer cerosDelFactorial3 n | n < 5 = 0 | otherwise = m + cerosDelFactorial3 m where m = n `div` 5 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_cerosDelFactorial :: Positive Integer -> Bool prop_cerosDelFactorial (Positive n) = all (== cerosDelFactorial1 n) [cerosDelFactorial2 n, cerosDelFactorial3 n] -- La comprobación es -- λ> quickCheck prop_cerosDelFactorial -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> cerosDelFactorial1 (4*10^4) -- 9998 -- (1.93 secs, 2,296,317,904 bytes) -- λ> cerosDelFactorial2 (4*10^4) -- 9998 -- (1.57 secs, 1,636,242,040 bytes) -- λ> cerosDelFactorial3 (4*10^4) -- 9998 -- (0.02 secs, 527,584 bytes) |
El código se encuentra en GitHub.