算法刷题1-勾股元组数

2023-08-25 11:35:18 浏览数 (2)

题目1：勾股元组数

如果三个正整数A、B、C ,A² B²=C²则为勾股数

如果ABC之间两两互质，即A与B，A与C，B与C均互质没有公约数，则称其为勾股数元组

请求出给定n~m范围内所有的勾股数元组式。

输入描述

起始范围

代码语言：javascript复制
1 < n < 10000
n < m < 10000
1
2

输出描述

ABC保证A<B<C；输出格式A B C

多组勾股数元组，按照A B C升序的排序方式输出。

若给定范围内，找不到勾股数元组时，输出Na。

关键点

  1. a b 互质，即 a 和 b 的公约数为1

概念：公约数只有1的两个数叫做互质数。根据互质数的概念可以对一组数是否互质进行判断。如：3和11的公约数只有1，则它们是互质数。

​

这里用阿基里德算法（辗转相除法），递归方式，如果最后结果==1，表示a,b 互质

gcd(a,b) = gcd(b, a%b)

  1. i，j，k 用穷举法得出，满足条件 i<j<k，且 i,j,k 两两互质

Java版本

参考了一个博主的Java版本

代码语言：javascript复制
public class Main0001 {
  public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
      int n = scanner.nextInt();
      int m = scanner.nextInt();
      solution(n, m);
    }
  }

  private static void solution(int n, int m) {
    int count = 0;
    for (int a = n; a < m - 1; a  ) {
      for (int b = a   1; b < m; b  ) {
        for (int c = b   1; c < m   1; c  ) {
          if (relativelyPrime(a, b) &&
              relativelyPrime(b, c) &&
              relativelyPrime(a, c) &&
              a * a   b * b == c * c) {
            count  ;
            System.out.printf("%d %d %dn", a, b, c);
          }
        }
      }
    }
    if (count == 0) {
      System.out.println("Na");
    }
  }

  private static boolean relativelyPrime(int x, int y) {
    if (x == y && y == 1) {
        return false;
    }
    int min = Math.min(x, y);
    for (int i = 2; i <= min; i  ) {
        if (x % i == 0 && y % i == 0) {
            return false;
        }
    }
    return true;
  }
}

两个数是否互质

代码语言：javascript复制
def isPrime(x,y):
    """
    作用：
        判断两个数是否互质
    参数：
        提供两个数:x,y
    返回值：
        布尔值
    """
    if x == y and y == 1:
        return False

    min_ = min(x,y)

    for i in range(2, min_   1):
        if x % i == 0 and y % i == 0: # 余数为0，说明此时i就是二者的另一个公约数（且i>=2）
            return False
    else:
        return True
代码语言：javascript复制
isPrime(1,1)
代码语言：javascript复制
False
代码语言：javascript复制
isPrime(2,9)
代码语言：javascript复制
True
代码语言：javascript复制
isPrime(3,8)
代码语言：javascript复制
True
代码语言：javascript复制
isPrime(3,15)
代码语言：javascript复制
False

Python勾股元组数判断

个人改成Python版本

代码语言：javascript复制
def isPrime(x,y):
    """
    作用：
        判断两个数是否互质
    参数：
        提供两个数:x,y
    返回值：
        布尔值
    """
    if x == y and y == 1:
        return False

    min_ = min(x,y)

    for i in range(2, min_   1):
        # 余数为0，说明此时i就是二者的另一个公约数（且i>=2）
        if x % i == 0 and y % i == 0:
            return False
    else:
        return True  # for循环完之后没有满足的i，就说明二者是互质的-True


def gou_gu(m,n):
    flag = False
    for a in range(m, n-1):
        for b in range(a 1, n):
            for c in range(b 1, n 1):
                if isPrime(a,b) and isPrime(a,c) and isPrime(b,c) and a**2   b**2 == c**2:
                    print(f"{a}n{b}n{c}")
                    print("*" * 20)
                    # 只要出现了勾股数，标志位变成True
                    flag = True

    if not flag:
        print("Na")
代码语言：javascript复制
gou_gu(3,9)
代码语言：javascript复制
3
4
5
********************
代码语言：javascript复制
gou_gu(3,20)
代码语言：javascript复制
3
4
5
********************
5
12
13
********************
8
15
17
********************
代码语言：javascript复制
gou_gu(8,20)
代码语言：javascript复制
8
15
17
********************
代码语言：javascript复制
gou_gu(5,20)
代码语言：javascript复制
5
12
13
********************
8
15
17
********************
int min return 递归 算法

0 人点赞