Triángulos geométricos
Un triángulo geométrico es un triángulo de lados enteros, representados por la terna (a,b,c) tal que a ≤ b ≤ c y están en progresión geométrica, es decir, b^2 = a*c. Por ejemplo, un triángulo de lados a = 144, b = 156 y c = 169.
Definir la función
|
1 |
numeroTG :: Integer -> Int |
tal que (numeroTG n) es el número de triángulos geométricos de perímetro menor o igual que n. Por ejemplo
|
1 2 3 |
numeroTG 10 == 3 numeroTG 100 == 42 numeroTG 200 == 91 |
Nota: Los triángulos geométricos de perímetro menor o igual que 20 son
|
1 |
[(1,1,1),(2,2,2),(3,3,3),(4,4,4),(5,5,5),(6,6,6),(4,6,9)] |
Se observa que (1,2,4) aunque cumple que 1+2+4 <= 20 y 2^2 = 1*4 no pertenece a la lista ya que 1+2 > 4 y, por tanto, no hay ningún triángulo cuyos lados midan 1, 2 y 4.
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 |
-- 1ª definición: numeroTG :: Integer -> Int numeroTG n = length [(a,b,c) | c <- [1..n] , b <- [1..c] , a <- [1..b] , a+b > c , a+b+c <= n , b^2 == a*c ] -- 2ª definición: numeroTG2 :: Integer -> Int numeroTG2 n = length [(a,b,c) | c <- [1..n] , b <- [1..c] , b^2 `rem` c == 0 , let a = b^2 `div` c , a+b > c , a+b+c <= n ] -- Comparación de eficiencia: -- λ> numeroTG 300 -- 143 -- (2.40 secs, 1,496,824,720 bytes) -- λ> numeroTG2 300 -- 143 -- (0.05 secs, 40,908,568 bytes) |
Referencia
El ejercicio está basado en el problema 370 del proyecto Euler.
Corrigiendo la anterior solución para incorporar la condición de ser triángulos (
a + b >= c):Los límites de cada lado se obtienen de las siguientes relaciones:
De donde se deduce:
Corregido.