-3

Euclid 算法告诉我们如何计算两个正整数和的最大公约数(GCD) 。使用欧几里得算法,求 和 的 GCD (例如),首先求除以时的余数。然后再次使用相同的想法找到 和这个余数(结果是)的 GCD 。当您到达第二个数字为 的点时,第一个数字将是您要查找的 GCD , 如下所示。ab2064020640406020640

gcd(206, 40)
= gcd(40, 6)
= gcd(6, 4)
= gcd(4, 2)
= gcd(2, 0)
= 2

编写一个名为gcd. 您必须在此方法中使用递归(在方法中调用方法)。此方法应使用欧几里得算法返回两个正整数的最大公约数。

所以基本上我不知道如何用递归来做到这一点(对不起,我之前没有意外写过)递归..请帮忙!:(我已经坚持了这么久..我写了一个方法,但它不使用递归,它只适用于给定的20640..

4

1 回答 1

4

使用递归很容易实现:

public int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

该算法在Wikipedia 页面中进行了说明。

于 2013-09-13T15:29:15.853 回答