更相减损术怎么编程

时间:2025-01-25 15:55:52 网络游戏

更相减损术是一种求两个正整数最大公约数的算法,其基本步骤如下:

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`。

输出结果:

打印出最大公约数。

这个程序可以正确地实现更相减损术,并求出两个整数的最大公约数。