前言
Hello！小伙伴！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
自我介绍 ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，有幸拿过国奖、省奖等，已保研。目前正在学习C++/Linux（真的真的太难了～）
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
<font color="red" font-wight="800">【动画消消乐】</font> 平时学习生活比较枯燥，无意之间对一些网页、应用程序的过渡/加载动画产生了浓厚的兴趣，想知道具体是如何实现的？ 便在空闲的时候学习下如何使用css实现一些简单的动画效果，文章仅供作为自己的学习笔记，记录学习生活，争取理解动画的原理，多多“消灭”动画！
概念
最大公约数：也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个
最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。
求法
注：以求两个正整数的最大公因数为例
方法一【枚举法】
思路：
- 找到a、b中的较小值
- 从该值开始，判断该数能否同时被a、b整除
- 若可以被整除 返回该值
- 若不可以 则递减1
#include <iostream>
using namespace std;
// 求最大公约数
int gcd(int a, int b)
{
int temp = a > b ? b : a;
while (temp)
{
if (a % temp == 0 && b % temp == 0)
{
break;
}
--temp;
}
return temp;
}
int main()
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
方法二【辗转相除法】
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
- 若 r 是 a ÷ b 的余数，且r不为0， 则gcd(a,b) = gcd(b,r)
注：gcd表示最大公因数，gcd(a,b)表示a、b两数的最大公因数
程序设计思路是：
- 令r为a/b所得余数（0<=r）
- 若 r= 0，算法结束；b 即为答案。
- 互换：置 a←b，b←r，并返回第一步。
#include <iostream>
using namespace std;
// 求最大公约数
int gcd(int a, int b)
{
int r;
// 当a不能被b整除完全时
// 令a=b b=a%b
// 重复循坏 直到a%b==0
// 返回b b就是最大公因数
while (a % b != 0)
{
r = a % b;
a = b;
b = r;
}
return b;
}
int main()
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
同样的思路，使用递归实现：
核心：
- 若 r 是 a ÷ b 的余数，且r不为0， 则gcd(a,b) = gcd(b,r)
#include <iostream>
using namespace std;
// 求最大公约数
int gcd(int a, int b)
{
if (a % b == 0)
{
return b;
}
else
{
return gcd(b, a % b);
}
}
int main()
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
方法三【更相减损法】
程序设计步骤：
- 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
- 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
- 则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
#include <iostream>
#include <math.h>
using namespace std;
// 求最大公约数
int gcd(int a, int b)
{
// 判断两数是否都是偶数
// 若都是 则都除以2
// 直到其中一个数为奇数
int count = 0;// 记录2的个数
while (a % 2 == 0 && b % 2 == 0)
{
a /= 2;
b /= 2;
++count;
}
// 当a!=b时
// 用a、b中的较大数减去较小数字
// 一直循环 直到a==b
while (a != b)
{
if (a > b)
{
a -= b;
}
else
{
b -= a;
}
}
// 注意需要乘以count个2
return a * pow(2, count);
}
int main()
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
递归：
#include <iostream>
#include <math.h>
using namespace std;
// 求最大公约数
int gcd(int a, int b)
{
// 在这里递归时 没有对a b进行同时约2的操作
if (a == b)
{
return a;
}
else if (a > b)
{
a -= b;
}
else
{
b -= a;
}
return gcd(a, b);
}
int main()
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
方法四【Stein算法】
用Cn表示最大公因数
算法步骤：
1、设置An=|A|、Bn=|B|、Cn=1和n=1
2、如果An=Bn,那么An(或Bn)*Cn是最大公约数,算法结束
3、如果An=0，Bn是最大公约数，算法结束
4、如果Bn=0，An是最大公约数，
算法结束
5、如果An和Bn都是偶数，则An+1=An/2，Bn+1=Bn/2，Cn+1=Cn*2(注意，乘2只要把整数左移一位即
可，除2只要把整数右移一位即可)
6、如果An是偶数，Bn不是偶数，则An+1=An/2，Bn+1=Bn，Cn+1=Cn(很显然啦，2不是奇数的约数)
7、如果Bn是偶数，An不是偶数，则Bn+1=Bn/2，An+1=An，Cn+1=Cn(很显然啦，2不是奇数的约数)
8、如果An和Bn都不是偶数，则An+1=|An-Bn|/2（或An+1=|An-Bn|也行），Bn+1=min(An,Bn)，Cn+1=Cn
9、n=n+1，转2
非递归：
#include <iostream>
#include <math.h>
using namespace std;
// 求最大公约数
int gcd(int a, int b)
{
int count = 0;
if (a == b)
return a;
if (a == 0)
return b;
if (b == 0)
return a;
while (a != b)
{
// a&1==1 说明a是奇数 与a%2==1得到的效果一样
// 都是判断a是奇数还是偶数
if (a & 1)
{
if (b & 1)
{
//a,b都是奇数时
// 提前存储a 因为后面a变了
int temp = a;
a = abs(a - b) >> 1;
b = min(temp, b);
}
else
{
//a是奇数 b是偶数
b >>= 1;
}
}
else
{
if (b & 1)
{
//a是偶数 b是奇数
a >>= 1;
}
else
{
//a、b都是偶数
a >>= 1;
b >>= 1;
++count;
}
}
}
return a << count;
}
int main()
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
递归实现：
#include <iostream>
#include <math.h>
using namespace std;
// 求最大公约数
int gcd(int a, int b)
{
// 如果A=0 B是最大公因数 返回B
if (a == 0)
return b;
// 如果B=0 A是最大公因数 返回A
if (b == 0)
return a;
// 如果A、B都是偶数
// 则分别除以因子2
// 直到不满足二者同时为偶数
if (a % 2 == 0 && b % 2 == 0)
return 2 * gcd(a >> 1, b >> 1);
// 若a是偶数 b不是偶数
// 说明因子2不在公共因子中 可以直接除去2
else if (a % 2 == 0)
return gcd(a >> 1, b);
// 若b是偶数 a不是偶数
// 说明因子2不在公共因子中 可以直接除去2
else if (b % 2 == 0)
return gcd(a, b >> 1);
// 若 a、b都是奇数时
// An+1 =|An -Bn|，Bn+1 =min(An,Bn)
else
// abs(a-b)/2也对
// return gcd(abs(a - b)/2, min(a, b));
return gcd(abs(a - b), min(a, b));
}
int main()
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
最小公倍数求法就比较简单了，求出最大公因数后，之间用a*b/gcd(a,b)即可
结语
文章仅作为学习笔记，记录从0到1的一个过程
希望对您有所帮助，如有错误欢迎小伙伴指正～
