火山日常啰嗦
今天參加騰訊筆試践美，做編程題時在最小公倍數(shù)、最大公約數(shù)這些這么簡單的知識點上卡殼了找岖，自信心受到強烈的打擊陨倡，下來后猛復(fù)習了這方面的相關(guān)編程知識。
有以下幾個關(guān)鍵點：
1许布、任意正整數(shù)的最大公約數(shù)兴革、最小公倍數(shù)都是它本身。
2、求兩個數(shù)的最大公約數(shù)（遞歸法杂曲、相減法庶艾、輾轉(zhuǎn)相除法）
3、求兩個數(shù)的最小公倍數(shù)擎勘，兩個數(shù)的最小公倍數(shù)與它們的最大公約數(shù)之間存在如下關(guān)系：
某兩個數(shù)a,b的最小公倍數(shù)=(a*b)/a與b的最大公約數(shù)
4咱揍、求多個數(shù)的最大公約數(shù)可以拆解成求兩個數(shù)的最大公約數(shù)的過程
5、求多個數(shù)的最小公倍數(shù)可以拆解成求兩個數(shù)的最小公倍數(shù)的過程
詳細解析都在以下代碼中：
public class Main {
// 遞歸法
public static int MaxCommonNum(int left , int right){
/**
* 我始終讓left>right棚饵，這不是硬性要求哈煤裙，只是我個人的編程習慣
*/
if(left<right){
int temp = left;
left = right;
right = temp;
}
if((left%2!=0 || right%2!=0)&&(left%right!=0)) return 1;
else if((left%2!=0 || right%2!=0)&&(left%right==0)) return right;
else return 2*MaxCommonNum(left/2,right/2);
}
// 相減法
/**
* @param left
* @param right
* @return
* 1 若a>b,則a-=b
* 2 若a<b,則b-=a
* 3 若a==b,則a(或者b)就是所求的最大公約數(shù)
* 4 若a!=b，則回去執(zhí)行1噪漾、2步驟
*/
public static int MaxCommonNum1(int left , int right){
if(left==right) return left;
if(left>right) left-=right;
else right-=left;
return MaxCommonNum1(left,right);
}
// 輾轉(zhuǎn)相除法
/**
* @param left
* @param right
* @return
* 若要用left對right取模硼砰，那么要保證left>=right（反之亦然）
* 1 若left%right==0,則right就是所求的最大公約數(shù)
* 2 若left%right!=0,則將right的值賦給left，將left%riht的值賦給right怪与，即left=right,right=left%right,然后再取模，判斷余數(shù)是否為0
* 3 重復(fù)這些步驟缅疟，直到left%right==0,則right就是所求的最大公約數(shù)
*
* */
public static int MaxCommonNum2(int left , int right){
if(left<right){
int temp = left;
left = right;
right = temp;
}
if(left%right==0) return right;
else return MaxCommonNum2(right,left%right);
}
// 求多個數(shù)的最大公約數(shù)分别，借助求兩個數(shù)的最大公約數(shù)的方法來求
/**
*
* @param arr
* @return
* 求多個數(shù)的最大公約數(shù)，那么可以傳入一個數(shù)組int arr[]
* 1 取arr[0]賦給temp(某個正整數(shù)的最大公約數(shù)是它本身),然后通過求兩個數(shù)的最大公約數(shù)的方法先求出temp與arr[1]的最大公約數(shù)存淫，將結(jié)果賦給temp耘斩，則temp表示arr[0]與arr[1]的最大公約數(shù)
* 2 然后再求temp與arr[2]的最大公約數(shù)，將結(jié)果賦給temp
* 3 循環(huán)直到temp與剩余的每個數(shù)都求過最大公約數(shù)了桅咆，那么最后所求的那個就是這組數(shù)的最大公約數(shù)了
*
*/
public static int MaxCommonNumFromMultiNumbers(int arr[]){
int temp = arr[0];
for(int i=1;i<arr.length;i++){
temp = MaxCommonNum(temp,arr[i]);
}
return temp;
}
// 求兩個數(shù)的最小公倍數(shù)
/**
*
* @param left,right
* 兩個數(shù)a括授，b的最小公倍數(shù)=(a*b)/a與b的最大公約數(shù)
*
*/
public static int MinCommonNum(int left,int right){
return left*right/MaxCommonNum(left,right);
}
// 求多個數(shù)的最小公倍數(shù)
/**
*
* @param arr
* @return
* 求多個數(shù)的最小公倍數(shù)跟求多個數(shù)的最大公約數(shù)的方法一樣
*/
public static int MinCommonNumFromNumbers(int arr[]){
int temp = arr[0];
for(int i=1;i<arr.length;i++){
temp = MinCommonNum(temp,arr[i]);
}
return temp;
}
public static void main(String[] args) {
// 求兩個數(shù)的最大公約數(shù)，有三種方法：
// 1岩饼、遞歸法
// 2荚虚、相減法
// 3、輾轉(zhuǎn)相除法
// 求多個數(shù)的最大公約數(shù)籍茧，借助求兩個數(shù)的最大公約數(shù)的方法來求
// 遞歸法
System.out.println(MaxCommonNum(3,5));
System.out.println(MaxCommonNum(12,8));
// 相減法
System.out.println(MaxCommonNum1(3,5));
System.out.println(MaxCommonNum1(12,8));
// 輾轉(zhuǎn)相除法
System.out.println(MaxCommonNum2(3,5));
System.out.println(MaxCommonNum2(12,8));
// 求多個數(shù)的最大公約數(shù)
int[] arr = {1,2,3,4,5,6};
System.out.println(MaxCommonNumFromMultiNumbers(arr));
// 求兩個數(shù)的最小公倍數(shù)
System.out.println(MinCommonNum(3,5));
System.out.println(MinCommonNum(12,8));
// 求多個數(shù)的最小公倍數(shù)
int[] array = {4,5,6};
int[] array1 = {1,2,3,4,5,6};
System.out.println(MinCommonNumFromNumbers(array));
System.out.println(MinCommonNumFromNumbers(array1));
}
}
有誤之處望請指出版述，望共同進步。感謝寞冯！
