如何编写一个简单的Java程序，找到两个数字之间最大的公约数？ [英] How to write a simple Java program that finds the greatest common divisor between two numbers?

问题描述

这是一个问题：

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

"Write a method named gcd that accepts two integers as parameters and returns the greatest common divisor of the two numbers. The greatest common divisor (GCD) of two integers a and b is the largest integer that is a factor of both a and b. The GCD of any number and 1 is 1, and the GCD of any number and 0 is that number.

计算两个数字的GCD的一种有效方法是使用Euclid算法，该算法说明如下：

One efficient way to compute the GCD of two numbers is to use Euclid's algorithm, which states the following:

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

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

I'm really confused as to how to solve this problem. I just want some hints and tips as to what I did wrong in the program I have so far. (I have to put in a Scanner, that is my teacher's requirement.) Don't give me a full code as I kinda want to solve this out myself. Maybe just give me a hint on how I incorporate this formula that you see above. (And if you're wondering why I put in the == 0, it's because I thought that if you have two numbers, say 0 and 90, their GCD would be 0 right??)

另外，我的代码必须包含while循环......如果循环我会更喜欢...

Also, my code has to include while loops...I would've preferred if loops...

提前致谢！ ：）

我当前的程序：

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);
    }
}

推荐答案

A递归方法是：

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
}

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

When I'm returning a+b, I'm actually returning the non-zero number assuming one of them is 0.

这篇关于如何编写一个简单的Java程序，找到两个数字之间最大的公约数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！