Puntos en una región
Definir la función
|
1 |
puntos :: Integer -> [(Integer,Integer)] |
tal que (puntos n) es la lista de los puntos (x,y) con coordenadas enteras de
la cuadrícula [1..n]x[1..n] (es decir, 1 ≤ x,y ≤ n) tales que |x²-xy-y²| = 1. Por ejemplo,
|
1 2 3 4 |
length (puntos 10) == 5 length (puntos 100) == 10 length (puntos 1000) == 15 length (puntos (10^50000)) == 239249 |
Soluciones
|
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 |
-- 1ª definición -- ============= puntos1 :: Integer -> [(Integer,Integer)] puntos1 n = [(x,y) | x <- [1..n], y <- [1..n], abs (x^2-x*y-y^2) == 1] -- 2ª definición -- ============= -- Calculando algunos elementos -- λ> puntos1 10 -- [(1,1),(2,1),(3,2),(5,3),(8,5)] -- λ> puntos1 20 -- [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8)] -- λ> puntos1 100 -- [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8),(21,13),(34,21),(55,34),(89,55)] -- λ> puntos1 89 -- [(1,1),(2,1),(3,2),(5,3),(8,5),(13,8),(21,13),(34,21),(55,34),(89,55)] -- se observa una ley de construcción de cada elemento a partir del anterior. puntos2 :: Integer -> [(Integer,Integer)] puntos2 n = takeWhile menor (iterate siguiente (1,1)) where siguiente (x,y) = (x+y,x) menor (x,y) = x <= n -- 3ª definición -- ============= -- Se observa que la lista de las segundas componentes -- 1,1,2,3,5,8,13,21,34,55,89,... -- y la lista de las primeras componentes es el resto de la segunda. puntos3 :: Integer -> [(Integer,Integer)] puntos3 n = zip (tail xs) xs where xs = takeWhile (<=n) fibonacci -- fibonacci es la sucesión de Fibonacci. Por ejemplo, -- take 11 fibonacci == [1,1,2,3,5,8,13,21,34,55,89] fibonacci :: [Integer] fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci) -- Comparación de eficiencia -- ========================= -- λ> length (puntos1 (10^3)) -- 15 -- (7.96 secs, 1,092,368,200 bytes) -- λ> length (puntos2 (10^3)) -- 15 -- (0.02 secs, 0 bytes) -- -- λ> length (puntos2 (10^30000)) -- 143549 -- (1.14 secs, 974,239,544 bytes) -- λ> length (puntos3 (10^30000)) -- 143549 -- (3.28 secs, 967,206,560 bytes) |