首頁 >web前端 >js教程 >JS取得最小公倍數與最大公約數

JS取得最小公倍數與最大公約數

php中世界最好的语言原創: 2018-05-12 10:43:583525瀏覽

這次為大家帶來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(&#39;最小公倍数&#39;,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,&#39;min&#39;)
    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)成立。 ######得證。 ###

定理1對於2個數的情況為[a,b]=ab/(ab/a,ab/b)=ab/(b,a)=ab/(a,b)，即[a, b]=ab/(a,b)。因此，定理1為2個數最小公倍數公式[a,b]=ab/(a,b)的擴展。利用定理1能夠把求多個數的最小公倍數轉換為求多個數的最大公約數。

2．多個數最大公約數的演算法實現

根據定理1，求多個數最小公倍數可以轉換為求多個數的最大公約數。求多個數的最大公約數(a1,a2,..,an)的傳統方法是多次求兩個數的最大公約數，即

（1）用輾轉相除法[2]計算a1和a2的最大公約數(a1,a2)

（2）用輾轉相除法計算(a1,a2)和a3的最大公約數，求得(a1,a2,a3)

（3）用輾轉相除法計算(a1,a2,a3)和a4的最大公約數，求得(a1,a2,a3,a4)

（4）依此重複，直到求得(a1,a2,..,an)

上述方法需要n-1次輾轉相除運算。

本文將兩個數的輾轉相除法擴展為n個數的輾轉相除法，即用一次n個數的輾轉相除法計算n個數的最大公約數，基本方法是採用反覆用最小數模其它數的方法進行計算，依據是下面的定理2。

定理2：多個非負整數a1,a2,..,an，若aj>ai，i不等於j，則在a1,a2,..,an中用aj-ai替換aj ，其最大公約數不變，即(a1,a2,..,aj-1,aj,aj 1,..an)=(a1,a2,..,aj-1,aj-ai,aj 1, ..an)。

例如：(34,24,56,68)=(34,24,56-34,68)=(34,24,22,68)。

證明：

根據最大公約數的交換律和結合率，有

(a1,a2,..,aj-1,aj,aj 1,. .an)= ((ai,aj),(a1,a2,..,ai-1,ai 1,..aj-1,aj 1,..an))（i>j情況），或

(a1,a2,..,aj-1,aj,aj 1,..an)= ((ai,aj),(a1,a2,..,aj-1,aj 1,.. ai-1,ai 1,..an))（i

而對(a1,a2,..,aj-1,aj-ai,aj 1,..an)，有

(a1,a2,..,aj-1 ,aj-ai,aj 1,..an)= ((ai, aj-ai),( a1,a2,..,ai-1,ai 1,.. aj-1,aj 1,..an) )（i>j情況），或

(a1,a2,..,aj-1,aj-ai,aj 1,..an)= ((ai, aj-ai),( a1 ,a2,..,aj-1,aj 1,.. ai-1,ai 1,..an))（i

因此只需證明(ai,aj)=( ai, aj-ai)即可。

由於(aj-ai)= aj-ai，因此ai,aj的任意公因子必然也是(aj-ai)的因子，即也是ai,( aj-ai)的公因子。由於aj = (aj-ai) ai，因此ai,( aj-ai)的任意公因子必然也是aj的因子，即也是ai,aj的公因子。所以，ai,aj的最大公約數和ai,(aj-ai) 的最大公約數必須相等，即(ai,aj)=(ai,aj-ai)成立。

得證。

定理2類似於矩陣的初等變換，即

令一個向量的最大公約數為該向量各個分量的最大公約數。對於向量進行變換：在一個分量中減去另一個分量，新向量和原向量的最大公約數相等。

求多個數的最大公約數採用重複用最小數模其它數的方法，即對其他數用最小數多次去減，直到剩下比最小數更小的餘數。令n個正整數為a1,a2,..,an，求多個數最大共約數的演算法描述為：

（1）找出a1,a2,..,an中的最小非零項aj，若有多個最小非零項則任取一個

（2）aj以外的所有其他非0項ak用ak mod aj代替；若沒有除aj以外的其他非0項，則轉到（4）

（3）轉到（3）

（4）a1,a2,..,an的最大公約數為aj

#例如：對於5個數34, 56, 78, 24, 85，有

(34, 56, 78, 24, 85)=(10,8,6,24,13)=(4, 2,6,0,1)=(0,0,0,0,1)=1，

對於6個數字12, 24, 30, 32, 36, 42，有

(12, 24, 30, 32, 36, 42)=(12,0,6,8,0,6)=(0,0,0,2,0,6)=(0,0,0 ,2,0,0)=2。

3. 多個數最小共倍數的演算法實現

求多個數最小共倍數的演算法為：

（1）計算m=a1*a2*..*an

（2）把a1,a2,..,an中的所有項ai用m/ai代換

（3）找到a1 ,a2,..,an中的最小非零項aj，若有多個最小非零項則任取一個

（4）aj以外的所有其他非0項ak用ak mod aj代替；若沒有aj以外的其他非0項，則轉到（6）

（5）轉到（3）

（6）最小公倍數為m/aj

上述演算法在VC環境下用高級語言進行了編程實現，透過多組求5個隨機數最小公倍數的實例，與標準方法進行了比較，驗證了其正確性。標準計算方法為：求5個隨機數最小公倍數透過求4次兩個數的最小公倍數獲得，而兩個數的最小公倍數則是求兩個數的最大公約數來獲得。

5. 結論

計算多個數的最小公倍數是常見的基本運算。 n個數的最小公倍數可以表示成另外n個數的最大公約數，因而可以透過求多個數的最大公約數來計算。求多個數最大公約數可採用向量轉換演算法一次求得。

相信看了本文案例你已經掌握了方法，更多精彩請關注php中文網其它相關文章！