这次给大家带来如何使用JS求得数组的最小公倍数和最大公约数,使用JS求得数组的最小公倍数和最大公约数注意事项有哪些,下面就是实战案例,一起来看一下。

方法来自求多个数最小公倍数的一种变换算法(详见附录说明)

最小公倍数的算法由最大公约数转化而来。最大公约数可通过如下步骤求得:

(1) 找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个
(2) aj以外的所有其他非0项ak用ak mod aj代替;若没有除aj以外的其他非0项,则转到(4)
(3) 转到(1)
(4) a1,a2,..,an的最大公约数为aj

写了两个版本的javascript求公倍数和公约数,主要偏重于算法,没有太注意命名,很多就直接写的单字母名称。

0. 简单易懂的循环

function getMin(arr){ var min = Infinity arr.forEach(function(item){ if( item < min && item !=0 ){ min = item } }) return min } function howMuchZero(arr){ var zerocount = 0 arr.forEach( function(item){ item === 0 ? zerocount++ : zerocount } ) if(zerocount === arr.length -1) { return true } else return false } function maxpi(arr){ do { var min = getMin(arr) arr = arr.map((item)=> item===min? item:item%min ) } while (!howMuchZero(arr)) return getMin(arr) } function minMulti(arr){ var totalMulti = arr.reduce((pre,item)=> pre = pre * item ) var brr = arr.map((item)=> totalMulti/item ) var brr_maxpi = maxpi(brr) return totalMulti/brr_maxpi }

1. function套function

var arr_minMulti, arr_maxpi function minMulti(arr){ var totalmulti = arr.reduce((multi,curvalue) => multi * curvalue) if (totalmulti === 0) { arr_minMulti = 0 return } var marr = arr.map((item) => totalmulti/item) maxpisor(marr) arr_minMulti = totalmulti / arr_maxpi } function maxpisor(arr){ var min = getMin(arr) if(min === Infinity) { arr_maxpi = min return } var exparr = arr.filter(function(item){ return (item !== min && item !== 0) }) if(exparr.length === 0){ arr_maxpi = min return; } else{ var modearr = arr.map(function(item){ return (item === min||item===0)? item:item%min }) console.log(modearr,'modearr') maxpisor(modearr) } } function getMin(arr){ var min = Infinity arr.forEach(function(item){ if (item && item < min) { min = item } }) return min } arr =[13,20,10,26] minMulti(arr) console.log('最小公倍数',arr_minMulti)

2. object oriented 面向对象

function maxpisor(arr,origin){ this.arr = arr this.min = this._getMin(arr) this.maxpisor = this._getMaxp() if(origin){ this.minMulti = this._getMinMulti() } } maxpisor.prototype._getMin = function(arr) { var min = Infinity arr.forEach(item => min = (item && item < min)? item : min) return min } maxpisor.prototype._getMaxp = function() { var arr_maxpi var self = this, arr = this.arr function maxpisor(arr){ //console.log(self._getMin) var min = self._getMin.call(null,arr) console.log(min,'min') if(min === Infinity) { arr_maxpi = 0 return ; } var exparr = arr.filter( item => (item !== min && item != 0) ) if(exparr.length === 0){ arr_maxpi = min return; } else{ var modearr = arr.map(item => (item === min || item === 0)? item : item % min ) maxpisor(modearr) } } maxpisor(this.arr) return arr_maxpi } maxpisor.prototype._getMinMulti = function(){ var arr = this.arr, arr_minMulti var totalmulti = arr.reduce((multi,curvalue) => multi * curvalue) if (totalmulti === 0) { return 0 } else { var marr = arr.map((item) => totalmulti/item), b = new maxpisor(marr,false) arr_minMulti = totalmulti / b.maxpisor return arr_minMulti } } var a = new maxpisor([12,9,6],true) console.log(a)

附录:求多个数最小公倍数的一种变换算法原理分析

令[a1,a2,..,an] 表示a1,a2,..,an的最小公倍数,(a1,a2,..,an)表示a1,a2,..,an的最大公约数,其中a1,a2,..,an为非负整数。对于两个数a,b,有[a,b]=ab/(a,b),因此两个数最小公倍数可以用其最大公约数计算。但对于多个数,并没有[a1,a2,..,an]=M/(a1,a2,..,an)成立,M为a1,a2,..,an的乘积。例如:[2,3,4]并不等于24/(2,3,4)。即两个数的最大公约数和最小公倍数之间的关系不能简单扩展为n个数的情况。

这里对多个数最小公倍数和多个数最大公约数之间的关系进行了探讨。将两个数最大公约数和最小公倍数之间的关系扩展到n个数的情况。在此基础上,利用求n个数最大公约数的向量变换算法计算多个数的最小公倍数。

1.多个数最小公倍数和多个数最大公约数之间的关系

令p为a1,a2,..,an中一个或多个数的素因子,a1,a2,..,an关于p的次数分别为r1,r2,..,rn,在r1,r2,..,rn中最大值为rc1=rc2=..=rcm=rmax,最小值为rd1=rd2=..=rdt=rmin,即r1,r2,..,rn中有m个数所含p的次数为最大值,有t个数所含p的次数为最小值。例如:4,12,16中关于素因子2的次数分别为2,2,4,有1个数所含2的次数为最大值,有2个数所含2的次数为最小值;关于素因子3的次数分别为0,1,0,有1个数所含3的次数为最大值,有2个数所含3的次数为最小值。

对最大公约数有,只包含a1,a2,..,an中含有的素因子,且每个素因子次数为a1,a2,..,an中该素因子的最低次数,最低次数为0表示不包含[1]。

对最小公倍数有,只包含a1,a2,..,an中含有的素因子,且每个素因子次数为a1,a2,..,an中该素因子的最高次数[1]。

定理1:[a1,a2,..,an]=M/(M/a1,M/a2,..,M/an),其中M为a1,a2,..,an的乘积,a1,a2,..,an为正整数。

例如:对于4,6,8,10,有[4,6,8,10]=120,而M=4*6*8*10=1920,M/(M/a1,M/a2,..,M/an) =1920/(6*8*10,4*8*10,4*6*10,4*6*8)=1920/16=120。

证明:

M/a1,M/a2,..,M/an中p的次数都大于等于r1+r2+..+rn-rmax,且有p的次数等于r1+r2+..+rn-rmax的。这是因为

(1)M/ai中p的次数为r1+r2+..+rn-ri,因而M/a1,M/a2,..,M/an中p的次数最小为r1+r2+..+rn-rmax。

(2)对于a1,a2,..,an中p的次数最大的项aj(1项或多项),M/aj中p的次数为r1+r2+..+rn-rmax。

或者对于a1,a2,..,an中p的次数最大的项aj,M/aj中p的次数小于等于M/ak,其中ak为a1,a2,..,an中除aj外其他的n-1个项之一,而M/aj中p的次数为r1+r2+..+rn-rmax。

因此,(M/a1,M/a2,..,M/an)中p的次数为r1+r2+..+rn-rmax,从而M/(M/a1,M/a2,..,M/an)中p的次数为rmax。

上述的p并没有做任何限制。由于a1,a2,..,an中包含的所有素因子在M/(M/a1,M/a2,..,M/an)中都为a1,a2,..,an中的最高次数,故有[a1,a2,..,an]=M/(M/a1,M/a2,..,M/an)成立。

得证。