Definir la funci\u00f3n<\/p>\n
\n puntos :: Integer -> [(Integer,Integer)]\n<\/pre>\ntal que (puntos n) es la lista de los puntos (x,y) con coordenadas enteras de
\nla cuadr\u00edcula [1..n]x[1..n] (es decir, 1 \u2264 x,y \u2264 n) tales que |x\u00b2-xy-y\u00b2| = 1. Por ejemplo,<\/p>\n
\n length (puntos 10) == 5\n length (puntos 100) == 10\n length (puntos 1000) == 15\n length (puntos (10^50000)) == 239249\n<\/pre>\nSoluciones<\/h4>\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\npuntos1 :: Integer -> [(Integer,Integer)]\npuntos1 n =\n [(x,y) | x <- [1..n],\n y <- [1..n],\n abs (x^2-x*y-y^2) == 1] \n\n-- 2\u00aa definici\u00f3n\n-- =============\n\n-- Calculando algunos elementos\n-- \u03bb> puntos1 10\n-- [(1,1),(2,1),(3,2),(5,3),(8,5)]\n-- \u03bb> puntos1 20\n-- [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8)]\n-- \u03bb> puntos1 100\n-- [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8),(21,13),(34,21),(55,34),(89,55)]\n-- \u03bb> puntos1 89\n-- [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8),(21,13),(34,21),(55,34),(89,55)]\n-- se observa una ley de construcci\u00f3n de cada elemento a partir del anterior.\n\npuntos2 :: Integer -> [(Integer,Integer)]\npuntos2 n = takeWhile menor (iterate siguiente (1,1))\n where siguiente (x,y) = (x+y,x)\n menor (x,y) = x <= n\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\n-- Se observa que la lista de las segundas componentes\n-- 1,1,2,3,5,8,13,21,34,55,89,...\n-- y la lista de las primeras componentes es el resto de la segunda. \n\npuntos3 :: Integer -> [(Integer,Integer)]\npuntos3 n = zip (tail xs) xs\n where xs = takeWhile (<=n) fibonacci\n\n-- fibonacci es la sucesi\u00f3n de Fibonacci. Por ejemplo,\n-- take 11 fibonacci == [1,1,2,3,5,8,13,21,34,55,89]\nfibonacci :: [Integer]\nfibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> length (puntos1 (10^3))\n-- 15\n-- (7.96 secs, 1,092,368,200 bytes)\n-- \u03bb> length (puntos2 (10^3))\n-- 15\n-- (0.02 secs, 0 bytes)\n-- \n-- \u03bb> length (puntos2 (10^30000))\n-- 143549\n-- (1.14 secs, 974,239,544 bytes)\n-- \u03bb> length (puntos3 (10^30000))\n-- 143549\n-- (3.28 secs, 967,206,560 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Definir la funci\u00f3n puntos :: Integer -> [(Integer,Integer)] tal que (puntos n) es la lista de los puntos (x,y) con coordenadas enteras de la cuadr\u00edcula [1..n]x[1..n] (es decir, 1 \u2264 x,y \u2264 n) tales que |x\u00b2-xy-y\u00b2| = 1. Por ejemplo, length (puntos 10) == 5 length (puntos 100) == 10 length (puntos 1000) == 15…<\/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":[4],"tags":[130,8,50,11,6,45,34,255,9,76],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1948"}],"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=1948"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1948\/revisions"}],"predecessor-version":[{"id":1985,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1948\/revisions\/1985"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1948"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1948"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1948"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}