如何编写一个简单的Java程序来找到两个数字之间最大的公约数？

loops java while-loop greatest-common-divisor

2022-09-04 23:59:48

问题是：

“编写一个名为gcd的方法，该方法接受两个整数作为参数，并返回两个数字的最大公约数。两个整数 a 和 b 的最大公约数（GCD）是 a 和 b 的因子的最大整数。任何数字和 1 的 GCD 是 1，任何数字和 0 的 GCD 是该数字。

计算两个数字的GCD的一种有效方法是使用欧几里得算法，该算法声明如下：

GCD(A, B) = GCD(B, A % B) 
GCD(A, 0) = Absolute value of A"

我对如何解决这个问题感到非常困惑。我只想得到一些提示和技巧，说明到目前为止我在程序中做错了什么。（我必须放一台扫描仪，这是我老师的要求。不要给我一个完整的代码，因为我有点想自己解决这个问题。也许只是给我一个提示，说明我如何结合你上面看到的这个公式。（如果你想知道为什么我输入==0，那是因为我认为如果你有两个数字，比如0和90，他们的GCD将是0对吧？？）

另外，我的代码必须包含 while 循环...我宁愿循环...

提前致谢！:)

我目前的计划：

public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
        int a = console.nextInt();
        int b = console.nextInt();
        gcd (a, b);
    }

    public static void gcd(int a, int b) {
        System.out.print("Type in two numbers and I will print outs its Greatest Common Divisor: ");
        int gcdNum1 = console.nextInt();
        int gcdNum2 = console.nextInt();
        while (gcdNum1 == 0) {
            gcdNum1 = 0;
        }
        while (gcdNum2 > gcdNum1) {
            int gcd = gcdNum1 % gcdNum2;
        }
        System.out.print(gcdNum1 + gcdNum2);
    }
}

答案 1

递归方法是：

static int gcd(int a, int b)
{
  if(a == 0 || b == 0) return a+b; // base case
  return gcd(b,a%b);
}

使用 while 循环：

static int gcd(int a, int b)
{
  while(a!=0 && b!=0) // until either one of them is 0
  {
     int c = b;
     b = a%b;
     a = c;
  }
  return a+b; // either one is 0, so return the non-zero value
}

当我返回时，我实际上返回了非零数字，假设其中一个是0。a+b

答案 2

您也可以使用三行方法执行此操作：

public static int gcd(int x, int y){
  return (y == 0) ? x : gcd(y, x % y);
}

这里，如果返回 x。否则，将再次调用具有不同参数值的方法。y = 0gcd