A estratégia que utilizaremos aqui será a de definir duas
funções. Uma que retornará True caso uma tripla (a, b, c)
seja uma tripla pitagoriana e outra que buscará uma combinação
tal que \(a + b + c = 1000\).
Assumiremos que a, b e c são números naturais.
def tripla_pit(a, b, c):
"""
a, b, c: numeros inteiros tais que
a < b < c
retorna: True se os numeros formam uma tripla
pitagoriana e False caso contrario.
"""
if a**2 + b**2 == c**2:
return True
else:
return False
def find_tripla(n):
"""
n: numero natural
retorna: uma tupla com os valores de
a, b, e c tais que a, b e c sao uma
tripla pitagoriana e que a + b + c = n.
Caso eles nao sejam, retorna False
"""
for a in range(1, n-1):
for b in range(1, n):
for c in range(1, n+1):
if a + b + c == n and tripla_pit(a, b, c):
return (a, b, c)
return False
if __name__=="__main__":
#Exemplo
print(tripla_pit(3, 4, 5))
#Nosso caso
print(find_tripla(1000))
O resultado é portanto a tripla (200, 375, 425).
Note que o algorítimo acima é bastante ineficiente,
pois é um método de força bruta Isto é, utiliza a definição
do problema para resolvê-lo.
A parte importante para calcular a complexidade do algorítimo
está na função find tripla, pois sua ordem de complexidade é
claramente maior do que a da função tripla pit.
Note que no pior caso possível, a = n-2, b = n-1 e c = n, ou seja,
analisaremos todas as possibilidades .
Isso significa que passaremos n vezes por cada valor
possível para a, b e c, o que implica em uma complexidade de O(n^3).
Isso é fácil de visualizar com somatórios.
\(\sum_{n}^{n-2}\sum_{n}^{n-1}\sum_{n}^{n}1\Rightarrow \sum_{n}^{n-2}\sum_{n}^{n-1}n\Rightarrow \sum_{n}^{n-2}(n-1)n\)
\((n-2)(n-1)n \Rightarrow n^{3}-3n^{2}+3n\)
Que tem complexidade \(n^{3}\).