Mejorando el rendimiento de la determinación de cuántos triángulos posibles se pueden formar con una vara dada.
Estoy haciendo una evaluación que solicita el “n” dado como entrada, que es la longitud de una vara; ¿cuántos triángulos se pueden formar? (3 < n < 1,000,000)
Por ejemplo:
input: N=8
output: 1
explicación:
(3,3,2)
input: N=12
output: 3
explicación:
(4,4,4) (4,5,3) (5,5,2)
Ahora, los códigos que escribí están devolviendo un 33% de precisión, ya que la evaluación web arroja un error de límite de tiempo.
ans = 0
n = int(input())
for a in range(1, n + 1):
for b in range(a, n - a + 1):
c = n - a - b
if a + b > c >= b:
ans += 1
print(ans)
Código b:
ans = 0
n = int(input())
for i in range(1,n):
for j in range(i,n):
for c in range(j,n):
if(i+j+c==n and i+j>c):
ans+=1
print(ans)
¿Cómo se puede hacer esto más rápido?
davy.ai
Ambas variaciones de código están utilizando bucles anidados para verificar todas las posibles combinaciones de longitudes para los lados de un triángulo con un perímetro dado. Sin embargo, la segunda variación solo verifica combinaciones distintas de longitudes de lados comenzando el bucle interno desde el valor actual del bucle externo, lo que reduce la cantidad de verificaciones innecesarias.
Para optimizar aún más el código, podemos eliminar el tercer bucle utilizando manipulaciones algebraicas para calcular la longitud máxima posible del tercer lado dado los valores de los dos primeros lados. Esto reduce la complejidad temporal de O(n^3) a O(n^2), lo que debería mejorar significativamente el rendimiento, especialmente para valores grandes de n.
Aquí tienes una versión mejorada del código:
En esta implementación, estamos calculando el valor máximo posible de b para evitar iteraciones innecesarias, y utilizando una declaración if para verificar si se cumple la desigualdad del triángulo. Este algoritmo debería ejecutarse mucho más rápido para valores grandes de n.