Sumas de dos cuadrados
Definir la función
|
1 |
sumasDe2Cuadrados :: Integer -> [(Integer, Integer)] |
tal que (sumasDe2Cuadrados n) es la lista de los pares de números tales que la suma de sus cuadrados es n y el primer elemento del par es mayor o igual que el segundo. Por ejemplo,
|
1 2 3 4 5 |
sumasDe2Cuadrados 25 == [(5,0),(4,3)] sumasDe2Cuadrados 32 == [(4,4)] sumasDe2Cuadrados 55 == [] sumasDe2Cuadrados 850 == [(29,3),(27,11),(25,15)] length (sumasDe2Cuadrados (10^12)) == 7 |
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 61 62 63 64 65 66 67 68 69 70 71 72 73 |
-- 1ª definición sumasDe2Cuadrados1 :: Integer -> [(Integer, Integer)] sumasDe2Cuadrados1 n = [(x,y) | x <- [n,n-1..0] , y <- [0..x] , x*x+y*y == n] -- 2ª definición: sumasDe2Cuadrados2 :: Integer -> [(Integer, Integer)] sumasDe2Cuadrados2 n = [(x,y) | x <- [a,a-1..0] , y <- [0..x] , x*x+y*y == n] where a = (floor . sqrt . fromIntegral) n -- 3ª definición sumasDe2Cuadrados3 :: Integer -> [(Integer, Integer)] sumasDe2Cuadrados3 n = [(raizEntera x, raizEntera y) | y <- takeWhile (<= n `div` 2) cuadrados , let x = n - y , esCuadrado x] cuadrados :: [Integer] cuadrados = map (^2) [0..] esCuadrado :: Integer -> Bool esCuadrado x = x == y * y where y = raizEntera x raizEntera :: Integer -> Integer raizEntera x = (floor . sqrt . fromIntegral) x -- 4ª definición sumasDe2Cuadrados4 :: Integer -> [(Integer, Integer)] sumasDe2Cuadrados4 n = aux ((floor . sqrt . fromIntegral) n) 0 where aux x y | x < y = [] | x*x + y*y < n = aux x (y+1) | x*x + y*y == n = (x,y) : aux (x-1) (y+1) | otherwise = aux (x-1) y -- Comparación de eficiencia -- λ> sumasDe2Cuadrados1 2020 -- [(42,16),(38,24)] -- (4.29 secs, 621,601,336 bytes) -- λ> sumasDe2Cuadrados2 2020 -- [(42,16),(38,24)] -- (0.01 secs, 488,496 bytes) -- λ> sumasDe2Cuadrados3 2020 -- [(42,16),(38,24)] -- (0.02 secs, 197,256 bytes) -- λ> sumasDe2Cuadrados4 2020 -- [(42,16),(38,24)] -- (0.01 secs, 175,088 bytes) -- -- λ> length (sumasDe2Cuadrados2 48612265) -- 32 -- (51.25 secs, 7,395,035,904 bytes) -- λ> length (sumasDe2Cuadrados3 48612265) -- 32 -- (0.06 secs, 8,368,296 bytes) -- λ> length (sumasDe2Cuadrados4 48612265) -- 32 -- (0.04 secs, 3,483,168 bytes) -- -- λ> length (sumasDe2Cuadrados3 (10^12)) -- 7 -- (7.32 secs, 1,137,167,688 bytes) -- λ> length (sumasDe2Cuadrados4 (10^12)) -- 7 -- (3.64 secs, 480,776,736 bytes) |
[/schedule]
Buenas! aquí un novato total en haskell que propone su primera solución:
No se hasta que punto será eficiente, pero al menos pasa los test propuestos.
Un saludo.
En mi ordenador no es capaz de calcular el último ejemplo. En 2 segundos a lo más que llega a calcular es
Buenas, puedes conseguir mejorar la eficiencia de la función haciendo unos mínimos cambios tal que así (básicamente cambiar ceiling por floor (pues un número mayor a la raíz no va a poder ser solución, y así te ahorras alguna comprobación) y poner en tercer lugar la comprobación x < y, pues de esta manera también puedes ahorrarte algunas comprobaciones en algunos casos. El quitar la definición de raiz del where se debe a que solo calculas el valor una vez y por tanto no hace falta ponerlo):
Donde sumasDe2Cuadrados es tu definición.
Habría que hacerle un pequeño arreglo a la definición anterior pues en algunos casos genera pares de más:
Igualmente la comprobación de la eficiencia:
Ahora sí que funciona todo bien (o eso espero).