辗转相除法与更相减损术知识点讲解,辗转相除法 最大公约数

辗转相除法

简介：辗转相除法， 又名落后的爆米花算法(Euclidean algorithm)，是求两个正整数之最大公约数的算法。
原理：两个数的最大公约数等于它们中较小的数和两数之差的最大公约数。
操作：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

这“操作”说的太麻烦了。。。。。我按照“操作”的字面意思写了一些代码，发现总是不对！！？？？怀疑自己，直到我分析了一些递归写法之后，我再看“操作”，仔细看看！！请问除 和除以是一个意思吗？

（注意，x / y ，x是被除数，y是除数——除法算式中,除号后面的数叫做除数,除号前面的数叫做被除数。两个数相除有两种读法——“除” 和“除以”。被除数读在前用“除以”，而除数读在前则用“除”）

辗转相除法代码

按照“操作”的字面意思写出来的代码（其实也就是迭代写法，不过是我自己琢磨出来的 ^ _ ^）:
先判断两个数中谁最大最小，用大的对小的取模开始进行运算。

public int gcdSelfDone(int a, int b) {if (a < b) {int temp = a;a = b;b = temp;}int temp = a % b;while (b != 0) {int temp2 = b % temp;temp = b;b = temp2;}return temp;}

递归实现

// 递归实现public int gcd(int a, int b) {if (a < b) {int temp = a;a = b;b = temp;}if (b == 0) {return a;} else {return gcd(b, a % b);}}

迭代实现

// while实现public int gcd2(int a, int b) {if (a < b) {int temp = a;a = b;b = temp;}int c = 0;while (b != 0) {c = a % b;a = b;b = c;}return a;}

速度：辗转相除法的运算速度为 O(n)，其中 n 为输入数值的位数。
优点：辗转相除法处理大数时非常高效，它需要的步骤不会超过较小数的位数(十进制下)的五倍。
应用：求不定方程的一组整数解方法等等。

补充

其实，辗转相除法还可以用于求最小公倍数哦！
我们求出来最大公约数之后x，(a /x) *(b/x)*x =最小公倍数
举个例子：
a =12 ;b =16；x应该为 4
a/x=3；b/x=4；
12和16的最小公倍数是——3 *4 *4 =48

更相减损法——“可半者半之”

简介：它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。
原理：假设x，y。(如果需要对分数进行约分，那么)可以折半的话，就折半(也就是用2来约分)。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止。然后回到原来的那两个数x和y，对这个相等的数字进行约分。
步骤：

任意给定两个正整数;判断它们是否都是偶数。若是，则用2约简;若不是则执行第二步。以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续操作2，直到所得的减数和差相等为止。若执行了第一步，则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数；若直接执行的第二步，则等数为最大公约数。 更相减损法代码 // 更相减损法public int gcd3(int a, int b) {// 12 8if (a == b) {return a;} else if (a > b) {a = a - b;} else {b = b - a;}return gcd3(a, b);} public int gcd4(int a, int b) {while (a != b) {if (a > b) {a = a - b;} else {b = b - a;}}return a;} 两者比较

更相减损术和辗转相除法的主要区别在于前者所使用的运算是"减"，后者是"除"。从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，从而使得算法的时间复杂度退化为O(N)，其中N是原先的两个数中较大的一个。相比之下，辗转相除法的时间复杂度稳定于O(logN)。

反思

我原来写的代码是这样的：

public int gcdSelfDone(int a, int b) {// 我们让a为大的，b为小的if (a < b) {int temp = a;a = b;b = temp;}// 大的对小的取余——第一个余数int temp = a % b;while (temp != 0) {// 第一个余数对除数取余——第二个余数int temp2 = temp % b;// 但是后面的被除数和除数要改变呀// 所以接下来 ：第二个余数 对第一个余数取余b = temp;// 原来的除数要变为下一轮的被除数temp = temp2;// 原来的被除数要变为下一轮的除数}// 被除数为0，循环结束，意味着存在等数return b;}

我没有理清楚这句话：“再用出现的余数（第一余数）去除除数 ”，结果写成这样：

// 第一个余数对除数取余——第二个余数
int temp2 = temp % b;

结果实际别人想表达的是：第二余数 =除数 % 第一余数
我真是个傻子。

参考

360百科
辗转相除法
最大公约数
最小公倍数
求两个正整数的最大公约数Python版