Menu Close

Día: 2 abril, 2021

Antiimagen de función creciente

Una función f de los números naturales en los números naturales es estrictamente creciente si para cualquier par de números x, y tales que x < y se verifica que f(x) < f(y). La antiimagen por f de un número natural t es el número natural x tal que f(x) = t. No todos los números tienen antiimiagen por f, pero en caso de tenerla es única.

Definir la función

   antiimagen :: (Integer -> Integer) -> Integer -> Maybe Integer

tal que, suponiendo que f es una función creciente de los números naturales en los números naturales, (antiimagen f t) es justamente la antiimagen por f de t, si existe y es Nothing, en caso contrario. Por ejemplo,

   antiimagen (\x -> 2*x^2-3) 47  ==  Just 5
   antiimagen (\x -> 2*x^2-3) 48  ==  Nothing
   antiimagen (\x -> 2^x) 1024    ==  Just 10
   antiimagen (2^) 1024           ==  Just 10
   antiimagen (2^) (2^(10^7))     ==  Just 10000000
   antiimagen (2^) (1+2^(10^7))   ==  Nothing

Soluciones

import Data.Maybe (listToMaybe)
 
-- 1ª solución
-- ===========
 
antiimagen :: (Integer -> Integer) -> Integer -> Maybe Integer
antiimagen f t =
  listToMaybe [x | x <- [0..t], f x == t]
 
-- 2ª solución
-- ===========
 
antiimagen2 :: (Integer -> Integer) -> Integer -> Maybe Integer
antiimagen2 f t = busqueda (0,t)
  where busqueda (a,b) = listToMaybe [x | x <- [a..b], f x == t]
 
-- 3ª solución
-- ===========
 
antiimagen3 :: (Integer -> Integer) -> Integer -> Maybe Integer
antiimagen3 f t = busqueda (0,t)
  where busqueda (a,b)
          | a > b     = Nothing
          | t < f m   = busqueda (a,m-1)
          | t == f m  = Just m
          | otherwise = busqueda (m+1,b)
          where m = (a+b) `div` 2
 
-- 4ª solución
-- ===========
 
antiimagen4 :: (Integer -> Integer) -> Integer -> Maybe Integer
antiimagen4 f t | f x == t  = Just x
                | otherwise = Nothing
  where x = busqueda (cotas f t)
        busqueda (a,b) = head [x | x <- [a+1..b], t <= f x]
 
-- (cotas f t) es un par (a,b) de potencias consecutivas de 2 tal que la
-- antiimagen de t por f está en el intevalo [a+1,b]. Por ejemplo,
--    cotas (\x -> 2*x^2-3) 47  ==  (4,8)
--    cotas (\x -> 2^x) 1024    ==  (8,16)
cotas :: (Integer -> Integer) -> Integer -> (Integer, Integer)
cotas f t | t <= f 0  = (-1,0)
          | otherwise = (b `div` 2, b)
  where b = until done (*2) 1
        done b = t <= f b
 
-- 5ª solución
-- ===========
 
antiimagen5 :: (Integer -> Integer) -> Integer -> Maybe Integer
antiimagen5 f t | f x == t  = Just x
                | otherwise = Nothing
  where x = busqueda (cotas f t)
        busqueda (a,b) | a+1 == b  = b
                       | t <= f m  = busqueda (a,m)
                       | otherwise = busqueda (m,b)
          where m = (a+b) `div`  2
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> antiimagen (2^) (2^30)
--    Just 30
--    (0.01 secs, 142,728 bytes)
--    λ> antiimagen2 (2^) (2^30)
--    Just 30
--    (0.01 secs, 142,784 bytes)
--    λ> antiimagen3 (2^) (2^30)
--    Just 30
--    (8.05 secs, 335,820,048 bytes)
--    λ> antiimagen4 (2^) (2^30)
--    Just 30
--    (0.01 secs, 133,984 bytes)
--    λ> antiimagen5 (2^) (2^30)
--    Just 30
--    (0.02 secs, 121,816 bytes)
--
--    λ> antiimagen (2^) (2^50000)
--    Just 50000
--    (1.29 secs, 673,789,160 bytes)
--    λ> antiimagen2 (2^) (2^50000)
--    Just 50000
--    (1.28 secs, 673,791,368 bytes)
--    λ> antiimagen4 (2^) (2^50000)
--    Just 50000
--    (0.84 secs, 342,311,360 bytes)
--    λ> antiimagen5 (2^) (2^50000)
--    Just 50000
--    (0.01 secs, 549,688 bytes)
--
--    λ> antiimagen4 (2^) (2^100000)
--    Just 100000
--    (4.37 secs, 1,210,476,848 bytes)
--    λ> antiimagen5 (2^) (2^100000)
--    Just 100000
--    (0.01 secs, 918,096 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>