Fórum de Matemática
DÚVIDAS? Nós respondemos!

Um Fórum em Português dedicado à Matemática
Data/Hora: 02 mai 2024, 05:31

Os Horários são TMG [ DST ]




Fazer Nova Pergunta Responder a este Tópico  [ 7 mensagens ] 
Autor Mensagem
 Título da Pergunta: Quadrados Perfeitos
MensagemEnviado: 11 abr 2013, 04:04 
Offline

Registado: 11 abr 2013, 03:51
Mensagens: 3
Localização: Porto Alegre
Agradeceu: 0 vez(es)
Foi agradecido: 0 vez(es)
Olá pessoal.

Meu primeiro acesso e talvez de forma incorreta, mas...venho recorrer aos experts em matemática.

Não sou estudante de matemática, mas sim da área de TI, e o problema que me foi proposto é o do enunciado a seguir...
Código:
Achar combinações de três números inteiros positivos x, y e z de forma que x+y, x-y, y +z, y- z, x+z
e x-z sejam quadrados perfeitos. Além disso, os números x, y e z devem ser diferentes entre si.
Você deve desenvolver um algoritmo que encontra todas as combinações de x, y e z entre 1
e 2.000.000 com estas propriedades...


Bem, como percebem o problema é mais matemático do que qualquer coisa...sei o que é um número perfeito, mas não consegui encontrar uma solução que me reduza ao máximos os testes entre todas as combinações possíveis, por isso venho a vocês.


Topo
 Perfil  
 
 Título da Pergunta: Re: Quadrados Perfeitos
MensagemEnviado: 11 abr 2013, 12:40 
Offline

Registado: 17 jan 2013, 13:36
Mensagens: 2487
Localização: Lisboa
Agradeceu: 31 vezes
Foi agradecido: 1049 vezes
Bem, mesmo sem uma análise matemática profunda, pode limitar a pesquisa desses indices... Como x - y , x-z, y-z devem ser positivos devemos ter z < y < x. Assim pode fazer algo do estilo

for (z = 1; z <= 1999998; z++)
for (y = z+1; y <= 1999999; y++)
for (x = y+1; x<=2000000; x++)
{
...TESTAR as condições e escrever em caso de sucesso...
};


suponho que pensando um pouco mais talvez se possam reduzir as hipóteses... mas assim já se reduzem substancialmente!


Topo
 Perfil  
 
 Título da Pergunta: Re: Quadrados Perfeitos
MensagemEnviado: 11 abr 2013, 13:10 
Offline

Registado: 17 jan 2013, 13:36
Mensagens: 2487
Localização: Lisboa
Agradeceu: 31 vezes
Foi agradecido: 1049 vezes
Uma ideia melhor ...

\(x+y = a^2
x-y = b^2
y+z = c^2
y-z=d^2
x+z=e^2
x-z=f^2\)

Manipulando estas expressões pode chegar a

\(x = (a^2+b^2)/2
y = (a^2-b^2)/2
z =(2c^2-a^2+b^2)/2\)

Deste modo pode construir os ciclos percorrendo os possiveis valores de a,b,c e testando se (x,y,z) verifica ou não a condição proposta. Qual a vantagem ? Bem é que a <=2000, b <=1415 e c <= 2000...


Topo
 Perfil  
 
 Título da Pergunta: Re: Quadrados Perfeitos
MensagemEnviado: 11 abr 2013, 17:12 
Offline

Registado: 11 abr 2013, 03:51
Mensagens: 3
Localização: Porto Alegre
Agradeceu: 0 vez(es)
Foi agradecido: 0 vez(es)
Citar:

Deste modo pode construir os ciclos percorrendo os possiveis valores de a,b,c e testando se (x,y,z) verifica ou não a condição proposta. Qual a vantagem ? Bem é que a <=2000, b <=1415 e c <= 2000...



Hum...Sem querer abusar muito, seria possível dar um exemplo da construção?? Estou realmente perdido nessa questão e pra mim ainda é meio confuso entender....

Grato.


Topo
 Perfil  
 
 Título da Pergunta: Re: Quadrados Perfeitos
MensagemEnviado: 12 abr 2013, 11:26 
Offline

