Perímetro más frecuente de triángulos rectángulos
El grado perimetral de un número p es la cantidad de tres triángulos rectángulos de lados enteros cuyo perímetro es p. Por ejemplo, el grado perimetral de 120 es 3 ya que sólo hay 3 triángulos rectángulos de lados enteros cuyo perímetro es 120: {20,48,52}, {24,45,51} y {30,40,50}.
Definir la función
|
1 |
maxGradoPerimetral :: Int -> (Int,[Int]) |
tal que (maxGradoPerimetral n) es el par (m,ps) tal que m es el máximo grado perimetral de los números menores o iguales que n y ps son los perímetros, menores o iguales que n, cuyo grado perimetral es m. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 |
maxGradoPerimetral 50 == (1,[12,24,30,36,40,48]) maxGradoPerimetral 100 == (2,[60,84,90]) maxGradoPerimetral 200 == (3,[120,168,180]) maxGradoPerimetral 400 == (4,[240,360]) maxGradoPerimetral 500 == (5,[420]) maxGradoPerimetral 750 == (6,[720]) maxGradoPerimetral 839 == (6,[720]) maxGradoPerimetral 840 == (8,[840]) maxGradoPerimetral 1500 == (8,[840,1260]) maxGradoPerimetral 2000 == (10,[1680]) maxGradoPerimetral 3000 == (12,[2520]) |
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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
import Data.List import Data.Array (accumArray, assocs) -- 1ª solución -- -- =========== maxGradoPerimetral1 :: Int -> (Int,[Int]) maxGradoPerimetral1 p = (m,[x | (n,x) <- ts, n == m]) where ts = [(length (triangulos x),x) | x <- [1..p]] (m,_) = maximum ts -- (triangulos p) es el conjunto de triángulos rectángulos de perímetro -- p. Por ejemplo, -- triangulos 120 == [(20,48,52),(24,45,51),(30,40,50)] triangulos :: Int -> [(Int,Int,Int)] triangulos p = [(a,b,c) | a <- [1..q], b <- [a..q], let c = p-a-b, a*a+b*b == c*c] where q = p `div` 2 -- 2ª solución -- -- =========== maxGradoPerimetral2 :: Int -> (Int,[Int]) maxGradoPerimetral2 p = (m,[x | (n,x) <- ts, n == m]) where ts = [(n,x) | (x,n) <- numeroPerimetrosTriangulos p, n > 0] (m,_) = maximum ts -- (numeroPerimetrosTriangulos p) es la lista formado por los números de -- 1 a p y la cantidad de triángulos rectángulos enteros cuyo perímetro -- es dicho número. Por ejemplo, -- ghci> [(p,n) | (p,n) <- numeroPerimetrosTriangulos 70, n > 0] -- [(12,1),(24,1),(30,1),(36,1),(40,1),(48,1),(56,1),(60,2),(70,1)] numeroPerimetrosTriangulos :: Int -> [(Int,Int)] numeroPerimetrosTriangulos p = assocs (accumArray (\x _ -> 1+x) 0 (1,p) (perimetrosTriangulos p)) -- (perimetrosTriangulos p) es la lista formada por los perímetros y los -- lados de los triángulos rectángulos enteros cuyo perímetro es menor o -- igual que p. Por ejemplo, -- ghci> perimetrosTriangulos 70 -- [(12,(3,4,5)), (30,(5,12,13)),(24,(6,8,10)), (56,(7,24,25)), -- (40,(8,15,17)), (36,(9,12,15)),(60,(10,24,26)),(48,(12,16,20)), -- (60,(15,20,25)),(70,(20,21,29))] perimetrosTriangulos :: Int -> [(Int,(Int,Int,Int))] perimetrosTriangulos p = [(q,(a,b,c)) | a <- [1..p1], b <- [a..p1], esCuadrado (a*a+b*b), let c = raizCuadradaE (a*a+b*b), let q = a+b+c, q <= p] where p1 = p `div` 2 -- (esCuadrado n) se verifica si n es un cuadrado. Por ejemplo, -- esCuadrado 25 == True -- esCuadrado 27 == False esCuadrado :: Int -> Bool esCuadrado n = a*a == n where a = raizCuadradaE n -- (raizCuadradaE n) es la raíz cuadrada entera de n. Por ejemplo, -- raizCuadradaE 25 == 5 -- raizCuadradaE 27 == 5 -- raizCuadradaE 35 == 5 -- raizCuadradaE 36 == 6 raizCuadradaE :: Int -> Int raizCuadradaE = floor . sqrt . fromIntegral -- 3ª solución -- -- =========== maxGradoPerimetral3 :: Int -> (Int,[Int]) maxGradoPerimetral3 p = (m,[x | (n,x) <- ts, n == m]) where ts = [(n,x) | (x,n) <- numeroPerimetrosTriangulos2 p, n > 0] (m,_) = maximum ts -- (numeroPerimetrosTriangulos2 p) es la lista formado por los números de -- 1 a p y la cantidad de triángulos rectángulos enteros cuyo perímetro -- es dicho número. Por ejemplo, -- ghci> [(p,n) | (p,n) <- numeroPerimetrosTriangulos2 70, n > 0] -- [(12,1),(24,1),(30,1),(36,1),(40,1),(48,1),(56,1),(60,2),(70,1)] numeroPerimetrosTriangulos2 :: Int -> [(Int,Int)] numeroPerimetrosTriangulos2 p = [(head xs, length xs) | xs <- group (sort (perimetrosTriangulos2 p))] -- (perimetrosTriangulos2 p) es la lista formada por los perímetros de -- los triángulos rectángulos enteros cuyo perímetro es menor o igual -- que p. Por ejemplo, -- perimetrosTriangulos2 70 == [12,30,24,56,40,36,60,48,60,70] perimetrosTriangulos2 :: Int -> [Int] perimetrosTriangulos2 p = [q | a <- [1..p1], b <- [a..p1], esCuadrado (a*a+b*b), let c = raizCuadradaE (a*a+b*b), let q = a+b+c, q <= p] where p1 = p `div` 2 -- Comparación de eficiencia -- ========================= -- La comparación es -- ghci> maxGradoPerimetral1 1000 -- (8,[840]) -- (120.08 secs, 21116625136 bytes) -- ghci> maxGradoPerimetral2 1000 -- (8,[840]) -- (0.66 secs, 132959056 bytes) -- ghci> maxGradoPerimetral3 1000 -- (1000,[1]) -- (0.66 secs, 133443816 bytes) |