Antiimágenes de funciones crecientes bidimensionales
Una función f de pares de números naturales en números naturales es estrictamente creciente en ambos argumentos si
- para x1 < x2, se tiene f(x1,y) < f(x1,y), para todo y y
- para y1 < y2, se tiene f(x,y1) < f(x,y2), para todo x.
Por ejemplo, la función f definida por f(x,y) = x^2+3^y es creciente en ambos argumentos.
Las antiimágenes por f de t son los pares (x,y) tales que f(x,y) = t. Por ejemplo, las antimágenes por f(x,y) = x^2+3^y de 82 son los pares (1,4) y (9,0).
Definir la función
1 |
antiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)] |
tal que (antiimagenes f t) es la lista de las antiimágenes por f de t, donde se supone que f es una función de pares de números naturales en números naturales que es estrictamente creciente en ambos argumentos. Por ejemplo,
1 2 |
antiimagenes (\(x,y) -> x^2+3^y) 82 == [(1,4),(9,0)] antiimagenes (\(x,y) -> x^2+3^y) 387421785 == [(36,18)] |
Soluciones
[schedule expon=’2021-04-12′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 12 de abril.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
[/schedule]
[schedule on=’2021-04-12′ at=»06:00″]
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 77 78 79 80 81 82 83 84 85 86 |
-- 1ª solución -- =========== antiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)] antiimagenes f t = [(x,y) | x <- [0..t], y <- [0..t ], f (x,y) == t] -- 2ª solución -- =========== antiimagenes2 :: Integral a => ((a,a) -> a) -> a -> [(a,a)] antiimagenes2 f t = antiimagenesEn (0,t) where antiimagenesEn (a,b) = [(x,y) | x <- [a..t], y <- [b,b-1..0], f (x,y) == t] -- 3ª solución -- =========== antiimagenes3 :: Integral a => ((a,a) -> a) -> a -> [(a,a)] antiimagenes3 f t = antiimagenesEn (0,t) where antiimagenesEn (a,b) | a > t || b < 0 = [] | c < t = antiimagenesEn (a+1,b) | c == t = (a,b) : antiimagenesEn (a+1,b-1) | c > t = antiimagenesEn (a,b-1) where c = f (a,b) -- 3ª solución -- =========== antiimagenes4 :: Integral a => ((a,a) -> a) -> a -> [(a,a)] antiimagenes4 f t = desde (0,p) (q,0) where p = menor (-1,t) (\ y -> f (0,y)) t q = menor (-1,t) (\ x -> f (x,0)) t desde (x1,y1) (x2,y2) | x2 < x1 || y1 < y2 = [] | y1 - y <= x2 - x1 = fila x | otherwise = columna y where x = menor (x1-1,x2) (\ x -> f (x,r)) t y = menor (y2-1,y1) (\ y -> f (c,y)) t c = (x1 + x2) `div` 2 r = (y1 + y2) `div` 2 fila x | z < t = desde (x1,y1) (x2,r+1) | z == t = (x,r) : desde (x1,y1) (x-1,r+1) ++ desde (x+1,r-1) (x2,y2) | z > t = desde (x1,y1) (x-1,r+1) ++ desde (x,r-1) (x2,y2) where z = f (x,r) columna y | z < t = desde (c+1,y1) (x2,y2) | z == t = (c,y) : desde (x1,y1) (c-1,y+1) ++ desde (c+1,y-1) (x2,y2) | z > t = desde (x1,y1) (c-1,y) ++ desde (c+1,y-1) (x2,y2) where z = f (c, y) -- (menor (a,b) f t), suponiendo que t <= f b, es el menor x enel -- intervalo (a,b] tal que t <= f x. menor :: Integral a => (a,a) -> (a -> a) -> a -> a menor (a,b) f t | a + 1 == b = b | t <= f m = menor (a, m) f t | otherwise = menor (m, b) f t where m = (a + b) `div` 2 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> antiimagenes (\(x,y) -> x^2+3^y) 2383 -- [(14,7)] -- (15.63 secs, 26,904,500,208 bytes) -- λ> antiimagenes2 (\(x,y) -> x^2+3^y) 2383 -- [(14,7)] -- (16.37 secs, 26,950,312,440 bytes) -- λ> antiimagenes3 (\(x,y) -> x^2+3^y) 2383 -- [(14,7)] -- (0.03 secs, 11,892,160 bytes) -- λ> antiimagenes4 (\(x,y) -> x^2+3^y) 2383 -- [(14,7)] -- (0.01 secs, 277,696 bytes) -- -- λ> antiimagenes3 (\(x,y) -> x^2+3^y) 59449 -- [(20,10)] -- (3.77 secs, 1,329,803,208 bytes) -- λ> antiimagenes4 (\(x,y) -> x^2+3^y) 59449 -- [(20,10)] -- (0.03 secs, 400,400 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>
[/schedule]