寻找毕达哥拉斯三胞胎的代码

Question

我目前正在尝试这个问题:

毕达哥拉斯三元组是三个自然数a,b和c的集合,其中² + b ² = c ².

例如,3 ² + 4 ² = 9 + 16 = 25 = 5 ².

恰好存在一个毕达哥拉斯三元组,其中a + b + c = 1000.找到产品abc.

我的代码如下,我认为它应该是正确的,但网站告诉我我的答案是错的？有人可以帮我看看我的逻辑中的缺陷吗？

public class Pythagoras {
    public static void main(String[] args) {
            int sum = 1000;
            int a;
            int product=0;
            for (a = 1; a <= sum/3; a++)
            {
                int b;
                for (b = a + 1; b <= sum/2; b++)
                {
                    int c = sum - a - b;
                    if ( c > 0 && (a*a + b*b == c*c) )
                       System.out.printf("a=%d, b=%d, c=%d\n",a,b,c);
                        product = a * b * c;
                }
            }
            System.out.println(product);
        }
    }

Answer 1

这里有5个解决方案(从慢到快):

1)琐碎的实现 - 732857微秒(0.7秒)

private static void p1(int sum) {
    for (int a = 0; a <= sum; a++) {
        for (int b = 0; b <= sum; b++) {
            for (int c = 0; c <= sum; c++) {
                if (a < b && b < c && a + b + c == sum
                        && (c * c == a * a + b * b)) {
                    System.out.print(a * b * c);
                    return;
                }
            }
        }
    }
}

2)限制b&c的下限(建立顺序关系) - 251091微秒(0.2秒)

private static void p2(int sum) {
    for (int a = 0; a <= sum; a++) {
        for (int b = a + 1; b <= sum; b++) {
            for (int c = b + 1; c <= sum; c++) {
                if (a + b + c == sum && (c * c == a * a + b * b)) {
                    System.out.print(a * b * c);
                    return;
                }
            }
        }
    }
}

3)限制b&c的下限和上限 - 111220微秒(0.1秒)

private static void p3(int sum) {
    for (int a = 0; a <= sum; a++) {
        for (int b = a + 1; b <= sum - a; b++) {
            for (int c = b + 1; c <= sum - a - b; c++) {
                if (a + b + c == sum && (c * c == a * a + b * b)) {
                    System.out.print(a * b * c);
                    return;
                }
            }
        }
    }
}

4)限制b的下限和上限,固定值为c - 2625微秒

private static void p4(int sum) {
    for (int a = 0; a <= sum; a++) {
        for (int b = a + 1; b <= sum - a; b++) {
            int c = sum - a - b;
            if (c > b && c * c == a * a + b * b) {
                System.out.print(a * b * c);
                return;
            }
        }
    }
}

5)使用欧几里得公式 - 213微秒

private static void p5(int sum) {
    // a = m^2 - n^2
    // b = 2mn
    // c = m^2 + n^2
    int a, b, c;
    int sqrt = (int)Math.sqrt(sum);
    for (int n = 1; n <= sqrt; n++) {
        for (int m = n+1; m <= sqrt; m++) {
            a = m*m - n*n;
            b = 2*m*n;
            c = m*m + n*n;
            if ( a + b + c == 1000 ) {
                System.out.print(a * b * c);
                return;
            }
        }
    }
}

Answer 2

我想你错过了一套大括号.缩进使我相信两个最内层的陈述是一致的,但你需要花括号来证明这一点是正确的.

if ( c > 0 && (a*a + b*b == c*c) )
{
    System.out.printf("a=%d, b=%d, c=%d\n",a,b,c);
    product = a * b * c;
}

如果没有括号product总是包含的产品最后的值a,b和c.(333*500*167 == 27805500).