华为OD机试真题---勾股数元组

华为OD机试中的“勾股数元组”题目是一道考察编程能力、算法基础和数学知识的题目。以下是对该题目的详细解析：

一、题目描述

如果三个正整数(a, b, c)满足a²+b²=c²的关系，则称(a, b, c)为勾股数。为了探索勾股数的规律，题目要求找到给定范围[N, M]内所有的勾股数元组，其中勾股数元组是指勾股数(a, b, c)之间两两互质（即a与b，a与c，b与c之间均互质，没有公约数）。

二、输入与输出

• 输入描述：起始范围N和结束范围M，其中1≤N<M≤10000。
• 输出描述：在给定范围内找到的所有勾股数元组(a, b, c)，并保证a<b<c。多组勾股数元组需要按照a升序、b升序、最后c升序的方式排序输出。如果给定范围内找不到勾股数元组，则输出“NA”。

三、解题思路

1. 遍历范围：首先，需要遍历给定范围[N, M]内的所有可能的a、b组合。
2. 计算c：对于每一对(a, b)，根据勾股定理计算c的值，即c=√(a²+b²)。由于a、b、c都是正整数，因此需要判断c是否为整数。
3. 判断互质：如果c是整数，接下来需要判断(a, b, c)是否两两互质。可以使用辗转相除法（欧几里得算法）来判断两个数是否互质。
4. 输出结果：将满足条件的勾股数元组按照要求排序并输出。

四、示例

• 示例输入：
  示例1：

1 20

• 示例输出：

3 4 5
5 12 13
8 15 17

示例2：

1 100

• 示例输出：

3 4 5
5 12 13
7 24 25
8 15 17
9 40 41
11 60 61
12 35 37
13 84 85
16 63 65
20 21 29
20 99 101
28 45 53
33 56 65
36 77 85
39 80 89
48 55 73
60 91 109
65 72 97

五、代码实现

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PythagoreanTriples {

    /**
     * 检查两个数是否互质
     * 互质的定义是，两个或多个整数的公约数只有1时，这些整数被称为互质整数
     * 判定两个数是否互质的算法基于欧几里得算法，通过逐步取余数来判断两个数的最大公约数是否为1
     * 
     * @param a 第一个整数
     * @param b 第二个整数
     * @return 如果两个数互质，返回true；否则返回false
     */
    private static boolean isCoprime(int a, int b) {
        // 使用欧几里得算法计算最大公约数
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        // 最大公约数为1时，两数互质
        return a == 1;
    }

    /**
     * 检查三个数是否互质
     * 互质意味着这三个数的最大公约数为1
     * @param a 第一个整数
     * @param b 第二个整数
     * @param c 第三个整数
     * @return 如果三个数互质返回true，否则返回false
     */
    private static boolean areCoprime(int a, int b, int c) {
        return isCoprime(a, b) && isCoprime(a, c) && isCoprime(b, c);
    }

    // 主方法，用于找到并打印勾股数元组
    public static void main(String[] args) {
        // 使用Scanner读取用户输入的两个整数N和M
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        // 关闭Scanner，释放资源
        scanner.close();

        // 初始化一个列表，用于存储找到的勾股数元组
        List<String> triples = new ArrayList<>();

        // 遍历所有可能的a和b，其中a < b
        for (int a = N; a < M; a++) {
            for (int b = a + 1; b < M; b++) {
                // 计算a² + b²的结果，使用long避免溢出
                long cSquared = (long) a * a + (long) b * b;
                // 计算c的值，即a² + b²的平方根
                int c = (int) Math.sqrt(cSquared);

                // 检查c是否为整数且c²是否等于a² + b²（避免浮点数误差）
                // 同时检查a、b、c是否互质
                if ((long) c * c == cSquared && c > b && areCoprime(a, b, c)) {
                    // 如果满足勾股定理且互质，则将这个元组添加到列表中
                    triples.add(a + " " + b + " " + c);
                }
            }
        }

        // 检查是否找到勾股数元组，并打印结果
        if (triples.isEmpty()) {
            // 如果没有找到，打印"NA"
            System.out.println("NA");
        } else {
            // 如果找到了，遍历列表并打印每个勾股数元组
            for (String triple : triples) {
                System.out.println(triple);
            }
        }
    }
}

六、运行示例解析

假设输入如下：

1 20

运行过程及输出：
1、读取用户输入的两个整数N和M：

 int N = scanner.nextInt(); // N = 1
   int M = scanner.nextInt(); // M = 20

2、关闭Scanner，释放资源：

  scanner.close();

3、初始化一个列表，用于存储找到的勾股数元组：

 List<String> triples = new ArrayList<>();

4、遍历所有可能的a和b，其中a < b：

• 外层循环：a从1到19
  • 内层循环：b从a+1到19
• 具体计算过程：
  • a = 3, b = 4

   long cSquared = (long) 3 * 3 + (long) 4 * 4; // cSquared = 9 + 16 = 25
   int c = (int) Math.sqrt(25); // c = 5
   if ((long) 5 * 5 == 25 && 5 > 4 && areCoprime(3, 4, 5)) {
       // 25 == 25, 5 > 4, 3, 4, 5互质
       triples.add("3 4 5");
   }
   

• a = 5, b = 12

