11 abr 2013, 04:04
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.
11 abr 2013, 12:40
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!
11 abr 2013, 13:10
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...
11 abr 2013, 17:12
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.
12 abr 2013, 11:26
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
13 abr 2013, 15:20
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.
14 abr 2013, 22:40
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}\)
Powered by phpBB © phpBB Group.
phpBB Mobile / SEO by Artodia.