蓝桥杯 勾股数 暴力

问题描述

　　勾股数是一组三个自然数，a < b < c，以这三个数为三角形的三条边能够形成一个直角三角形
　　输出所有a + b + c <= 1000的勾股数
　　a小的先输出；a相同的，b小的先输出。

输出格式

　　每行为一组勾股数，用空格隔开

样例输出

例如，结果的前三行应当是
3 4 5
5 12 13
6 8 10

水题，不过有些思考还是对我挺有帮助的。

我第一版代码长这样。

#include <bits/stdc++.h>
using namespace std;
int main() {
    for (int i = 1; i <= 1000; i++) {
        for (int j = 1; j <= 1000; j++) {
            for (int k = 1; k <= 1000; k++) {
                if (i + j + k <= 1000 && i * i + j * j == k * k) {
                    cout << i << " " << j << " " << k << endl;
                }
            }
        }
    }
    return 0;
}

然后时间复杂度10^9。

然后看到题目要求a小的先输出，然后b小的输出，然后c小的输出。

然后就可以改成这样。

#include <bits/stdc++.h>
using namespace std;
int main() {
    for (int i = 3; i <= 1000; i++) {
        for (int j = i + 1; j <= 1000; j++) {
            for (int k = j + 1; k <= 1000; k++) {
                if (i + j + k <= 1000 && i * i + j * j == k * k) {
                    cout << i << " " << j << " " << k << endl;
                }
            }
        }
    }
    return 0;
}

这样就保证了a小的先输出，然后b小的输出，然后c小的输出。

然后还可以再减去多余的运算，所以最外层可以改为 for (int i = 3; i <= 333; i++)。因为333+334+335就大于1000了。同理对第二层的范围修改一下，第三层就不能大改了。

然后就是时间复杂度较小的最终版代码了。

#include <bits/stdc++.h>
using namespace std;
int main() {
    for (int i = 3; i <= 333; i++) {
        for (int j = i + 1; j <= 500; j++) {
            for (int k = j + 1; k <= 999; k++) {
                if (i + j + k <= 1000 && i * i + j * j == k * k) {
                    cout << i << " " << j << " " << k << endl;
                }
            }
        }
    }
    return 0;
}