Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Encontrando uma tripla pitagoriana

0 votos
30 visitas
perguntada Mar 18 em Programação Computacional por Felipe Yudi (46 pontos)  
editado Mar 18 por Felipe Yudi

Uma tripla pitagoriana é um conjunto de 3 números \(a < b < c\) tais que \(a^2 + b^2 = c^2\).
Existe apenas uma dessas triplas tal que \(a + b + c = 1000\) .
Ache essa tripla. Discuta a eficiência da sua solução.

Compartilhe
comentou Mar 18 por Stuart Mill (1,434 pontos)  
Os números são naturais?

1 Resposta

+1 voto
respondida Mar 18 por Felipe Yudi (46 pontos)  
editado Mar 19 por Felipe Yudi

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}\).

comentou Mar 22 por Carlos Piccioni (1 ponto)  
editado Mar 22 por Carlos Piccioni
Felipe, tudo bem?

Podemos implementar algumas modificações no algoritmo de força bruta para melhorar o desempenho. Na versão atual, passamos por laços em que a especificação \(a \lt b \lt c\) é violada. Por exemplo, a situação \(a = 2, b = 1, c = 1\) acaba sendo avaliada. Uma forma imediata de corrigir esse problema e melhorar o desempenho é restringir o valor inferior do range, de cada laço interior, a um incremento do valor da variável avaliada no for exterior. Por exemplo:

for a in range(1, n-1):
        for b in range(a+1, n):
            for c in range(b+1, n+1):

Com isso, respeitamos a especificação \(a \lt b \lt c \) para o limite inferior (mas ainda não para o limite superior, como veremos adiante).

Outra melhoria seria eliminar o terceiro laço, por meio da especificação \(a + b + c = 1000\). Como, após o segundo for, já temos candidatos para \(a\) e \(b\), podemos calcular diretamente \(c = 1000 - a - b\), não sendo necessário chutar valores para \(c\).

Além disso, como \(a \lt b \lt c\) e \(a + b + c = 1000\), sabemos que não podemos ter \(a \gt 333\) (por exemplo, se \(a = 333, b \gt 333, c \gt 334\), logo \(a + b + c \gt 1000)\). Assim, podemos limitar superiormente o range do primeiro for. Na prática, não terá efeito, pois na solução \(a = 200\).

Porém, também podemos limitar superiormente o range do segundo laço, e esse sim terá efeitos práticos no desempenho. Como \(a \lt b \lt c\), com \(a \geq 1\), não podemos ter \(b \geq 500\), ou \(b \geq n/2\), pois com \(c \gt b\), teríamos \(a + b + c \gt 1000\).

Podemos ir além, e para cada incremento de \(a\), podemos diminuir o limite superior do range do segundo for para \((n-a)/2\), aproximando para o inteiro imediatamente superior, ou seja, o segundo for seria:

for b in range(a+1, int((n-a)/2)+1):

Com isso, por exemplo, quando estivermos na situação em que \(a=199, b=400, c=401\) (que ainda não é nossa tripla pitagoriana), não avaliaremos  \(b=401\) na próxima passagem, pois \(a=199, b=401, c=400\) viola \(b \lt c\). Assim, reduzimos um considerável número de passagens pelo segundo laço durante toda a execução do algoritmo.

Uma forma 'suja' de eliminar o segundo laço é resolver o próprio sistema de equações especificada: \(a + b + c = n\) e \(a^2 + b^2 = c^2\). Substituindo \(c = n - a - b\) na segunda equação e resolvendo para \(b\), temos:

\(b = (n*n - 2*a*n) / (2*(n - a))\)

Observando que só podemos admitir \(b\) natural (sendo então necessário testar, para cada passagem pelo laço, essa condição (exemplo: if(b.is_integer()) ) ).

Em conjunto com \(c = n - a - b\), bastaria testar se, para cada \(a, b, c\) calculados, temos uma tripla pitagoriana.

