更相减损术是一种求两个正整数最大公约数的算法,其基本步骤如下:
1. 如果两个整数都是偶数,则将它们同时除以2,直到它们不再都是偶数为止。
2. 如果两个整数不都是偶数,则用较大的数减去较小的数,得到差值。
3. 将较小的数和差值进行比较,用大数减小数,继续这个过程,直到差值等于较小的数为止。
4. 在整个过程中,记录下除以2的次数。
5. 最后,将约掉的2的次数与最后得到的差值相乘,即为原来两个整数的最大公约数。
下面是使用Java实现更相减损术的代码示例:
```java
import java.util.Scanner;
public class SubSubAlgorithm {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入两个数字:");
int a = sc.nextInt();
int b = sc.nextInt();
int gcd = subsub(a, b);
System.out.println("最大公约数 = " + gcd);
}
public static int subsub(int a, int b) {
int i = 0;
int c = 0;
// 如果两个数都是偶数,则除以2,并记录被2除的次数
while (a % 2 == 0 && b % 2 == 0) {
a = a / 2;
b = b / 2;
i++;
}
// 主体,大数减小数,循环,直到两数相等为止
while (a != b) {
if (a > b) {
a -= b;
} else {
b -= a;
}
}
// 如果i不为0,则c为b乘以i乘以2,否则c为b
if (i != 0) {
c = b * i * 2;
} else {
c = b;
}
return c;
}
}
```
代码解释:
输入部分:
通过`Scanner`类从控制台读取两个整数`a`和`b`。
处理偶数:
使用`while`循环检查`a`和`b`是否都是偶数,如果是,则将它们同时除以2,并记录被2除的次数`i`。
主体循环:
使用另一个`while`循环,只要`a`不等于`b`,就继续执行大数减小数的操作,直到两数相等为止。
计算最大公约数:
如果`i`不为0,则最大公约数`c`为`b`乘以`i`乘以2;否则,最大公约数`c`为`b`。
输出结果:
打印出最大公约数。
这个程序可以正确地实现更相减损术,并求出两个整数的最大公约数。