JS求最小公倍數（高效算法2—利用最大公約數和遞歸調用）

任務：求數組arr[]中所有資料的最小公倍數。

任務解析：

        求數組所有資料的最小公倍數，可以先将問題簡化為求兩個正整數的最小公倍數，再通過遞歸或數組累加器來求出最後結果。

        而求兩個正整數a,b的最小公倍數c，可先求出最大公約數d,則最小公倍數就顯而易見c=a*b/d；

       求最大公約數的方法參見：https://my.oschina.net/flyyourdream/blog/867327

JS算法實作：

//算法：利用最大公約數求兩整數的最小公倍數
function twoSmallestCommonMultiple(a,b){
  var c=mostCommonDivisor(a,b);
  return a*b/c;
}
//算法：輾轉相減法求兩個整數的最大公約數
function mostCommonDivisor(a,b){
	var c=Math.min(a,b);
		a=Math.max(a,b);
		b=c;
	if(b===0){
		return  alert("error,please input a number bigger than zero");
	}
	var c=a-b;
	while(c>0){
		a=Math.max(b,c);
		b=Math.min(b,c);
		c=a-b;
	}
	return b;
} 
//使用函數調用和遞推的方式求數組所有元素的最小公倍數
function smallestCommonMultiple(arr){
	if(arr.length<2){
		return arr[0];
	}
	var a=0;
	var result=1;
	for(var i=0;i<arr.length;i++){
		result=twoSmallestCommonMultiple(result,arr[i]);
	}
	return result;
}
           

      上述smallestCommonMultiple(arr)，也可以使用Arr.prototype.reduce()累加器進行計算，具體實作方式如下：

function smallestCommonMultiple(arr){
	if(arr.length<2){
		return arr[0];
	}
	var a=0;
	var result=arr.reduce(function(acc,val){
		return twoSmallestCommonMultiple(acc,val);
	},1);
	return result;
}
           

轉載于:https://my.oschina.net/flyyourdream/blog/867338