Stein算法——Java实现

Stein算法，听起来很陌生，甚至没有怎么见过的算法，但是在求最大公约数中发挥了较大的作用。虽然是递归实现，但是相较于辗转相除法和更相减损术有着不可比拟的优势

代码：

package homework3.GreatestCommonDivisor;

import java.util.Scanner;

public class Stein {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入两个数：");
        int a = sc.nextInt();
        int b = sc.nextInt();
        b = stein(a, b);        //这里需要给b赋值来输出最大公约数
        System.out.println(b);
    }

    public static int stein(int a, int b) {
        int c;
        if (a < b) {
            c = a;
            a = b;
            b = c;
        }        //判断输入的数字的大小，让a始终大于b，一下为算法主体
        if (b == 0)
            return a;
        if (a % 2 == 0 && b % 2 == 0)
            return 2 * stein(a / 2, b / 2);
        if (a % 2 == 0)
            return stein(a / 2, b);
        if (b % 2 == 0)
            return stein(a, b / 2);
        return stein((a + b) / 2, (a - b) / 2);
    }
}

这次的算法存在一下原因导致出错，首先是我将最大公约数的输出放在了倒数第3行和倒数第4行之间。虽然这是在算法内部的数据，但仍有可能得出错误的结果，经过调试，我一度以为是算法的问题，但是没有考虑到最后一个return所返回的值。

将方法Stein所得到的结果赋值给b之后，将b输出即可。