La cuadr\u00edcula entera de lado n, C\u2099, es el conjunto de los puntos (x,y) donde x e y son n\u00fameros enteros tales que 1 \u2264 x, y \u2264 n.<\/p>\n
Un punto (x,y) de C\u2099 es visible<\/strong> desde el origen si el m\u00e1ximo com\u00fan divisor de x e y es 1. Por ejemplo, el punto (4,6) no es visible porque est\u00e1 ocultado por el (2,3); en cambio, el (2,3) s\u00ed es visible.<\/p>\n El conjunto de los puntos visibles en la cuadr\u00edcula entera de lado 6 son (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,3), (2,5), (3,1), (3,2), (3,4), (3,5), (4,1), (4,3), (4,5), (5,1), (5,2), (5,3), (5,4), (5,6), (6,1) y (6,5).<\/p>\n Definir la funci\u00f3n<\/p>\n tal que (nVisibles n) es el n\u00famero de los puntos visibles en la cuadr\u00edcula de lado n.Por ejemplo,<\/p>\n\n nVisibles :: Integer -> Integer\n<\/pre>\n
\n nVisibles 6 == 23\n nVisibles 10 == 63\n nVisibles 100 == 6087\n nVisibles 1000 == 608383\n nVisibles 10000 == 60794971\n nVisibles 100000 == 6079301507\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Data.List (genericLength, group, sort)\nimport Data.Numbers.Primes (primeFactors)\n\ntype Punto = (Integer,Integer)\n\n-- (visible p) se verifica si el punto p es visible. Por ejemplo,\n-- visible (4,5) == True\n-- visible (4,6) == False\nvisible :: Punto -> Bool\nvisible (x,y) = gcd x y == 1\n\n-- (visibles n) es el conjunto de los puntos visibles en la cuadr\u00edcula\n-- de lado 1. Por ejemplo,\n-- cuadrado 1 <= x, y <= n. Por ejemplo,\n-- \u03bb> sort (visibles 6)\n-- [(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,3),(2,5),(3,1),(3,2),(3,4),\n-- (3,5),(4,1),(4,3),(4,5),(5,1),(5,2),(5,3),(5,4),(5,6),(6,1),(6,5)]\n\n-- 1\u00aa definici\u00f3n de visibles\nvisibles1 :: Integer -> [Punto]\nvisibles1 n = [(x,y) | x <- [1..n], y <- [1..n], visible (x,y)]\n\n-- 2\u00aa definici\u00f3n de visibles\nvisibles2 :: Integer -> [Punto]\nvisibles2 n = (1,1) : ps ++ [(y,x) | (x,y) <- ps] \n where ps = [(x,y) | x <- [1..n], y <- [x+1..n], visible (x,y)]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> length (visibles1 1000)\n-- 608383\n-- (3.40 secs, 758,346,208 bytes)\n-- \u03bb> length (visibles2 1000)\n-- 608383\n-- (2.22 secs, 464,276,856 bytes)\n\n-- Usaremos la 2\u00aa definici\u00f3n de visibles\nvisibles :: Integer -> [Punto]\nvisibles = visibles2\n\n-- 1\u00aa definici\u00f3n de nVisibles\nnVisibles1 :: Integer -> Integer\nnVisibles1 = genericLength . visibles\n\n\n-- 2\u00aa definici\u00f3n de nVisibles\nnVisibles2 :: Integer -> Integer\nnVisibles2 n = \n 1 + 2 * genericLength [(x,y) | x <- [1..n], \n y <- [x+1..n], \n visible (x,y)]\n\n-- 3\u00aa definici\u00f3n de nVisibles\nnVisibles3 :: Integer -> Integer\nnVisibles3 1 = 1\nnVisibles3 n = nVisibles3 (n-1) + (2 * phi n)\n\n-- La funci\u00f3n \u03c6 de Euler (del ejercicio anterior).\nphi :: Integer -> Integer\nphi n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n] \n \nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion n =\n [(head xs,genericLength xs) | xs <- group (primeFactors n)]\n\n-- 4\u00aa definici\u00f3n de nVisibles\nnVisibles4 :: Integer -> Integer\nnVisibles4 n = 2 * sum [phi x | x <- [1..n]] - 1\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> nVisibles1 1000\n-- 608383\n-- (2.69 secs, 521,599,512 bytes)\n-- \u03bb> nVisibles2 1000\n-- 608383\n-- \u03bb> nVisibles3 1000\n-- 608383\n-- (0.05 secs, 0 bytes)\n-- \u03bb> nVisibles4 1000\n-- 608383\n-- (0.04 secs, 0 bytes)\n<\/pre>\n
Referencias<\/h4>\n