Uma abordagem alternativa ao método de força bruta é utilizar a fórmula de Euclides (https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple) para geração de triplas pitagorianas.

Dados quaisquer números naturais \(x\) e \(y\), com \(x \gt y\), \(x\) e \(y\) coprimos, exatamente um deles sendo par, e:

\(a = d*(x^2 - y^2)\)
\(b = d*(2*x*y)\)
\(c = d*(x^2 + y^2)\)

com \(d\) sendo o maior divisor comum de \(a, b, c\), então toda tripla pitagoriana \((a, b, c)\) pode ser representada unicamente por \((d, x, y)\) (não provaremos isso aqui).

Qual a vantagem dessa abordagem?

A redução do range de números que precisam ser testados, em relação aos métodos de força bruta que avaliam \(a, b, c\) diretamente, se procurarmos por \((d, x, y)\). Isso ocorre pois, como temos:

\(a + b + c = n\)

Substituindo a fórmula de Euclides em \(a, b, c\) temos:

\(d*(x^2-y^2) + d*(2*x*y) + d*(x^2+y^2) = n\)

Resolvendo:

\(2*d*x^2 + 2*d*x*y = n\)

\(d*x*(x+y) = n/2\)

Note que, obrigatoriamente, deste resultado, \(n/2\) é natural, pois \(d, x\) e \(x+y\) são naturais. Logo, dessa equação e das definições da fórmula de Euclides, teremos que ter:

1) \(n/2\) deve ser divisível por \(x\);
2) \(n/(2*x)\) deve ser divisível por \(x+y\);
3) \(x \lt \sqrt{n/2}\), pois \(d \geq 1\) e \(x+y \gt x\), logo \(d*x*(x+y) > x*x\) o que implica que \(x*x \lt n/2\) ou \(x \lt \sqrt{n/2}\);
4) \(x+y\) é ímpar, pois \(x\) ou \(y\), exatamente um deles, é par;
5) o maior divisor comum de \(x+y\) e \(x\) deve ser 1 (pois \(x\) e \(y\) são coprimos).

Nesse problema, \(x \lt \sqrt{1000/2}\), que é aproximadamente 22,36, logo \(x \lt 23\). Como \(x \gt y\), o esforço de busca por \(x\) e \(y\) que gerem a solução do problema \(a,b,c\) é bem reduzida.

Para encontrar \(y\), também pode-se limitar \(x+y\) durante a execução do algoritmo (ficará mais eficiente do que executar um laço em que \(y\) possa ir até \(x - 1\) para atender \(x \gt y\)). Chamando \(z=x+y\), a partir de \(d*x*(x+y) = n/2\) temos que \(d*x*z = n/2\), o que implica que \(z = n/(2*d*x)\), logo:

\(z \leq n/(2*x)\)

pois \(d \geq 1\)

E, como \(x < x + y < 2 * x\), pois \(x \gt y\), então:

\(z < 2 * x\)

Assim, um algoritmo eficiente para a solução do problema pode ser implementado testando, para cada \(x \lt \sqrt{n/2}\) (condição 3), se \(s/2\) é divisível por \(x\) (condição 1). Em caso afirmativo, atribuir um valor inicial para \(z\), \(z = x + 1\) se \(x\) for par ou \(z = x + 2\) se \(x\) for ímpar (condição 4), e por meio de um laço interno prosseguir incrementando \(z\) enquanto \(z \leq n/(2*x)\) e \(z < 2 * x\). Se \(n/(2 * x)\) for divisível por \(z\) (condição 2) e o maior divisor comum de \(z\) e \(x\) for 1 (condição 5), atendemos as condições enunciadas, ou seja, encontramos \(z\), logo \(y\), e assim calculamos \(d\) por \(d*x*(x+y) = n/2\). Por fim encontramos \(a, b, c\) pelas equações de Euclides.

Abraços
...