Inversa del factorial
Definir la función
|
1 |
inversaFactorial :: Integer -> Maybe Integer |
tal que (inversaFactorial x) es (Just n) si el factorial de n es x y es Nothing si no existe ningún número n tal que el factorial de n es x. Por ejemplo,
|
1 2 |
inversaFactorial 24 == Just 4 inversaFactorial 25 == Nothing |
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 |
-- 1ª definición -- ============= inversaFactorial :: Integer -> Maybe Integer inversaFactorial 1 = Just 1 inversaFactorial x = aux 2 x where aux n 1 = Just (n-1) aux n y | y `mod` n == 0 = aux (n+1) (y `div` n) | otherwise = Nothing -- 2ª definición -- ============= inversaFactorial2 :: Integer -> Maybe Integer inversaFactorial2 x | y == x = Just n |otherwise = Nothing where ((n,y):_) = dropWhile (\(k,z) -> z < x) factorialesAnotados -- factorialesAnotados es la lista de los factoriales anotados con sus -- posiciones. Por ejemplo, -- take 5 factorialesAnotados == [(0,1),(1,1),(2,2),(3,6),(4,24)] factorialesAnotados :: [(Integer, Integer)] factorialesAnotados = zip [0..] factoriales -- factoriales es la lista de los factoriales. Por ejemplo, -- take 5 factoriales == [1,1,2,6,24] factoriales :: [Integer] factoriales = 1 : scanl1 (*) [1..] -- Comparación de eficiencia -- λ> inversaFactorial (product [1..4*10^4]) -- Just 40000 -- (2.76 secs, 3,105,158,528 bytes) -- λ> inversaFactorial2 (product [1..4*10^4]) -- Just 40000 -- (2.60 secs, 3,261,722,960 bytes) -- -- λ> inversaFactorial (1 + product [1..4*10^4]) -- Nothing -- (1.80 secs, 1,626,433,432 bytes) -- λ> inversaFactorial2 (1 + product [1..4*10^4]) -- Nothing -- (2.56 secs, 3,257,388,296 bytes) |