求最大公約數有三種方式
- 暴力窮舉法
- 輾轉相除法
- 更相減損術
暴力窮舉法
暴力窮舉法的思路：從兩個數之間找最小的數，然后用這個數往下減侧蘸，若是兩個數都能夠被整除坑鱼，那個數就是最大公約數
int maxNumber(int m, int n) {
int temp = m > n ? n : m;
for (int i = temp; i > 0; i--) {
if (m % i == 0 && n % i == 0) {
return i;
}
}
return 0;
}
這種算法的效率太慢耳鸯。要是筆試寫這個分分鐘回去等通知樱衷。
輾轉相除法
輾轉相除法有兩種方式，維基百科和百度百科對于輾轉相除法的定義有些出入
百度百科：最大公約數等于a除以b的余數c和b之間的最大公約數店溢。
int maxNumber(int m, int n) {
int temp;
if (n > m) {
temp = n;
n = m;
m = temp;
}
if (m % n == 0) {
return n;
}
return maxNumber(n, m % n);
}
維基百科：最大公約數等于其中較小的數和兩數的差的最大公約數叁熔。
int maxNumber(int m, int n) {
int temp;
if (n > m) {
temp = n;
n = m;
m = temp;
}
if (m % n == 0) {
return n;
}
return maxNumber(m - n, n);
}
更相減損術
更相減損術出自《九章算術》
原文描述：可半者半之，不可半者床牧，副置分母荣回、子之數，以少減多戈咳，更相減損心软，求其等也壕吹。以等數約之。
白話文譯文：如果需要對分數進行約分删铃，那么）可以折半的話耳贬，就折半（也就是用2來約分）。如果不可以折半的話猎唁，那么就比較分母和分子的大小咒劲，用大數減去小數，互相減來減去诫隅，一直到減數與差相等為止腐魂，用這個相等的數字來約分。
- 任意給定兩個正整數阎肝；判斷它們是否都是偶數。若是肮街，則用2約簡风题；若不是則執(zhí)行第二步。
- 以較大的數減較小的數嫉父，接著把所得的差與較小的數比較沛硅，并以大數減小數。繼續(xù)這個操作绕辖，直到所得的減數和差相等為止摇肌。
- 則第一步中約掉的若干個2與第二步中等數的乘積就是所求的最大公約數。
int maxNumber(int m, int n) {
if (m == n) {
return n;
}
if (n > m) {
return maxNumber(n,m);
}else {
// 同為偶數
if((m&1) == 0 && (n&1)==0){
return maxNumber(m >> 1, n >> 1) << 1;
}else if((m&1) == 0 && (n&1) !=0){
return maxNumber(m >>1,n);
}else if((m&1) != 0 && (n&1) ==0){
return maxNumber(m,n>>1);
}else {
return maxNumber(n,m - n);
}
}
}
