OneCoder Avatar
OneCodercoderli.com · 1023 篇博文
二级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++二级练习 luogu-B3845, [GESP样题 二级] 勾股数

📅 2025-01-06·✍️ OneCoder·计算中...·⏱️ 5 分钟

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

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

题目要求

题目描述

勾股数是很有趣的数学概念。如果三个正整数 ,满足 ,而且 ,我们就将 组成的三元组 称为勾股数。你能通过编程,数数有多少组勾股数,能够满足 吗?

输入格式

输入一行,包含一个正整数 。约定 。

输出格式

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

样例输入 #1

CONSOLE1 行
5

样例输出 #1

CONSOLE1 行
1

样例输入 #2

CONSOLE1 行
13

样例输出 #2

CONSOLE1 行
3

提示

【样例解释 1】

满足 的勾股数只有 一组。

【样例解释 2】

满足 的勾股数有 组,即 、 和 。


题目分析

思路一

思路一的解题思路总结:

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

这种方法的时间复杂度为 ,因为有三层循环,每层循环的时间复杂度为 。

思路二

  1. 读取输入的最大值 。
  2. 使用两层循环,外层循环控制 的值,内层循环控制 的值。
  3. 在内层循环中,计算 ,并判断 是否小于等于 。
  4. 如果 符合条件,计数器 加1。
  5. 循环结束后,输出 的值,即为所求的勾股数的数量。

示例代码

方案一

3层循环,暴力匹配。复杂度

C++18 行
#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;
}

方案二

两层循环,结果检查。复杂度

C++18 行
#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; // 返回程序执行成功
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!