java - 使用欧几里得算法查找最大公约数

Question

我试图找出一个解决方案，通过它我可以以最佳方式找到 2 个数字的 GCD，因此，我需要一些帮助来弄清楚我提出的程序是否适用于所有可能的情况，或者是否有任何情况会崩溃，或者我可以进一步改进它以使其成为最佳解决方案。

程序:

public static void main(String[] args) {
     int a= 153;
        int b= 81;
        boolean flag = true;
        int gcd = 1;
        while(flag)
        {
          if(a>b && a%b ==0)
           {
                flag = false;
                gcd = b;
            }
            else if(b>a && b%a ==0)
            {
                flag=false;
                gcd = a;
            }
            else if( a>b)
            a = a-b;
            else
            b = b-a;
        }
        System.out.println(gcd);

}

请帮助我找出正确的解决方案，提前致谢。

Answer 1

尝试这样的事情。欧几里得 GCD 算法基本上是这样说的:2 个数字(我们称它们为较大和较小)的 GCD 等于较小数字的 GCD 以及较大和较小数字之间的差。重复该过程直到两个数字相同。下面是迭代解决方案。

    int a= 153 , b = 81, gcd = 1;

    while( gcd != a ) {

        if( a > b ) a -= b;
        else if( b > a) b -= a;
        else gcd = a;
    }

    System.out.println(gcd);

这是递归解决方案。希望这会有所帮助。

    public static int euclidGCD(int a, int b) {
        if (b == a) return a;
        if (b > a)  return euclidGCD(b - a, a);
        else  return euclidGCD(a - b, b);
}

这是对您的程序的修改。要测试一个程序，最好的办法就是写下它的条件和案例。在此练习中有两个条件:

• 1.) 数字必须是整数
• 2.) 数字必须为正数。

处理数字通常有离散数量的情况。在本练习中有两种情况:

• 1.) 数字是相等的。
• 2.) 数字不同。

当 a 等于 b 时，您的代码不正确(请自行尝试)。当数字不同时，您的代码可以正常工作。以下是修改。

    int a= 55;
    int b= 55;
    boolean flag = true;
    int gcd = b;
    while(flag && b != a)
    {
        if(a>b && a%b ==0)
        {
            flag = false;
            gcd = b;
        }
        else if(b>a && b%a ==0)
        {
            flag=false;
            gcd = a;
        }
        else if( a>b)
            a = a-b;
        else
            b = b-a;
    }
    System.out.println(gcd);