前言
Hello峭跳！小伙伴！
非常感謝您閱讀海轟的文章缺前，倘若文中有錯誤的地方蛀醉，歡迎您指出～
?
自我介紹 ?(?ˊ?ˋ)?
昵稱：海轟
標(biāo)簽：程序猿｜C++選手｜學(xué)生
簡介：因C語言結(jié)識編程，隨后轉(zhuǎn)入計(jì)算機(jī)專業(yè)衅码，有幸拿過國獎拯刁、省獎等，已保研逝段。目前正在學(xué)習(xí)C++/Linux（真的真的太難了～）
學(xué)習(xí)經(jīng)驗(yàn)：扎實(shí)基礎(chǔ) + 多做筆記 + 多敲代碼 + 多思考 + 學(xué)好英語垛玻！
?
<font color="red" font-wight="800">【動畫消消樂】</font> 平時學(xué)習(xí)生活比較枯燥，無意之間對一些網(wǎng)頁奶躯、應(yīng)用程序的過渡/加載動畫產(chǎn)生了濃厚的興趣帚桩，想知道具體是如何實(shí)現(xiàn)的？ 便在空閑的時候?qū)W習(xí)下如何使用css實(shí)現(xiàn)一些簡單的動畫效果巫糙，文章僅供作為自己的學(xué)習(xí)筆記朗儒，記錄學(xué)習(xí)生活，爭取理解動畫的原理参淹，多多“消滅”動畫醉锄！
概念
最大公約數(shù)：也稱最大公因數(shù)、最大公因子浙值，指兩個或多個整數(shù)共有約數(shù)中最大的一個
最小公倍數(shù)：兩個或多個整數(shù)公有的倍數(shù)叫做它們的公倍數(shù)恳不，其中除0以外最小的一個公倍數(shù)就叫做這幾個整數(shù)的最小公倍數(shù)。
求法
注：以求兩個正整數(shù)的最大公因數(shù)為例
方法一【枚舉法】
思路：
- 找到a开呐、b中的較小值
- 從該值開始烟勋，判斷該數(shù)能否同時被a规求、b整除
- 若可以被整除 返回該值
- 若不可以 則遞減1
#include <iostream>
using namespace std;
// 求最大公約數(shù)
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;
}
方法二【輾轉(zhuǎn)相除法】
輾轉(zhuǎn)相除法是利用以下性質(zhì)來確定兩個正整數(shù) a 和 b 的最大公因子的：
- 若 r 是 a ÷ b 的余數(shù)，且r不為0卵惦， 則gcd(a,b) = gcd(b,r)
注：gcd表示最大公因數(shù)阻肿，gcd(a,b)表示a、b兩數(shù)的最大公因數(shù)
程序設(shè)計(jì)思路是：
- 令r為a/b所得余數(shù)（0<=r）
- 若 r= 0沮尿，算法結(jié)束丛塌；b 即為答案。
- 互換：置 a←b畜疾，b←r赴邻，并返回第一步。
#include <iostream>
using namespace std;
// 求最大公約數(shù)
int gcd(int a, int b)
{
int r;
// 當(dāng)a不能被b整除完全時
// 令a=b b=a%b
// 重復(fù)循壞 直到a%b==0
// 返回b b就是最大公因數(shù)
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;
}
同樣的思路啡捶，使用遞歸實(shí)現(xiàn)：
核心：
- 若 r 是 a ÷ b 的余數(shù)姥敛，且r不為0， 則gcd(a,b) = gcd(b,r)
#include <iostream>
using namespace std;
// 求最大公約數(shù)
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;
}
方法三【更相減損法】
程序設(shè)計(jì)步驟：
- 第一步：任意給定兩個正整數(shù)瞎暑；判斷它們是否都是偶數(shù)彤敛。若是，則用2約簡金顿；若不是則執(zhí)行第二步臊泌。
- 第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較揍拆，并以大數(shù)減小數(shù)渠概。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止嫂拴。
- 則第一步中約掉的若干個2的積與第二步中等數(shù)的乘積就是所求的最大公約數(shù)播揪。
#include <iostream>
#include <math.h>
using namespace std;
// 求最大公約數(shù)
int gcd(int a, int b)
{
// 判斷兩數(shù)是否都是偶數(shù)
// 若都是 則都除以2
// 直到其中一個數(shù)為奇數(shù)
int count = 0;// 記錄2的個數(shù)
while (a % 2 == 0 && b % 2 == 0)
{
a /= 2;
b /= 2;
++count;
}
// 當(dāng)a!=b時
// 用a、b中的較大數(shù)減去較小數(shù)字
// 一直循環(huán) 直到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;
// 求最大公約數(shù)
int gcd(int a, int b)
{
// 在這里遞歸時 沒有對a b進(jìn)行同時約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表示最大公因數(shù)
算法步驟：
1筒狠、設(shè)置An=|A|猪狈、Bn=|B|、Cn=1和n=1
2辩恼、如果An=Bn,那么An(或Bn)*Cn是最大公約數(shù),算法結(jié)束
3雇庙、如果An=0，Bn是最大公約數(shù)灶伊，算法結(jié)束
4疆前、如果Bn=0，An是最大公約數(shù)聘萨，
算法結(jié)束
5竹椒、如果An和Bn都是偶數(shù)，則An+1=An/2米辐，Bn+1=Bn/2胸完，Cn+1=Cn*2(注意书释，乘2只要把整數(shù)左移一位即
可，除2只要把整數(shù)右移一位即可)
6赊窥、如果An是偶數(shù)爆惧，Bn不是偶數(shù)，則An+1=An/2锨能，Bn+1=Bn检激，Cn+1=Cn(很顯然啦，2不是奇數(shù)的約數(shù))
7腹侣、如果Bn是偶數(shù)，An不是偶數(shù)齿穗，則Bn+1=Bn/2傲隶，An+1=An，Cn+1=Cn(很顯然啦窃页，2不是奇數(shù)的約數(shù))
8跺株、如果An和Bn都不是偶數(shù)，則An+1=|An-Bn|/2（或An+1=|An-Bn|也行）脖卖，Bn+1=min(An,Bn)乒省，Cn+1=Cn
9、n=n+1畦木，轉(zhuǎn)2
非遞歸：
#include <iostream>
#include <math.h>
using namespace std;
// 求最大公約數(shù)
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是奇數(shù) 與a%2==1得到的效果一樣
// 都是判斷a是奇數(shù)還是偶數(shù)
if (a & 1)
{
if (b & 1)
{
//a,b都是奇數(shù)時
// 提前存儲a 因?yàn)楹竺鎍變了
int temp = a;
a = abs(a - b) >> 1;
b = min(temp, b);
}
else
{
//a是奇數(shù) b是偶數(shù)
b >>= 1;
}
}
else
{
if (b & 1)
{
//a是偶數(shù) b是奇數(shù)
a >>= 1;
}
else
{
//a袖扛、b都是偶數(shù)
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;
}
遞歸實(shí)現(xiàn)：
#include <iostream>
#include <math.h>
using namespace std;
// 求最大公約數(shù)
int gcd(int a, int b)
{
// 如果A=0 B是最大公因數(shù) 返回B
if (a == 0)
return b;
// 如果B=0 A是最大公因數(shù) 返回A
if (b == 0)
return a;
// 如果A、B都是偶數(shù)
// 則分別除以因子2
// 直到不滿足二者同時為偶數(shù)
if (a % 2 == 0 && b % 2 == 0)
return 2 * gcd(a >> 1, b >> 1);
// 若a是偶數(shù) b不是偶數(shù)
// 說明因子2不在公共因子中 可以直接除去2
else if (a % 2 == 0)
return gcd(a >> 1, b);
// 若b是偶數(shù) a不是偶數(shù)
// 說明因子2不在公共因子中 可以直接除去2
else if (b % 2 == 0)
return gcd(a, b >> 1);
// 若 a十籍、b都是奇數(shù)時
// 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;
}
最小公倍數(shù)求法就比較簡單了，求出最大公因數(shù)后勾栗，之間用a*b/gcd(a,b)即可
結(jié)語
文章僅作為學(xué)習(xí)筆記惨篱，記錄從0到1的一個過程
希望對您有所幫助，如有錯誤歡迎小伙伴指正～