Registado: 17 jan 2013, 13:36
Mensagens: 2487
Localização: Lisboa
Agradeceu: 31 vezes
Foi agradecido: 1049 vezes
Repare, se x,y,z se podem escrever em termos de a,b,c do modo que sugeri antes, ao percorrer todas as combinações admissíveis de a,b,c também percorremos todos os candidatos a solução do problema... o esquema geral seria:

for(int b=1; b <=1415; b++)
for(int a = b+1; a<=2000;a++)
for(int c = floor(sqrt((a*a-b*b)/2))+1; c <=2000;c++)
{
x= (a*a +b*b)/2;
y =(a*a-b*b)/2;
z = (2*c*c-a*a+b*b)/2;
if(testa(x,y,z)) cout << x << " " << y << " " << z << endl;
};

a função "testa" verifica se x,y,z constitui uma solução do problema. Obtive deste modo as seguintes soluções:

434657, 420968, 150568
993250, 949986, 856350
1738628, 1683872, 602272
733025, 488000, 418304


Topo
 Perfil  
 
 Título da Pergunta: Re: Quadrados Perfeitos
MensagemEnviado: 13 abr 2013, 15:20 
Offline

Registado: 11 abr 2013, 03:51
Mensagens: 3
Localização: Porto Alegre
Agradeceu: 0 vez(es)
Foi agradecido: 0 vez(es)
Grande mestre, realmente perfeito.
Meu código em java:
Código:
public class Quadrados {
    String resultado = "";
    public void buscaQuadradosPerfeitos() {
        double x, y, z;
        for (int b = 1; b <= 1415; b++) {
            for (int a = b + 1; a <= 2000; a++) {
                for (int c = (int) (Math.floor(Math.sqrt((a * a - b * b) / 2))) + 1; c <= 2000; c++) {
                    x = (a * a + b * b) / 2;
                    y = (a * a - b * b) / 2;
                    z = (2 * c * c - a * a + b * b) / 2;
                    testa(x, y, z);
                }
            }
        }
        System.out.println(resultado);
    }

    private void testa(double x, double y, double z) {
        if (x == y || x == z || y == z)
            return;   
   
        double raiz;
        raiz = Math.sqrt(x - z);
        if (raiz != (long) raiz)
            return;
       
        raiz = Math.sqrt(y - z);
        if (raiz != (long) raiz)
            return;     

        raiz = Math.sqrt(x - y);
        if (raiz != (long) raiz) {
            return;
        }

        raiz = Math.sqrt(x + y);
        if (raiz != (long) raiz)
            return;
       
        raiz = Math.sqrt(y + z);
        if (raiz != (long) raiz)
            return;   

        raiz = Math.sqrt(x + z);
        if (raiz != (long) raiz)
            return;
       
        resultado += "  X = " + x;
        resultado += "  Y = " + y;
        resultado += "  Z = " + z;
        resultado += "  Raiz = " + raiz;
        resultado += "\n";
    }


Grato por me passar toda a solução pronta.
Agora meu desafio será correr atrás de compreender como chegaste nos números 1415 e 2000 para limite dos laços, não percebi nenhuma dica sobre isso, mas estou realmente grato.
Um abraço.


Topo
 Perfil  
 
 Título da Pergunta: Re: Quadrados Perfeitos
MensagemEnviado: 14 abr 2013, 22:40 
Offline

Registado: 17 jan 2013, 13:36
Mensagens: 2487
Localização: Lisboa
Agradeceu: 31 vezes
Foi agradecido: 1049 vezes
Como \(x + y = a^2\) e tanto x como y são menores de 2.000.000, x+y será menor que 4.000.000. Assim, \(a < \sqrt{4.000.000} = 2000\).

Do mesmo modo, como \(b^2 = x-y\), vemos que \(b^2 < x \leq 2.000.000\).Por isso \(b \leq \sqrt{2.000.000}\)


Topo
 Perfil  
 
Mostrar mensagens anteriores:  Ordenar por  
Fazer Nova Pergunta Responder a este Tópico  [ 7 mensagens ] 

Os Horários são TMG [ DST ]


Quem está ligado:

Utilizadores a ver este Fórum: Nenhum utilizador registado e 22 visitantes


Criar perguntas: Proibído
Responder a perguntas: Proibído
Editar Mensagens: Proibído
Apagar Mensagens: Proibído
Enviar anexos: Proibído

Pesquisar por:
Ir para: