求最大公约数有三种方式
1.暴力穷举法
2.辗转相除法
3.更相减损术
暴力穷举法
暴力穷举法的思路:从两个数之间找最小的数,然后用这个数往下减,若是两个数都能够被整除,那个数就是最大公约数
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来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分。
1.任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
2.以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
3.则第一步中约掉的若干个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); } } } |