关于java:看不懂辗转相除法求最小公约数以身相许那种哦

35次阅读

共计 1504 个字符，预计需要花费 4 分钟才能阅读完成。

给你打个比喻吧：你英雄救美了，美女想要回报你，你想要 1000 块感谢费，然而美女却想要以身相许????，懂了吧，同样都是回报，只是用了不一样的形式，辗转相除法也是这样，你两个数的最大公约数不容易求，我就用另外两个简略的数来解决。

废话不多说，看定理。

辗转相除 能够求最大公约数，顾名思义，重复的除，最终失去两数的最大公约数。
首先咱们来剖析下定理：

定理：两个整数 的最大公约数 等于其中较小的那个数和两数 相除余数 的最大公约数。最大公约数（Greatest Common Divisor）缩写为 GCD。
gcd(a,b) = gcd(b,a mod b) (无妨设 a >b 且 r =a mod b ,r 不为 0)

文字不好了解，举个实例：
134 / 18 = 7 … 8
18 / 8 = 2 … 2
8 / 2 = 4 … 0

看清了吧，是不是和定理截然不同，所以咱们要找最大公约数，而 134 /18 的和 8 / 2 的最大公约数相等，所以咱们只需要求出 8 / 2 的最大公约数，是不是就是结尾说的换了两个数再求，而咱们要晓得，因为 两数相除，余数为 0，其除数必然为最大公约数，所以这里的 2 也就是咱们要找的 138 / 18 的最大公约数。至于证实，百度搜寻，都有。次要证实思路就是，有 a / b 余 r 一式，先假如 y 为 a，b 的公约数，再证实 b,r 的公约数也为 y。

通过定理咱们晓得，要计算两数最大公约数，咱们只须要始终递归就行了，直到余数为 0，最大公约数就是 较小的那个数（除数）。递归置信大家都理解过吧，必然有一进口，保障程序进行或返回，那么这里的进口条件就是下面例子的 2，即 余数为 0 。程序就是先找出输出参数谁打谁小，再判断余数是否为 0（进口），再递归。代码用 java 写的，其实没啥差异，也没用 api，思路都一样，格局不一样罢了。

所以咱们开始写代码了：

private static void method4(int m, int n, int ji) {
        // 相比拟两个数，把较小的那个数赋值给 smallNum;
        int smallNum = (m > n ? n:m);
        int bigNum = (m > n ? m:n);
        if (n < 0 || m < 0){System.out.println("输出有错，完结了");
        }else{
            // 余数为 0，smallNum 就是那个最大公约数
            if (bigNum % smallNum == 0){System.out.println("最小公倍数"+(ji / smallNum)+"最大公约数"+smallNum);
                // 我写了几种办法，不便调用，所以返回的空
                return;
            }
            method4(smallNum,bigNum % smallNum, ji);
        }
    }

通过定理咱们晓得较小数为除数吧，所以咱们间接每次递归时，就把较小那个值找进去。而后把它变成除数，不就行了吗。

什么你还没学递归，不要紧，我还有一种办法，就是while 循环，while 循环就不必判断谁大谁小了，因为小数 % 大数 = 小数自身，代码搞起来：

private static void method2(int m ,int n,int ji) {while(true){if ((m = m % n) == 0){System.out.println("最大公约数"+n);
                System.out.println("最小公倍数"+(ji / n));
                System.exit(0);
            }
            if ((n = n % m) == 0) {System.out.println("最大公约数"+m);
                System.out.println("最小公倍数"+(ji / m));
                System.exit(0);
            }
        }
    }

其实我还有一种枚举的算法，就不写了。当然求解最大公倍数，辗转相除还不是最优，还有更优，大家能够搜搜看。如果有工夫，我在补充其余的算法。

正文完