/***********************************************************************
目的：求输入两个数的最大公约数
分析：确定较大值或较小值，并把较小值拷贝。
最大公约数不会超过两个数的较小值，所以从较小值开始往下找，直到能同时被两个数整除
24 18
24 17
…
25 6
平台：Visual studio 2017 && windows
*************************************************************************/
📝 实现代码1：
#include<stdio.h> #pragma warning(disable:4996) int main() { int m = 0; int n = 0; scanf("%d%d", &m, &n); //存储最大公约数 int gcd = 0; //确定最大值为m if (m < n) { int temp = m; m = n; n = temp; } //假设最大公约数是n gcd = n; while (1) { if (m % gcd == 0 && n % gcd == 0) { printf("%d\n", gcd); break; } gcd--; } }
/***********************************************************************
目的：优化代码1：
分析：可以不用确定较大值或较小值，但是必须得拷贝一份n或m
18 24
18 23
…
18 6
平台：Visual studio 2017 && windows
*************************************************************************/
📝 优化代码1：
#include<stdio.h> #pragma warning(disable:4996) int main() { int m = 0; int n = 0; scanf("%d%d", &m, &n); int gcd = 0; //假设最大公约数是m gcd = m; while (1) { if (m % gcd == 0 && n % gcd == 0) { printf("%d\n", gcd); break; } gcd--; } }
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
/***********************************************************************
目的：欧几里德算法 求最大公约数
算法简介：欧几里得算法又称辗转相除法，古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。扩展欧几里得算法可用于RSA加密等领域。
算法原理：通俗来讲就是以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数
24 18
24 % 18 = 1 … 6
18 % 6 = 3 … 0
平台：Visual studio 2017 && windows
*************************************************************************/
📝 实现代码2：：
#include<stdio.h> #pragma warning(disable:4996) int main() { int m = 0; int n = 0; scanf("%d%d", &m, &n); while(m % n) { //交换被除数和除数 int temp = m % n; m = n; n = temp; } printf("%d\n", n); return 0; }
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
/***********************************************************************
目的：更相减损术 求最大公约数
算法简介：《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。
算法原理：
▶ 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
▶ 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
▶ 则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。
平台：Visual studio 2017 && windows
*************************************************************************/
📝 实现代码2：
#include<stdio.h> #pragma warning(disable:4996) int main() { int m = 0; int n = 0; scanf("%d%d", &m, &n); int flag = 0;//为了区分这两个数有没有约简2 int count = 0;//记录约简了几次2 int temp = 0; while(1) { //两个数相同 if(m == n) { flag = -1; break; } //全为偶 if(m % 2 == 0 && n % 2 == 0) { flag = 1; count++; m /= 2; n /= 2; } //不全为偶 else { //大减小 if(m > n) { temp = m - n; } else { temp = n - m; } //比较减数和差 if(n > temp) { m = n; n = temp; } else if(n < temp) { m = temp; } else { //减数和差相等 break; } } } //约简2 if(1 == flag) { printf("%d\n", 2 * count * n); } //两数相等 else if(-1 == flag) { printf("%d\n", m); } else { printf("%d\n", n); } return 0; }
/***********************************************************************
目的：优化 更相减损术 求最大公约数
算法原理：可将上面的步骤理解为：
▶ 若m > n，则m = m - n
▶ 若m < n，则 n = n - m
▶ 若m = n，则最大公约数为m
平台：Visual studio 2017 && windows
*************************************************************************/
📝 优化代码2：
#include<stdio.h> #pragma warning(disable:4996) int main() { int m = 0; int n = 0; scanf("%d%d", &m, &n); while (m != n) { if (m > n) m -= n; else n -= m; } printf("%d\n", m); return 0; }
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
比较：更相减损术和辗转相除法的主要区别在于前者所使用的运算是“减”，后者是“除”。从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，从而使得算法的时间复杂度退化为O(N)，其中N是原先的两个数中较大的一个。相比之下，辗转相除法的时间复杂度稳定于O(logN)。
这场来自中西方的磨擦就此打住
当然还有其它的一些算法
穷举法 ：一听就很暴力
Stein算法 ：针对欧几里德算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法
目的：求输入两个数的最小公倍数
算法原理：
▶ 利用求出最大公约数，用两个数的乘积除以最大公约数即可。
▶ 最小公倍数不会小于两个数的较大值，所以从较大值开始往上找
平台：Visual studio 2017 && windows
*************************************************************************/
📝 实现代码3：
#include<stdio.h> #pragma warning(disable:4996) int main() { int m = 0; int n = 0; scanf("%d%d", &m, &n); //拷贝一份m和n int tmp_m = m; int tmp_n = n; while (m != n) { if (m > n) m -= n; else n -= m; } printf("%d\n", tmp_m * tmp_n / m); return 0; }
📝 实现代码4：
#include<stdio.h> #pragma warning(disable:4996) int main() { int m = 0; int n = 0; scanf("%d%d", &m, &n); int temp = m; while(1) { if(temp % m == 0 && temp % n == 0) { printf("%d\n", temp); break; } temp++; } return 0; }
