java - 为什么我的程序在某些情况下会给出错误的输出？

Question

我已经用 Java 实现了欧几里德算法，以找到两个给定数字的最大公约数 (GCD)。

在大多数情况下，我的程序运行良好，我已经用几组随机数字对其进行了测试，不过，我发现在一种情况下(据我所知)它给出了不正确的输出，这是为了以下数字组合:

Enter integer a: 8965Enter integer b: 55

程序的输出应该是55，但事实并非如此。给出的输出如下:

gcd = 1Execution time: 0.005747ms.

我不确定为什么这种特定的数字组合会导致问题，因为它适用于其他数字，例如，这是一组不同数字的结果:

Enter integer a: 15000

Enter integer b: 5325

gcd = 75

Execution time: 0.007389ms.

import java.util.Scanner;
public class EuclideanAlgorithm {
    public static void main (String [] args) {
        int a, b;
        try(Scanner sc = new Scanner(System.in);) {
            System.out.print("Enter integer a: ");
            a = sc.nextInt();
            System.out.print("Enter integer b: ");
            b = sc.nextInt();
        }
        long start = System.nanoTime();
        int answer = EuclideanAlgorithm(a, b);
        long stop = System.nanoTime();
        System.out.println("gcd = " + answer);
        System.out.println("Execution time: " + ((stop - start) / 1e+6) + "ms.");
        
    }
    
    public EuclideanAlgorithm() {}; //Suppress default constructor
    
    private static int EuclideanAlgorithm(int a, int b) {
        if ( (a == 0) || (b == 0)) {
            return 0;
        }
        if (b > a) {
            int temp = a;
            a = b;
            b = temp;
        }
        int gcd = 1;
        while(gcd != 0) {
            if( (a % b) == 0) {
                break;
            }
            gcd = a % b;
            a  = b;
            b = gcd;
        }
        return gcd;
    }
}

Answer 1

只要您的数字 a、b 中的一个是另一个的倍数，那么您的 if 条件将导致 break 和 1 将被返回，这是不正确的。但是算法的其余部分也不正确。

根据Euclidean Algorithm的伪代码:

function gcd(a, b)
while b ≠ 0
   t := b
   b := a mod b
   a := t
return a

您需要检查b 是否不是0，而不是gcd。您需要修改代码以匹配此算法；您的代码当前不匹配该算法。