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

问题是:

“编写一个名为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


推荐