// cSquared = 25 + 144 = 169
long cSquared = (long) 5 * 5 + (long) 12 * 12; 
int c = (int) Math.sqrt(169); // c = 13
if ((long) 13 * 13 == 169 && 13 > 12 && areCoprime(5, 12, 13)) {
// 169 == 169, 13 > 12, 5, 12, 13互质
triples.add("5 12 13");
}

• a = 8, b = 15

long cSquared = (long) 8 * 8 + (long) 15 * 15; // cSquared = 64 + 225 = 289
   int c = (int) Math.sqrt(289); // c = 17
   if ((long) 17 * 17 == 289 && 17 > 15 && areCoprime(8, 15, 17)) {
       // 289 == 289, 17 > 15, 8, 15, 17互质
       triples.add("8 15 17");
   }
   

• 其他组合：
  • 其他组合如 (4, 5), (6, 8), (7, 24), (9, 12), (12, 16) 等，虽然满足勾股定理，但不互质，因此不会被添加到列表中。

5、检查是否找到勾股数元组，并打印结果：

   if (triples.isEmpty()) {
       // 如果没有找到，打印"NA"
       System.out.println("NA");
   } else {
       // 如果找到了，遍历列表并打印每个勾股数元组
       for (String triple : triples) {
           System.out.println(triple);
       }
   }

输出结果：

3 4 5
5 12 13
8 15 17

解释

• 3 4 5：这是一个经典的勾股数元组，3² + 4² = 5²，且3、4、5互质。
• 5 12 13：5² + 12² = 13²，且5、12、13互质。
• 8 15 17：8² + 15² = 17²，且8、15、17互质。
  这些元组都满足勾股定理并且互质，因此被添加到列表中并最终打印出来。

七、注意事项

1. 范围限制：题目给定的范围较大（1≤N<M≤10000），因此需要优化算法以提高效率。
2. 精度问题：在计算c的值时，需要注意精度问题。由于浮点数运算可能存在误差，因此需要判断c是否为完全平方数的整数根。
3. 输出格式：输出时需要按照题目要求的格式进行排序和输出。

综上所述，华为OD机试中的“勾股数元组”题目是一道考察编程能力、算法基础和数学知识的综合性题目。通过遍历范围、计算c的值、判断互质以及输出结果等步骤，可以找到给定范围内的所有勾股数元组。

八、后续应用优化建议

1. 算法优化：

   • 减少不必要的计算：在遍历a和b的过程中，可以通过一些数学性质来减少不必要的计算。例如，由于a < b < c，因此当a固定时，b的取值范围可以进一步缩小为[a+1, √(M²-a²)]（其中M为给定范围的上界）。这是因为当b > √(M²-a²)时，即使c是整数，c也会大于M，从而不满足题目要求。

   • 使用更高效的数据结构：虽然题目中的数据规模不是特别大（1≤N<M≤10000），但在处理大规模数据时，可以考虑使用更高效的数据结构来存储和查找勾股数元组。例如，可以使用哈希表来存储已经找到的勾股数元组，以便在后续计算中快速判断某个元组是否已经存在。

   • 并行计算：对于更大的数据范围，可以考虑使用并行计算来提高效率。例如，可以将数据范围划分为多个子区间，并在不同的线程或处理器上并行计算每个子区间内的勾股数元组。

2. 实现细节：

   • 精度处理：在计算c的值时，需要注意精度问题。由于浮点数运算可能存在误差，因此需要判断c是否为完全平方数的整数根。这可以通过比较c²与a²+b²是否相等来实现。

   • 输入与输出：在处理输入和输出时，需要注意格式和顺序。输入需要读取两个整数N和M，输出需要按照a升序、b升序、c升序的方式排序并打印勾股数元组。如果找不到符合条件的勾股数元组，则需要输出“NA”。

   • 异常处理：在编写代码时，还需要考虑异常处理的情况。例如，当输入的N或M不满足题目要求时（如N大于M或N小于1等），需要给出相应的提示信息并退出程序。

九、数学背景与扩展

1. 勾股定理：

   • 勾股定理是直角三角形三边之间关系的数学定理。它表明，在直角三角形中，直角边的平方和等于斜边的平方。即，如果直角三角形的两条直角边分别为a和b，斜边为c，则满足a²+b²=c²。

   • 勾股定理不仅适用于直角三角形，还可以推广到更高维度的空间中。例如，在三维空间中，可以定义勾股四面体，其四边之间的关系也满足类似的定理。

2. 互质：

   • 互质是两个或多个整数的数学概念。如果两个或多个整数的公约数只有1，则称这些整数互质。例如，3和4互质，因为它们的公约数只有1；而6和8不互质，因为它们的公约数有1和2。

   • 互质在数论和密码学等领域有着广泛的应用。例如，在RSA加密算法中，需要选择两个大素数p和q，并计算它们的乘积n作为公钥的一部分。而p和q的选择需要满足一定的条件，其中之一就是它们需要互质。

3. 扩展数学内容：

   • 除了勾股定理和互质之外，这道题目还可以扩展到其他数学领域的内容。例如，可以研究勾股数元组的生成规律、勾股数在几何图形中的应用等。

   • 此外，还可以将这道题目与数论中的其他问题相结合，如费马小定理、欧拉定理等，以形成更具挑战性的数学问题。