我刚刚完成了Euler项目问题9(警告破坏者):
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
这是我的解决方案:
public static int specPyth(int num)
{
for (int a = 1; a < num; a++)
for (int b = 2; b < a; b++)
{
if (a*a +b*b == (num-a-b)*(num-a-b))
return a*b*(num-a-b); //ans = 31875000
}
return -1;
}
我不禁想到，有一个解决方案只涉及一个循环。有人有主意吗？我希望仅使用一个循环来回答问题，但是比我目前所拥有的效率更高的任何东西都是不错的。
最佳答案
if a + b +c = 1000
然后
a + b + sqroot(a² + b²) = 1000
-> (a² + b²) = (1000 - a - b)²
-> a² + b² = 1000000 - 2000*(a+b) + a² + 2*a*b + b²
-> 0 = 1000000 - 2000*(a+b) + 2*a*b
-> ... (easy basic maths)
-> a = (500000 - 1000*b) / (1000 - b)
然后，尝试每个b，直到找到一个从a中产生自然数的数字。
public static int specPyth(int num)
{
double a;
for (int b = 1; b < num/2; b++)
{
a=(num*num/2 - num*b)/(num - b);
if (a%1 == 0)
return (int) (a*b*(num-a-b));
}
return -1;
}
编辑:b不能高于499，因为c> b和(b + c)会高于1000。
关于java - 我可以使该功能更有效吗(9号欧拉计划)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16912056/