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

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

May 12, 2018 am 10:43 AM
javascript最大公約數最小公倍數

這次為大家帶來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  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 <p style="text-align: left;"><strong>#2. object oriented <a href="http://www.php.cn/code/327.html" target="_blank">物件導向</a></strong></p><pre class="brush:php;toolbar:false">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  (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中文網其它相關文章!

推薦閱讀:

JS callback回呼函數使用案例詳解

##JS DOM元素常見增刪改查操作詳解

以上是JS取得最小公倍數與最大公約數的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
JavaScript的起源:探索其實施語言JavaScript的起源:探索其實施語言Apr 29, 2025 am 12:51 AM

JavaScript起源於1995年,由布蘭登·艾克創造,實現語言為C語言。 1.C語言為JavaScript提供了高性能和系統級編程能力。 2.JavaScript的內存管理和性能優化依賴於C語言。 3.C語言的跨平台特性幫助JavaScript在不同操作系統上高效運行。

幕後:什麼語言能力JavaScript?幕後:什麼語言能力JavaScript?Apr 28, 2025 am 12:01 AM

JavaScript在瀏覽器和Node.js環境中運行,依賴JavaScript引擎解析和執行代碼。 1)解析階段生成抽象語法樹(AST);2)編譯階段將AST轉換為字節碼或機器碼;3)執行階段執行編譯後的代碼。

Python和JavaScript的未來:趨勢和預測Python和JavaScript的未來:趨勢和預測Apr 27, 2025 am 12:21 AM

Python和JavaScript的未來趨勢包括:1.Python將鞏固在科學計算和AI領域的地位,2.JavaScript將推動Web技術發展,3.跨平台開發將成為熱門,4.性能優化將是重點。兩者都將繼續在各自領域擴展應用場景,並在性能上有更多突破。

Python vs. JavaScript:開發環境和工具Python vs. JavaScript:開發環境和工具Apr 26, 2025 am 12:09 AM

Python和JavaScript在開發環境上的選擇都很重要。 1)Python的開發環境包括PyCharm、JupyterNotebook和Anaconda,適合數據科學和快速原型開發。 2)JavaScript的開發環境包括Node.js、VSCode和Webpack,適用於前端和後端開發。根據項目需求選擇合適的工具可以提高開發效率和項目成功率。

JavaScript是用C編寫的嗎?檢查證據JavaScript是用C編寫的嗎?檢查證據Apr 25, 2025 am 12:15 AM

是的,JavaScript的引擎核心是用C語言編寫的。 1)C語言提供了高效性能和底層控制,適合JavaScript引擎的開發。 2)以V8引擎為例,其核心用C 編寫,結合了C的效率和麵向對象特性。 3)JavaScript引擎的工作原理包括解析、編譯和執行,C語言在這些過程中發揮關鍵作用。

JavaScript的角色:使網絡交互和動態JavaScript的角色:使網絡交互和動態Apr 24, 2025 am 12:12 AM

JavaScript是現代網站的核心,因為它增強了網頁的交互性和動態性。 1)它允許在不刷新頁面的情況下改變內容,2)通過DOMAPI操作網頁,3)支持複雜的交互效果如動畫和拖放,4)優化性能和最佳實踐提高用戶體驗。

C和JavaScript:連接解釋C和JavaScript:連接解釋Apr 23, 2025 am 12:07 AM

C 和JavaScript通過WebAssembly實現互操作性。 1)C 代碼編譯成WebAssembly模塊,引入到JavaScript環境中,增強計算能力。 2)在遊戲開發中,C 處理物理引擎和圖形渲染,JavaScript負責遊戲邏輯和用戶界面。

從網站到應用程序:JavaScript的不同應用從網站到應用程序:JavaScript的不同應用Apr 22, 2025 am 12:02 AM

JavaScript在網站、移動應用、桌面應用和服務器端編程中均有廣泛應用。 1)在網站開發中,JavaScript與HTML、CSS一起操作DOM,實現動態效果,並支持如jQuery、React等框架。 2)通過ReactNative和Ionic,JavaScript用於開發跨平台移動應用。 3)Electron框架使JavaScript能構建桌面應用。 4)Node.js讓JavaScript在服務器端運行,支持高並發請求。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版