{"id":6241,"date":"2021-04-05T06:26:58","date_gmt":"2021-04-05T04:26:58","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6241"},"modified":"2021-03-29T18:29:18","modified_gmt":"2021-03-29T16:29:18","slug":"antiimagenes-de-funciones-crecientes-bidimensionales","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/antiimagenes-de-funciones-crecientes-bidimensionales\/","title":{"rendered":"Antiim\u00e1genes de funciones crecientes bidimensionales"},"content":{"rendered":"<p>Una funci\u00f3n f de pares de n\u00fameros naturales en n\u00fameros naturales es estrictamente creciente en ambos argumentos si<\/p>\n<ul>\n<li>para x1 &lt; x2, se tiene f(x1,y) &lt; f(x1,y), para todo y y<\/li>\n<li>para y1 &lt; y2, se tiene f(x,y1) &lt; f(x,y2), para todo x.<\/li>\n<\/ul>\n<p>Por ejemplo, la funci\u00f3n f definida por f(x,y) = x^2+3^y es creciente en ambos argumentos.<\/p>\n<p>Las antiim\u00e1genes por f de t son los pares (x,y) tales que f(x,y) = t. Por ejemplo, las antim\u00e1genes por f(x,y) = x^2+3^y de 82 son los pares (1,4) y (9,0).<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   antiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)]\n<\/pre>\n<p>tal que (antiimagenes f t) es la lista de las antiim\u00e1genes por f de  t, donde se supone que f es una funci\u00f3n de pares de n\u00fameros naturales en n\u00fameros naturales que es estrictamente creciente en ambos argumentos. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   antiimagenes (\\(x,y) -> x^2+3^y) 82        ==  [(1,4),(9,0)]\n   antiimagenes (\\(x,y) -> x^2+3^y) 387421785 ==  [(36,18)]\n<\/pre>\n<h4>Soluciones<\/h4>\n<p>[schedule expon=&#8217;2021-04-12&#8242; expat=\u00bb06:00&#8243;]<\/p>\n<ul>\n<li>Las soluciones se pueden escribir en los comentarios hasta el 12 de abril.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<p>[\/schedule]<\/p>\n<p>[schedule on=&#8217;2021-04-12&#8242; at=\u00bb06:00&#8243;]<\/p>\n<pre lang=\"haskell\">\r\n-- 1\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nantiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)]\r\nantiimagenes f t =\r\n  [(x,y) | x <- [0..t], y <- [0..t ], f (x,y) == t]\r\n\r\n-- 2\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nantiimagenes2 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]\r\nantiimagenes2 f t = antiimagenesEn (0,t)\r\n  where antiimagenesEn (a,b) = [(x,y) | x <- [a..t], y <- [b,b-1..0], f (x,y) == t]\r\n\r\n-- 3\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nantiimagenes3 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]\r\nantiimagenes3 f t = antiimagenesEn (0,t)\r\n  where antiimagenesEn (a,b)\r\n          | a > t || b < 0 = []\r\n          | c < t          = antiimagenesEn (a+1,b)\r\n          | c == t         = (a,b) : antiimagenesEn (a+1,b-1)\r\n          | c > t          = antiimagenesEn (a,b-1)\r\n          where c = f (a,b)\r\n\r\n-- 3\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nantiimagenes4 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]\r\nantiimagenes4 f t = desde (0,p) (q,0) where\r\n  p = menor (-1,t) (\\ y -> f (0,y)) t\r\n  q = menor (-1,t) (\\ x -> f (x,0)) t\r\n  desde (x1,y1) (x2,y2)\r\n    | x2 < x1 || y1 < y2 = []\r\n    | y1 - y <= x2 - x1  = fila x\r\n    | otherwise          = columna y\r\n    where\r\n      x = menor (x1-1,x2) (\\ x -> f (x,r)) t\r\n      y = menor (y2-1,y1) (\\ y -> f (c,y)) t\r\n      c = (x1 + x2) `div` 2\r\n      r = (y1 + y2) `div` 2\r\n      fila x\r\n        | z < t  = desde (x1,y1) (x2,r+1)\r\n        | z == t = (x,r) : desde (x1,y1) (x-1,r+1) ++ desde (x+1,r-1) (x2,y2)\r\n        | z > t  = desde (x1,y1) (x-1,r+1) ++ desde (x,r-1) (x2,y2)\r\n        where z = f (x,r)\r\n      columna y\r\n        | z < t  = desde (c+1,y1) (x2,y2)\r\n        | z == t = (c,y) : desde (x1,y1) (c-1,y+1) ++ desde (c+1,y-1) (x2,y2)\r\n        | z > t  = desde (x1,y1) (c-1,y) ++ desde (c+1,y-1) (x2,y2)\r\n        where z = f (c, y)\r\n\r\n\r\n-- (menor (a,b) f t), suponiendo que t <= f b, es el menor x enel\r\n-- intervalo (a,b] tal que t <= f x.\r\nmenor :: Integral a => (a,a) -> (a -> a) -> a -> a\r\nmenor (a,b) f t\r\n  | a + 1 == b = b\r\n  | t <= f m   = menor (a, m) f t\r\n  | otherwise  = menor (m, b) f t\r\n  where m = (a + b) `div` 2\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n-- La comparaci\u00f3n es\r\n--    \u03bb> antiimagenes (\\(x,y) -> x^2+3^y) 2383\r\n--    [(14,7)]\r\n--    (15.63 secs, 26,904,500,208 bytes)\r\n--    \u03bb> antiimagenes2 (\\(x,y) -> x^2+3^y) 2383\r\n--    [(14,7)]\r\n--    (16.37 secs, 26,950,312,440 bytes)\r\n--    \u03bb> antiimagenes3 (\\(x,y) -> x^2+3^y) 2383\r\n--    [(14,7)]\r\n--    (0.03 secs, 11,892,160 bytes)\r\n--    \u03bb> antiimagenes4 (\\(x,y) -> x^2+3^y) 2383\r\n--    [(14,7)]\r\n--    (0.01 secs, 277,696 bytes)\r\n--\r\n--    \u03bb> antiimagenes3 (\\(x,y) -> x^2+3^y) 59449\r\n--    [(20,10)]\r\n--    (3.77 secs, 1,329,803,208 bytes)\r\n--    \u03bb> antiimagenes4 (\\(x,y) -> x^2+3^y) 59449\r\n--    [(20,10)]\r\n--    (0.03 secs, 400,400 bytes)\r\n<\/pre>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<p>[\/schedule]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Una funci\u00f3n f de pares de n\u00fameros naturales en n\u00fameros naturales es estrictamente creciente en ambos argumentos si para x1 &lt; x2, se tiene f(x1,y) &lt; f(x1,y), para todo y y para y1 &lt; y2, se tiene f(x,y1) &lt; f(x,y2), para todo x. Por ejemplo, la funci\u00f3n f definida por f(x,y) = x^2+3^y es creciente&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6241"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=6241"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6241\/revisions"}],"predecessor-version":[{"id":6244,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6241\/revisions\/6244"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6241"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6241"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6241"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}