简单学完HTML+CSS+JS,现在开始看算法(第四版)----欧几里得算法

时间:2021-11-02 08:35:25

欧几里得算法

package euclidean_algorithm;

import java.util.Scanner;

/**
 * @author ALazy_cat
 * 欧几里得算法的自然语言描述:
 *    计算两个非负整数x和y的最大公约数: 若y = 0,则最大公约数为x; 否则将remainder = x % y,x和y的
 * 最大公约数即为y和remainder的最大公约数 
 */
public class EuclideanAlgorithm {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("请输入两个整数: ");
        int x = 0, y = 0;
        x = in.nextInt();
        y = in.nextInt();
        System.out.println("x, y的最大公约数是: " + euclideanAlgorithm_01(x, y, 1));
        System.out.println("---------------------");
        System.out.println("x, y的最大公约数是: " + euclideanAlgorithm_02(x, y, 1));
    }

    //欧几里得算法的递归实现
    public static int euclideanAlgorithm_01(int x, int y, int count) {
        //当y = 0时,递归结束
        int remainder = 0;
        System.out.println("第" + count++ + "次递归: " + "x = " + x + " , " + "y = " + y);
        if (y == 0)
            return x;
        remainder = x % y;
        return euclideanAlgorithm_01(y, remainder, count);
    }

    //欧几里得算法的循环实现
    public static int euclideanAlgorithm_02(int x, int y, int count) {
        int remainder = 0;
        while (y != 0) {
            System.out.println("第" + count++ + "次循环: " + "x = " + x + " , " + "y = " + y);
            remainder = x % y;
            x = y;
            y = remainder;
        }
        System.out.println("第" + count++ + "次循环: " + "x = " + x + " , " + "y = " + y);
        return x;
    }
}