Continuando con los problema propuestos por alumnos, el de hoy es el propuesto por Rafael Jim\u00e9nez.<\/p>\n
Se tiene una calle en la que las casas s\u00f3lo est\u00e1n en un lado de \u00e9sta y las casas est\u00e1n numeradas de 1 hasta n, donde n es el n\u00famero total de casas en la calle. Se dice que el n\u00famero de una casa es equilibrado si y solamente si la suma de los n\u00fameros de las casas anteriores es igual a la suma de los n\u00fameros posteriores a la casa. Por ejemplo, el n\u00famero de la 6\u00aa casa, en una calle con 8 casas, es equilibrado ya que<\/p>\n
\n 1 + 2 + 3 + 4 + 5 = 7 + 8\n<\/pre>\nDefinir la funci\u00f3n<\/p>\n
\n soluciones :: Integer -> Integer -> [(Integer,Integer)]\n<\/pre>\ntal que (soluciones x y) es la lista de pares (a,n) tales que a es el n\u00famero equilibrado de una casa en una calle con n casas y n est\u00e1 entre x e y. Por ejemplo,<\/p>\n
\n soluciones 1 500 == [(1,1),(6,8),(35,49),(204,288)]\n soluciones 1000 3000 == [(1189,1681)]\n soluciones (10^5) (10^6) == [(235416,332928)]\n soluciones (10^6) (10^7) == [(1372105,1940449)]\n (fst $ head $ soluciones (10^100) (10^101)) `mod` (10^9) == 763728460\n (fst $ head $ soluciones (10^800) (10^1000)) `mod` (10^9) == 311156546\n<\/pre>\nSoluciones<\/h4>\n\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsoluciones1 :: Integer -> Integer -> [(Integer,Integer)]\nsoluciones1 x y =\n [(n,n+m) | n <- [x..y], m <- [0..y-n], \n sum [1..n-1] == sum [n+1..n+m]]\n \n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsoluciones2 :: Integer -> Integer -> [(Integer,Integer)]\nsoluciones2 x y =\n [(n,n+m) | n <- [x..y], m <- [0..y-n], \n esSolucion (n,n+m)]\n\nesSolucion :: (Integer,Integer) -> Bool\nesSolucion (n,m) = suma (n-1) == suma m - suma n\n where suma n = n*(n+1) `div` 2\n \n-- 3\u00aa soluci\u00f3n\n-- ===========\n\n-- Con las definiciones anteriores se pueden calcular los cuatro\n-- primeros n\u00fameros de las casas equilibradas:\n-- ghci> map fst (soluciones2 1 500)\n-- [1,6,35,204]\n-- Conjeturando que el n-\u00e9simo n\u00famero p(n) se calcula mediante una\n-- recurrencia del tipo p(n)\u2004=\u2004x*p(n-1)\u2005+\u2005y*p(n-2) se tiene \n-- p(1) = 1\n-- p(2) = 6\n-- p(3) = 35 = 6x + y\n-- p(4) = 204 = 35x + 6y\n-- al resolverlo se obtiene x = 6 e y = -1. Por tanto,\n-- p(1) = 1\n-- p(2) = 6\n-- p(n) = 6*p(n-1) - p(n-2)\n--\n-- Haciendo lo mismo con las segundas componentes, \n-- ghci> map snd (soluciones2 1 2000)\n-- [1,8,49,288,1681]\n-- Conjeturando que el n-\u00e9simo n\u00famero s(n) se calcula mediante una\n-- recurrencia del tipo s(n)\u2004=\u2004x*s(n-1)\u2005+\u2005y*s(n-2) + z se tiene \n-- s(1) = 1\n-- s(2) = 8\n-- s(3) = 49 = 8x + y + z\n-- s(4) = 288 = 49x + 8y + z\n-- s(5) = 1681 = 288x + 49y + z \n-- al resolverlo se obtiene x = 6, y = -1, z = 2. Por tanto,\n-- s(1) = 1\n-- s(2) = 8\n-- s(n) = 6*s(n-1) - s(n-2) + 2\n\n-- El n\u00famero de la n-\u00e9simo casa equilibrada, p(n), se puede calcular por\n-- recursi\u00f3n: \ncasa :: Integer -> Integer\ncasa 1 = 1\ncasa 2 = 6\ncasa n = 6 * (casa (n-1)) - (casa (n-2))\n\n-- La sucesi\u00f3n de los n\u00fameros de las casas equilibradas se puede\n-- calcular por programaci\u00f3n din\u00e1mica:\ncasas :: [Integer]\ncasas = \n 1 : 6 : zipWith (\\x y -> 6*x-y) (tail casas) casas\n\n-- El n\u00famero de casas en la n-\u00e9sima calle con casas equilibradas, s(n),\n-- se puede calcular por recursi\u00f3n: \ncalle :: Integer -> Integer\ncalle 1 = 1\ncalle 2 = 8\ncalle n = 6 * (calle (n-1)) - (calle (n-2)) + 2\n\n-- La sucesi\u00f3n de los n\u00fameros de las casas equilibradas se puede\n-- calcular por programaci\u00f3n din\u00e1mica:\ncalles :: [Integer]\ncalles = \n 1 : 8 : zipWith (\\x y -> 6*x-y+2) (tail calles) calles\n\n-- Usando casas se obtiene la 3\u00aa soluci\u00f3n:\nsoluciones3 :: Integer -> Integer -> [(Integer,Integer)]\nsoluciones3 x y =\n takeWhile (<=(y,y)) (dropWhile (<(x,x)) (zip casas calles))\n\n-- Comprobaci\u00f3n de soluciones\n-- ==========================\n\n-- La propiedad es\nprop_soluciones :: Integer -> Integer -> Property\nprop_soluciones x y =\n 0 < x && x <= y ==>\n all esSolucion (soluciones3 x y)\n\n-- La comprobaci\u00f3n es\n-- ghci> quickCheck prop_soluciones\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia:\n-- ghci> soluciones1 1 2000\n-- [(1,1),(6,8),(35,49),(204,288),(1189,1681)]\n-- (337.30 secs, 396493594456 bytes)\n-- ghci> soluciones2 1 2000\n-- [(1,1),(6,8),(35,49),(204,288),(1189,1681)]\n-- (23.47 secs, 3859436176 bytes)\n-- ghci> soluciones3 1 2000\n-- [(1,1),(6,8),(35,49),(204,288),(1189,1681)]\n-- (0.01 secs, 1029592 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Continuando con los problema propuestos por alumnos, el de hoy es el propuesto por Rafael Jim\u00e9nez. Se tiene una calle en la que las casas s\u00f3lo est\u00e1n en un lado de \u00e9sta y las casas est\u00e1n numeradas de 1 hasta n, donde n es el n\u00famero total de casas en la calle. Se dice que…<\/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":[7],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1321"}],"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=1321"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1321\/revisions"}],"predecessor-version":[{"id":1348,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1321\/revisions\/1348"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1321"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1321"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1321"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}