[GESP样题 二级] 勾股数

GESP二级练习，多层循环嵌套和数学函数练习，难度★✮☆☆☆。

luogu-B3845 [GESP样题 二级] 勾股数

题目要求

题目描述

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

输入格式

输入一行，包含一个正整数 $n$。约定 $1 \le n \le 1000$。

输出格式

输出一行，包含一个整数 $C$，表示有 $C$ 组满足条件的勾股数。

样例输入 #1

5

样例输出 #1

1

样例输入 #2

13

样例输出 #2

3

提示

【样例解释 1】

满足 $c \leq 5$ 的勾股数只有 $(3,4,5)$ 一组。

【样例解释 2】

满足 $c \le 13$ 的勾股数有 $3$ 组，即 $(3,4,5)$、$(6,8,10)$ 和 $(5,12,13)$。

题目分析

思路一

思路一的解题思路总结：

1. 读取输入的最大值 $n$。
2. 使用三层循环，外层循环控制 $a$ 的值，中层循环控制 $b$ 的值，内层循环控制 $c$ 的值。
3. 在内层循环中，判断 $a^2 + b^2$ 是否等于 $c^2$，并且 $c$ 是否小于等于 $n$。
4. 如果条件满足，计数器 $count$ 加1。
5. 循环结束后，输出 $count$ 的值，即为所求的勾股数的数量。

这种方法的时间复杂度为 $O(n^3)$，因为有三层循环，每层循环的时间复杂度为 $O(n)$。

思路二

1. 读取输入的最大值 $n$。
2. 使用两层循环，外层循环控制 $a$ 的值，内层循环控制 $b$ 的值。
3. 在内层循环中，计算 $c = \sqrt{a^2 + b^2}$，并判断 $c$ 是否小于等于 $n$。
4. 如果 $c$ 符合条件，计数器 $count$ 加1。
5. 循环结束后，输出 $count$ 的值，即为所求的勾股数的数量。

{% include custom/custom-post-content-inner.html %}

示例代码

方案一

3层循环，暴力匹配。复杂度$O(n^3)$

#include <iostream>
using namespace std;
int main() {
    int n; // 输入的最大值
    cin >> n; // 读取输入的最大值
    int count = 0; // 计数器，用于统计勾股数的数量
    for (int i = 1; i <= n; i++) { // 外层循环，控制i的值
        for (int j = i; j <= n; j++) { // 中层循环，控制j的值
            for (int k = j; k <= n; k++) { // 内层循环，控制k的值
                if (i * i + j * j == k * k) { // 判断是否为勾股数
                    count++; // 如果是，计数器加1
                }
            }
        }
    }
    cout << count; // 输出计数器的值，即勾股数的数量
    return 0;
}

方案二

两层循环，结果检查。复杂度$O(n^2)$

#include <cmath>
#include <iostream>
using namespace std;
int main() {
    int n; // 定义变量n
    cin >> n; // 读取n的值
    int count = 0; // 初始化计数器
    for (int i = 1; i <= n; i++) { // 外层循环，控制i的值
        for (int j = i; j <= n; j++) { // 内层循环，控制j的值
            int c = sqrt(i * i + j * j); // 计算c的值
            if (c * c == j * j + i * i && c <= n) { // 判断是否为勾股数
                count++; // 如果是，计数器加1
            }
        }
    }
    cout << count; // 输出计数器的值
    return 0; // 返回程序执行成功
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号