c++ - 寻找毕达哥拉斯三重态(欧拉计划)

Question

我很清楚这种蛮力方法很糟糕，我应该使用类似欧几里德公式的东西，并且不需要最后的循环，因为 c = 1000 - (a + b) 等等......但是正确的现在我只想让它工作。

bool isPythagorean(int a, int b, int c) {
    if((a*a + b*b) == c*c && a < b && b < c) {
        cout << a << " " << b << " " << c << endl;
        return true;
    } else {
        return false;
    }
}

int main()
{
    int a = 1;
    int b = 2;
    int c = 3;

    for(a = 1; a < b; ++a) {
        for(b = 2; b < c; ++b) {
            for(c = 3; a + b + c != 1000 && !isPythagorean(a, b, c); ++c) {
            }
        }
    }

    return 0;
}

在大多数情况下，代码按我预期的方式工作。我不明白为什么它会停止回避 a + b + c = 1000。

我最后的三胞胎是 280 < 294 < 406，总计 980。

如果我删除 a < b < c 检查，三元组变为 332、249、415，总计 996。

所有结果都符合毕达哥拉斯定理——我就是不能得到 a + b + c = 1000。

是什么阻碍了我？

Answer 1

这部分代码迭代的很奇怪:

for(a = 1; a < b; ++a) {
    for(b = 2; b < c; ++b) {
        for(c = 3; a + b + c != 1000 && !isPythagorean(a, b, c); ++c) {
        }
    }
}

最初，a = 1, b = 2, c = 3。但是在第一次 for(c) 时，c=997，所以 for(b) 的第二次迭代将运行到 b=996。一直这样做，到某个时候你会发现一个三元组(a,b,c)，那时候c可能还没有接近1000，b会迭代起来到 c 所在的任何状态......等等。我认为您无法准确预测它会如何生成三元组。

我建议你选择类似的东西

for(a = 1; 3*a < 1000; ++a) {
    for(b = a+1; a+2*b < 1000; ++b) {
        for(c = b+1; a + b + c != 1000 && !isPythagorean(a, b, c); ++c) {
        }
    }
}

这样，循环就不会依赖于之前找到的三元组。

...你真的应该使用欧几里德的方法。