21.3 数学问题的嵌套循环解法

“嵌套循环在解决数学问题时非常有用，”我继续解释道，”尤其是在需要遍历多个变量的组合时，嵌套循环能够系统地探索所有可能性。”

21.3.1 勾股数

题目描述：勾股数是很有趣的数学概念。如果三个正整数a,b,c，满足a²+b²=c²，而且1≤a≤b≤c，我们就将a,b,c组成的三元组(a,b,c)称为勾股数。你能通过编程，数数有多少组勾股数，能够满足c≤n吗？

样例输入：

20

样例输出：

3

代码实现（方法一：三重循环）：

#include <iostream>
using namespace std;

int main() {
    int n, cnt = 0;  // n为上限值，cnt为满足条件的勾股数组数
    cin >> n;
    for(int a = 1; a <= n; a++) {  // 遍历可能的a值
        for(int b = a; b <= n; b++) {  // 遍历可能的b值，保证b>=a
            for(int c = b; c <= n; c++) {  // 遍历可能的c值，保证c>=b
                if(a*a + b*b == c*c) {  // 检查是否满足勾股定理
                    cnt++;  // 如果满足，计数器加1
                }
            }
        }
    }
    cout << cnt;  // 输出满足条件的组数
    return 0;
}

代码实现（方法二：优化解法）：

#include <iostream>
#include <cmath>  // 包含sqrt函数所需的头文件
using namespace std;

int main() {
    int n, cnt = 0;  // n为上限值，cnt为满足条件的勾股数组数
    cin >> n;
    for(int a = 1; a <= n; a++) {  // 遍历可能的a值
        for(int b = a; b <= n; b++) {  // 遍历可能的b值，保证b>=a
            int c = sqrt(a*a + b*b);  // 根据勾股定理计算可能的c值
            bool f1 = c*c == a*a + b*b;  // 检查c是否为整数（通过平方后是否相等判断）
            bool f2 = c <= n;  // 检查c是否不超过上限n
            if(f1 && f2) {  // 如果同时满足两个条件
                cnt++;  // 计数器加1
            }
        }
    }
    cout << cnt;  // 输出满足条件的组数
    return 0;
}

思考：

• 方法一使用三重循环，时间复杂度为O(n³)
• 方法二只使用两重循环，时间复杂度为O(n²)
• 方法二利用了勾股定理计算c值，大大减少了循环次数
• 注意使用sqrt函数需要包含cmath头文件