怎么用Java求最大公約數

這篇文章主要介紹“怎么用Java求最大公約數”，在日常操作中，相信很多人在怎么用Java求最大公約數問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”怎么用Java求最大公約數”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

/**

 * @date 2019/7/25 11:33
 * description:求最大公約數
 */
public class CommonDivisor {

    /**
     * 第一版本
     * 最簡單的想法，找較小數的一半，從大到小，開始試著找出能夠同時兩個數整除最大數
     * 這種方法暴力枚舉，會循環很多次
     *
     * @param a
     * @param b
     * @return
     */
    public static int getGreatestCommonDivisor(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        for (int i = small / 2; i > 1; i--) {
            if (small % i == 0 && big % i == 0) {
                return i;
            }
        }
        return 1;
    }


    /**
     * 第二版本
     * 歐幾里得算法：輾轉相除法求最大公約數
     * 兩個正數a和b(a>b),它們的最大公約數等于a和b相除的余數c和b的最大公約數  我們可以使用遞歸的方法簡化問題
     * eg 10和25 的最大公約數等于 余數5和10的最大公約數 5
     * 缺點 ： 兩個數較大時 a%b的轉換效率低
     *
     * @param a
     * @param b
     * @return
     */
    public static int getGreatestCommonDivisor2(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        return getGreatestCommonDivisor2(big % small, small);

    }


    /**
     * 第三版本
     * 九章算術
     * 更相減損術 :兩個正整數a,b(a>b),他們的最大公約數等于a-b的差值c和較小數b的最大公約數
     * 缺點：兩數相差很大時，遞歸次數太大
     *
     * @param a
     * @param b
     * @return
     */
    public static int getGreatestCommonDivisor3(int a, int b) {
        if (a == b) {
            return a;
        }
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        return getGreatestCommonDivisor3(big - small, small);

    }


    /**
     * 第四版本
     * 九章算術 更相減損術和輾轉相除法結合起來， 更相減損術上使用位移操作
     * 更相減損術 :兩個正整數a,b(a>b),他們的最大公約數等于a-b的差值c和較小數b的最大公約數
     * 缺點：兩數相差很大時，遞歸次數太大
     *
     * @param a
     * @param b
     * @return
     */
    public static int getGreatestCommonDivisor4(int a, int b) {

        if (a == b) {
            return a;
        }
        if ((a & 1) == 0 && (b & 1) == 0) {
            return getGreatestCommonDivisor4(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {
            return getGreatestCommonDivisor4(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {
            return getGreatestCommonDivisor4(a, b >> 1);
        } else {
            int big = a > b ? a : b;
            int small = a < b ? a : b;
            return getGreatestCommonDivisor4(big - small, small);
        }
    }

    public static void main(String[] args) {
        System.out.println(getGreatestCommonDivisor4(25, 5));
        System.out.println(getGreatestCommonDivisor4(100, 80));
        System.out.println(getGreatestCommonDivisor4(27, 14));
    }


}

到此，關于“怎么用Java求最大公約數”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！