Stein算法——Java实现

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

代码：

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输出即可。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！