Inversa del factorial

PorJosé A. Alonso 16-enero-201726-marzo-2022

Definir la función

   inversaFactorial :: Integer -> Maybe Integer

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,

   inversaFactorial 24  ==  Just 4
   inversaFactorial 25  ==  Nothing

1 2	inversaFactorial 24 == Just 4 inversaFactorial 25 == Nothing

Soluciones

-- 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)

-- 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)

9 Comentarios

inversaFactorial x = find (x==) $ takeWhile (x>=) $ factoriales
               where factoriales = map (fst) $ iterate p (1,1)
                     p (a,b) = (a*b, b+1)

inversaFactorial x = find (x==) $ takeWhile (x>=) $ factoriales

where factoriales = map (fst) $ iterate p (1,1)

p (a,b) = (a*b, b+1)

Responder

inversaFactorial :: Integer -> Maybe Integer
inversaFactorial x = find (q x) $ takeWhile (p x) [0..]
  where p x a       = x >= factorial a
        q x a       = x == factorial a
        factorial a = product [1..a]

inversaFactorial :: Integer -> Maybe Integer

inversaFactorial x = find (q x) $ takeWhile (p x) [0..]

where p x a = x >= factorial a

q x a = x == factorial a

factorial a = product [1..a]

Responder

inversaFactorial :: Integer -> Maybe Integer
inversaFactorial n = aux (zip [1..] (scanl1 (*) [1..]))
  where aux (x:xs) | snd x == n = Just (fst x) 
                   | snd x > n = Nothing
                   | otherwise = aux xs

inversaFactorial :: Integer -> Maybe Integer

inversaFactorial n = aux (zip [1..] (scanl1 (*) [1..]))

where aux (x:xs) | snd x == n = Just (fst x)

| snd x > n = Nothing

| otherwise = aux xs

Responder

inversaFactorial :: Integer -> Maybe Integer
inversaFactorial n = aux n [1..]
  where aux n (x:xs) | x == n         = Just x
                     | n `mod` x /= 0 = Nothing
                     | otherwise      = aux (n `div` x) xs

inversaFactorial :: Integer -> Maybe Integer

inversaFactorial n = aux n [1..]

where aux n (x:xs) | x == n = Just x

| n `mod` x /= 0 = Nothing

| otherwise = aux (n `div` x) xs

Responder

Se podría añadir un par de casos de prueba:

> inversaFactorial (product [1..10000])
Just 10000
(0.16 secs, 168,128,296 bytes)
> inversaFactorial (1 + product [1..10000])
Nothing
(0.09 secs, 97,577,040 bytes)

> inversaFactorial (product [1..10000])

Just 10000

(0.16 secs, 168,128,296 bytes)

> inversaFactorial (1 + product [1..10000])

Nothing

(0.09 secs, 97,577,040 bytes)

Responder

import Data.List

factorial 0 = 1
factorial 1 = 1
factorial n = n * factorial (n-1)

factoriales = [factorial n | n <- [0..]]

esFactorial n | n `elem` listaFactoriales n = True
              | otherwise = False

listaFactoriales n = takeWhile (<= n) factoriales

factor n = head [x | x <- [0..n], factorial x == n]

inversaFactorial :: Integer -> Maybe Integer
inversaFactorial n | esFactorial n = Just (factor n)
                   | otherwise = Nothing

import Data.List

factorial 0 = 1

factorial 1 = 1

factorial n = n * factorial (n-1)

factoriales = [factorial n | n <- [0..]]

esFactorial n | n `elem` listaFactoriales n = True

| otherwise = False

listaFactoriales n = takeWhile (<= n) factoriales

factor n = head [x | x <- [0..n], factorial x == n]

inversaFactorial :: Integer -> Maybe Integer

inversaFactorial n | esFactorial n = Just (factor n)

| otherwise = Nothing

Responder

inversaFactorial :: Integer -> Maybe Integer
inversaFactorial n = inversaFactorialaux 1 2 n
  where
    inversaFactorialaux x i n
      | x == n    = Just (i-1)
      | x > n     = Nothing 
      | otherwise = inversaFactorialaux (x*i) (i+1) n

inversaFactorial :: Integer -> Maybe Integer

inversaFactorial n = inversaFactorialaux 1 2 n

where

inversaFactorialaux x i n

| x == n = Just (i-1)

| x > n = Nothing

| otherwise = inversaFactorialaux (x*i) (i+1) n

Responder

inversaFactorial :: Integer -> Maybe Integer
inversaFactorial = aux 1
 where aux n p | p == n         = Just p
               | n `mod` p /= 0 = Nothing
               | otherwise      = aux (n `div` p) (p+1)

inversaFactorial :: Integer -> Maybe Integer

inversaFactorial = aux 1

where aux n p | p == n = Just p

| n `mod` p /= 0 = Nothing

| otherwise = aux (n `div` p) (p+1)

Responder

Alejandro dice:

19-enero-2017 a las 14:25

La definición falla para los ejemplos propuestos. Por ejemplo,

λ> inversaFactorial 24 Nothing

1
2

λ> inversaFactorial 24
Nothing

Responder

Inversa del factorial

Soluciones

9 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

9 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico