火山日常啰嗦
今天参加腾讯笔试，做编程题时在最小公倍数、最大公约数这些这么简单的知识点上卡壳了，自信心受到强烈的打击，下来后猛复习了这方面的相关编程知识。
有以下几个关键点：
1、任意正整数的最大公约数、最小公倍数都是它本身。
2、求两个数的最大公约数（递归法、相减法、辗转相除法）
3、求两个数的最小公倍数，两个数的最小公倍数与它们的最大公约数之间存在如下关系：
某两个数a,b的最小公倍数=(a*b)/a与b的最大公约数
4、求多个数的最大公约数可以拆解成求两个数的最大公约数的过程
5、求多个数的最小公倍数可以拆解成求两个数的最小公倍数的过程
详细解析都在以下代码中：
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)就是所求的最大公约数
* 4 若a!=b，则回去执行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);
}
// 辗转相除法
/**
* @param left
* @param right
* @return
* 若要用left对right取模，那么要保证left>=right（反之亦然）
* 1 若left%right==0,则right就是所求的最大公约数
* 2 若left%right!=0,则将right的值赋给left，将left%riht的值赋给right，即left=right,right=left%right,然后再取模，判断余数是否为0
* 3 重复这些步骤，直到left%right==0,则right就是所求的最大公约数
*
* */
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);
}
// 求多个数的最大公约数，借助求两个数的最大公约数的方法来求
/**
*
* @param arr
* @return
* 求多个数的最大公约数，那么可以传入一个数组int arr[]
* 1 取arr[0]赋给temp(某个正整数的最大公约数是它本身),然后通过求两个数的最大公约数的方法先求出temp与arr[1]的最大公约数，将结果赋给temp，则temp表示arr[0]与arr[1]的最大公约数
* 2 然后再求temp与arr[2]的最大公约数，将结果赋给temp
* 3 循环直到temp与剩余的每个数都求过最大公约数了，那么最后所求的那个就是这组数的最大公约数了
*
*/
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;
}
// 求两个数的最小公倍数
/**
*
* @param left,right
* 两个数a，b的最小公倍数=(a*b)/a与b的最大公约数
*
*/
public static int MinCommonNum(int left,int right){
return left*right/MaxCommonNum(left,right);
}
// 求多个数的最小公倍数
/**
*
* @param arr
* @return
* 求多个数的最小公倍数跟求多个数的最大公约数的方法一样
*/
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) {
// 求两个数的最大公约数，有三种方法：
// 1、递归法
// 2、相减法
// 3、辗转相除法
// 求多个数的最大公约数，借助求两个数的最大公约数的方法来求
// 递归法
System.out.println(MaxCommonNum(3,5));
System.out.println(MaxCommonNum(12,8));
// 相减法
System.out.println(MaxCommonNum1(3,5));
System.out.println(MaxCommonNum1(12,8));
// 辗转相除法
System.out.println(MaxCommonNum2(3,5));
System.out.println(MaxCommonNum2(12,8));
// 求多个数的最大公约数
int[] arr = {1,2,3,4,5,6};
System.out.println(MaxCommonNumFromMultiNumbers(arr));
// 求两个数的最小公倍数
System.out.println(MinCommonNum(3,5));
System.out.println(MinCommonNum(12,8));
// 求多个数的最小公倍数
int[] array = {4,5,6};
int[] array1 = {1,2,3,4,5,6};
System.out.println(MinCommonNumFromNumbers(array));
System.out.println(MinCommonNumFromNumbers(array1));
}
}
有误之处望请指出，望共同进步。感谢！
