【华为OD机试真题 C语言】19、勾股数元组 | 机试真题+思路参考+代码解析

文章目录

• • 一、题目
  • • 🎃题目描述
    • 🎃输入输出
    • 🎃样例1
    • 🎃样例2
  • 二、思路参考
  • 三、代码参考
• 作者：KJ.JK

🍂个人博客首页： KJ.JK
 
🍂专栏介绍： 华为OD机试真题汇总，定期更新华为OD各个时间阶段的机试真题，每日定时更新，本专栏将使用C语言进行更新解答，包含真题，思路分析，代码参考，欢迎大家订阅学习

一、题目

🎃题目描述

如果3个正整数(a,b,c)满足a2 + b2 = c2的关系，则称(a,b,c)为勾股数（著名的勾三股四弦五），
 
为了探索勾股数的规律，我们定义如果勾股数(a,b,c)之间两两互质（即a与b，a与c，b与c之间均互质，没有公约数），则其为勾股数元组（例如(3,4,5)是勾股数元组，(6,8,10)则不是勾股数元组）。
 
请求出给定范围[N,M]内，所有的勾股数元组。

🎃输入输出

输入
起始范围N，1 <= N <= 10000
结束范围M，N < M <= 10000
 
输出
1、a,b,c请保证a < b < c,输出格式：a b c；
2、多组勾股数元组请按照a升序，b升序，最后c升序的方式排序输出；
3、给定范围中如果找不到勾股数元组时，输出”NA“。

🎃样例1

输入
120输出
3 4 55 12 138 15 17说明：[1, 20]范围内勾股数有：(3 4 5)，(5 12 13)，(6 8 10)，(8 15 17)，(9 12 15)，(12 16 20)；其中，满足(a,b,c)之间两两互质的勾股数元组有：(3 4 5)，(5 12 13)，(8 15 17)；按输出描述中顺序要求输出结果。

🎃样例2

输入
5
10输出
NA说明：
[5, 10]范围内勾股数有：(6 8 10)；其中，没有满足(a,b,c)之间两两互质的勾股数元组；给定范围中找不到勾股数元祖，输出”NA“

二、思路参考

1、首先，我们需要编写一个函数来判断两个数是否互质。互质的条件是它们的最大公约数为 1。我们可以使用辗转相除法来求两个数的最大公约数。如果最大公约数为 1，则两个数互质。

2、接下来，我们可以使用两重循环遍历范围 [N, M] 内的所有数对 (a, b)，其中 N <= a < b <= M。对于每个数对，我们计算 c 的值，并判断是否满足勾股数条件和两两互质条件。

3、勾股数条件是 a^2 + b^2 = c^2。我们计算 c 的平方，然后取其平方根，将结果转换为整数。如果平方根的整数部分的平方等于 c 的平方，则满足勾股数条件。

4、在判断勾股数条件的基础上，我们还需要判断 (a, b, c) 是否两两互质。即判断 a 和 b、a 和 c、b 和 c 是否互质。我们可以调用之前编写的判断互质的函数进行判断。

5、如果满足勾股数条件和两两互质条件，将勾股数元组 (a, b, c) 添加到结果集合中。

6、最后，我们对结果集合进行排序，按照 a 升序、b 升序、最后 c 升序的方式排序。

根据题目要求的输出格式，按照每个勾股数元组一行的形式输出结果。

如果在给定范围内找不到勾股数元组，则输出 “NA”。

三、代码参考

#include 
#include 
#include // 判断两个数是否互质
bool areCoprime(int a, int b) {int temp;while (b != 0) {temp = b;b = a % b;a = temp;}return a == 1;
}int main() {int N, M;scanf("%d %d", &N, &M);bool found = false; // 标记是否找到勾股数元组for (int a = N; a < M; a++) {for (int b = a + 1; b < M; b++) {int c_square = a * a + b * b;int c = (int)sqrt(c_square);if (c * c == c_square && areCoprime(a, b) && areCoprime(a, c) && areCoprime(b, c)) {printf("%d %d %d\n", a, b, c);found = true;}}}if (!found) {printf("NA\n");}return 0;
}

作者：KJ.JK

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！