Java实现最大公约数算法及案例分析 |21xrx.com

2023-06-14 15:33:59 深夜i -- --

最大公约数 Java 代码案例

在Java中，求最大公约数的算法有很多种，其中最常用的是辗转相除法和更相减损法。下面我们将介绍这两种算法的具体实现，并结合代码案例进行分析。

1.辗转相除法

辗转相除法又称欧几里得算法，其原理是两个正整数a和b(a>b)的最大公约数等于a除以b的余数c和b之间的最大公约数。具体实现流程如下：

（1）计算a除以b的余数c

（2）如果c为0，则b就是最大公约数

（3）如果c不为0，则a=b，b=c，再回到第（1）步

代码实现：

public static int gcd(int a, int b) {

if (b == 0)

return a;

else {

return gcd(b, a % b);

}

2.更相减损法

更相减损法是古老的一种求最大公约数的方法，它的原理是两个正整数a和b(a>b)的最大公约数等于a-b的差值c和较小数b之间的最大公约数。具体实现流程如下：

（1）如果a、b相等，则a就是最大公约数

（2）如果a、b都是偶数，则用更相减损法，将a、b都除以2，继续进行第（1）步

（3）如果a是偶数，b是奇数，则用更相减损法，将a除以2，继续进行第（1）步

（4）如果a是奇数，b是偶数，则用更相减损法，将b除以2，继续进行第（1）步

（5）如果a、b都是奇数，则用更相减损法，将a、b之间的差值c计算出来，继续进行第（1）步

代码实现：

public static int gcd(int a, int b) {

if (a == b)

return a;

else if ((a & 1) == 0 && (b & 1) == 0) {

return gcd(a >> 1, b >> 1) << 1;

} else if ((a & 1) == 0 && (b & 1) != 0) {

return gcd(a >> 1, b);

} else if ((a & 1) != 0 && (b & 1) == 0) {

return gcd(a, b >> 1);

} else {

int c = Math.abs(a - b);

return gcd(Math.min(a, b), c);

}

三个

上一篇: idea打包java可执行jar包

下一篇: 我的Java自我评价

()

相似文章