JavaScript求一組數(shù)的最小公倍數(shù)和最大公約數(shù)常用算法詳解【面向?qū)ο?，回歸迭代和循環(huán)】
本文實(shí)例講述了JavaScript求一組數(shù)的最小公倍數(shù)和最大公約數(shù)常用算法。分享給大家供大家參考，具體如下：
方法來自求多個數(shù)最小公倍數(shù)的一種變換算法（詳見附錄說明）
最小公倍數(shù)的算法由最大公約數(shù)轉(zhuǎn)化而來。最大公約數(shù)可通過如下步驟求得：
（1） 找到a1,a2,..,an中的最小非零項(xiàng)aj，若有多個最小非零項(xiàng)則任取一個
（2） aj以外的所有其他非0項(xiàng)ak用ak mod aj代替；若沒有除aj以外的其他非0項(xiàng)，則轉(zhuǎn)到（4）
（3） 轉(zhuǎn)到（1）
（4） a1,a2,..,an的最大公約數(shù)為aj
寫了兩個版本的javascript求公倍數(shù)和公約數(shù)，主要偏重于算法，沒有太注意命名，很多就直接寫的單字母名稱。
0. 簡單易懂的循環(huán)
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 maxDivi(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_maxDivi = maxDivi(brr)
return totalMulti/brr_maxDivi
}
1. function套function
var arr_minMulti, arr_maxdivi
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)
maxDivisor(marr)
arr_minMulti = totalmulti / arr_maxdivi
}
function maxDivisor(arr){
var min = getMin(arr)
if(min === Infinity) {
arr_maxdivi = min
return
}
var exparr = arr.filter(function(item){
return (item !== min && item !== 0)
})
if(exparr.length === 0){
arr_maxdivi = min
return;
}
else{
var modearr = arr.map(function(item){
return (item === min||item===0)? item:item%min
})
console.log(modearr,'modearr')
maxDivisor(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('最小公倍數(shù)',arr_minMulti)
2. object oriented 面向?qū)ο?/strong>
function maxDivisor(arr,origin){
this.arr = arr
this.min = this._getMin(arr)
this.maxDivisor = this._getMaxDiv()
if(origin){
this.minMulti = this._getMinMulti()
}
}
maxDivisor.prototype._getMin = function(arr) {
var min = Infinity
arr.forEach(item => min = (item && item < min)? item : min)
return min
}
maxDivisor.prototype._getMaxDiv = function() {
var arr_maxdivi
var self = this,
arr = this.arr
function maxDivisor(arr){
//console.log(self._getMin)
var min = self._getMin.call(null,arr)
console.log(min,'min')
if(min === Infinity) {
arr_maxdivi = 0
return ;
}
var exparr = arr.filter( item => (item !== min && item != 0) )
if(exparr.length === 0){
arr_maxdivi = min
return;
}
else{
var modearr = arr.map(item =>
(item === min || item === 0)? item : item % min
)
maxDivisor(modearr)
}
}
maxDivisor(this.arr)
return arr_maxdivi
}
maxDivisor.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 maxDivisor(marr,false)
arr_minMulti = totalmulti / b.maxDivisor
return arr_minMulti
}
}
var a = new maxDivisor([12,9,6],true)
console.log(a)
附錄：求多個數(shù)最小公倍數(shù)的一種變換算法原理分析
令[a1,a2,..,an] 表示a1,a2,..,an的最小公倍數(shù)，(a1,a2,..,an)表示a1,a2,..,an的最大公約數(shù)，其中a1,a2,..,an為非負(fù)整數(shù)。對于兩個數(shù)a,b，有[a,b]=ab/(a,b)，因此兩個數(shù)最小公倍數(shù)可以用其最大公約數(shù)計(jì)算。但對于多個數(shù)，并沒有[a1,a2,..,an]=M/(a1,a2,..,an)成立，M為a1,a2,..,an的乘積。例如：[2,3,4]并不等于24/(2,3,4)。即兩個數(shù)的最大公約數(shù)和最小公倍數(shù)之間的關(guān)系不能簡單擴(kuò)展為n個數(shù)的情況。
這里對多個數(shù)最小公倍數(shù)和多個數(shù)最大公約數(shù)之間的關(guān)系進(jìn)行了探討。將兩個數(shù)最大公約數(shù)和最小公倍數(shù)之間的關(guān)系擴(kuò)展到n個數(shù)的情況。在此基礎(chǔ)上，利用求n個數(shù)最大公約數(shù)的向量變換算法計(jì)算多個數(shù)的最小公倍數(shù)。
1．多個數(shù)最小公倍數(shù)和多個數(shù)最大公約數(shù)之間的關(guān)系
令p為a1,a2,..,an中一個或多個數(shù)的素因子，a1,a2,..,an關(guān)于p的次數(shù)分別為r1,r2,..,rn，在r1,r2,..,rn中最大值為rc1=rc2=..=rcm=rmax，最小值為rd1=rd2=..=rdt=rmin，即r1,r2,..,rn中有m個數(shù)所含p的次數(shù)為最大值，有t個數(shù)所含p的次數(shù)為最小值。例如：4,12,16中關(guān)于素因子2的次數(shù)分別為2，2，4，有1個數(shù)所含2的次數(shù)為最大值，有2個數(shù)所含2的次數(shù)為最小值；關(guān)于素因子3的次數(shù)分別為0，1，0，有1個數(shù)所含3的次數(shù)為最大值，有2個數(shù)所含3的次數(shù)為最小值。
對最大公約數(shù)有，只包含a1,a2,..,an中含有的素因子，且每個素因子次數(shù)為a1,a2,..,an中該素因子的最低次數(shù)，最低次數(shù)為0表示不包含[1]。
對最小公倍數(shù)有，只包含a1,a2,..,an中含有的素因子，且每個素因子次數(shù)為a1,a2,..,an中該素因子的最高次數(shù)[1]。
定理1：[a1,a2,..,an]=M/(M/a1,M/a2,..,M/an)，其中M為a1,a2,..,an的乘積，a1,a2,..,an為正整數(shù)。
例如：對于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的次數(shù)都大于等于r1+r2+..+rn-rmax，且有p的次數(shù)等于r1+r2+..+rn-rmax的。這是因?yàn)?/p>
（1）M/ai中p的次數(shù)為r1+r2+..+rn-ri，因而M/a1,M/a2,..,M/an中p的次數(shù)最小為r1+r2+..+rn-rmax。
（2）對于a1,a2,..,an中p的次數(shù)最大的項(xiàng)aj（1項(xiàng)或多項(xiàng)），M/aj中p的次數(shù)為r1+r2+..+rn-rmax。
或者對于a1,a2,..,an中p的次數(shù)最大的項(xiàng)aj，M/aj中p的次數(shù)小于等于M/ak，其中ak為a1,a2,..,an中除aj外其他的n-1個項(xiàng)之一，而M/aj中p的次數(shù)為r1+r2+..+rn-rmax。
因此，(M/a1,M/a2,..,M/an)中p的次數(shù)為r1+r2+..+rn-rmax，從而M/(M/a1,M/a2,..,M/an)中p的次數(shù)為rmax。
上述的p并沒有做任何限制。由于a1,a2,..,an中包含的所有素因子在M/(M/a1,M/a2,..,M/an)中都為a1,a2,..,an中的最高次數(shù)，故有[a1,a2,..,an]=M/(M/a1,M/a2,..,M/an)成立。
得證。
定理1對于2個數(shù)的情況為[a,b]=ab/(ab/a,ab/b)=ab/(b,a)=ab/(a,b)，即[a,b]=ab/(a,b)。因此，定理1為2個數(shù)最小公倍數(shù)公式[a,b]=ab/(a,b)的擴(kuò)展。利用定理1能夠把求多個數(shù)的最小公倍數(shù)轉(zhuǎn)化為求多個數(shù)的最大公約數(shù)。
2．多個數(shù)最大公約數(shù)的算法實(shí)現(xiàn)
根據(jù)定理1，求多個數(shù)最小公倍數(shù)可以轉(zhuǎn)化為求多個數(shù)的最大公約數(shù)。求多個數(shù)的最大公約數(shù)(a1,a2,..,an)的傳統(tǒng)方法是多次求兩個數(shù)的最大公約數(shù)，即
（1）用輾轉(zhuǎn)相除法[2]計(jì)算a1和a2的最大公約數(shù)(a1,a2)
（2）用輾轉(zhuǎn)相除法計(jì)算(a1,a2)和a3的最大公約數(shù)，求得(a1,a2,a3)
（3）用輾轉(zhuǎn)相除法計(jì)算(a1,a2,a3)和a4的最大公約數(shù)，求得(a1,a2,a3,a4)
（4）依此重復(fù)，直到求得(a1,a2,..,an)
上述方法需要n-1次輾轉(zhuǎn)相除運(yùn)算。
本文將兩個數(shù)的輾轉(zhuǎn)相除法擴(kuò)展為n個數(shù)的輾轉(zhuǎn)相除法，即用一次n個數(shù)的輾轉(zhuǎn)相除法計(jì)算n個數(shù)的最大公約數(shù)，基本方法是采用反復(fù)用最小數(shù)模其它數(shù)的方法進(jìn)行計(jì)算，依據(jù)是下面的定理2。
定理2：多個非負(fù)整數(shù)a1,a2,..,an，若aj>ai，i不等于j，則在a1,a2,..,an中用aj-ai替換aj，其最大公約數(shù)不變，即 (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)。
證明：
根據(jù)最大公約數(shù)的交換律和結(jié)合率，有
(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<j情況）。
而對(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<j情況）。
因此只需證明(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的最大公約數(shù)和ai,(aj-ai) 的最大公約數(shù)必須相等，即(ai,aj)=(ai,aj-ai)成立。
得證。
定理2類似于矩陣的初等變換，即
令一個向量的最大公約數(shù)為該向量各個分量的最大公約數(shù)。對于向量<a1,a2,..,an>進(jìn)行變換：在一個分量中減去另一個分量，新向量和原向量的最大公約數(shù)相等。
求多個數(shù)的最大公約數(shù)采用反復(fù)用最小數(shù)模其它數(shù)的方法，即對其他數(shù)用最小數(shù)多次去減，直到剩下比最小數(shù)更小的余數(shù)。令n個正整數(shù)為a1,a2,..,an，求多個數(shù)最大共約數(shù)的算法描述為：
（1）找到a1,a2,..,an中的最小非零項(xiàng)aj，若有多個最小非零項(xiàng)則任取一個
（2）aj以外的所有其他非0項(xiàng)ak用ak mod aj代替；若沒有除aj以外的其他非0項(xiàng)，則轉(zhuǎn)到（4）
（3）轉(zhuǎn)到（3）
（4）a1,a2,..,an的最大公約數(shù)為aj
例如：對于5個數(shù)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個數(shù)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. 多個數(shù)最小共倍數(shù)的算法實(shí)現(xiàn)
求多個數(shù)最小共倍數(shù)的算法為：
（1）計(jì)算m=a1*a2*..*an
（2）把a(bǔ)1,a2,..,an中的所有項(xiàng)ai用m/ai代換
（3）找到a1,a2,..,an中的最小非零項(xiàng)aj，若有多個最小非零項(xiàng)則任取一個
（4）aj以外的所有其他非0項(xiàng)ak用ak mod aj代替；若沒有除aj以外的其他非0項(xiàng)，則轉(zhuǎn)到（6）
（5）轉(zhuǎn)到（3）
（6）最小公倍數(shù)為m/aj
上述算法在VC環(huán)境下用高級語言進(jìn)行了編程實(shí)現(xiàn)，通過多組求5個隨機(jī)數(shù)最小公倍數(shù)的實(shí)例，與標(biāo)準(zhǔn)方法進(jìn)行了比較，驗(yàn)證了其正確性。標(biāo)準(zhǔn)計(jì)算方法為：求5個隨機(jī)數(shù)最小公倍數(shù)通過求4次兩個數(shù)的最小公倍數(shù)獲得，而兩個數(shù)的最小公倍數(shù)通過求兩個數(shù)的最大公約數(shù)獲得。
5. 結(jié)論
計(jì)算多個數(shù)的最小公倍數(shù)是常見的基本運(yùn)算。n個數(shù)的最小公倍數(shù)可以表示成另外n個數(shù)的最大公約數(shù)，因而可以通過求多個數(shù)的最大公約數(shù)計(jì)算。求多個數(shù)最大公約數(shù)可采用向量轉(zhuǎn)換算法一次性求得。
PS：這里再為大家推薦一款本站相關(guān)在線工具供大家參考：
在線最小公倍數(shù)/最大公約數(shù)計(jì)算工具：
http://tools.jb51.net/jisuanqi/gbs_gys_calc
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript事件相關(guān)操作與技巧大全》、《JavaScript操作DOM技巧總結(jié)》及《JavaScript字符與字符串操作技巧總結(jié)》
希望本文所述對大家JavaScript程序設(shè)計(jì)有所幫助。
- JS使用Dijkstra算法求解最短路徑
- javascript算法題 求任意一個1-9位不重復(fù)的N位數(shù)在該組合中的大小排列序號
- javascript算法題：求任意一個1-9位不重復(fù)的N位數(shù)在該組合中的大小排列序號
- javascript使用遞歸算法求兩個數(shù)字組合功能示例
- JavaScript實(shí)現(xiàn)數(shù)組全排列、去重及求最大值算法示例
- javascript中解析四則運(yùn)算表達(dá)式的算法和示例
- JS使用Prim算法和Kruskal算法實(shí)現(xiàn)最小生成樹
- JS實(shí)現(xiàn)計(jì)算小于非負(fù)數(shù)n的素?cái)?shù)的數(shù)量算法示例
- JavaScript采用遞歸算法計(jì)算階乘實(shí)例
- JavaScript實(shí)現(xiàn)的一個計(jì)算數(shù)字步數(shù)的算法分享
- JS求解兩數(shù)之和算法詳解
相關(guān)文章
JS實(shí)現(xiàn)將鏈接生成二維碼并轉(zhuǎn)為圖片的方法
這篇文章主要介紹了JS實(shí)現(xiàn)將鏈接生成二維碼并轉(zhuǎn)為圖片的方法,涉及qrcodejs插件及js圖片生成相關(guān)操作技巧,需要的朋友可以參考下2018-03-03
js判斷數(shù)組是否包含某個字符串變量的實(shí)例
下面小編就為大家分享一篇js判斷數(shù)組是否包含某個字符串變量的實(shí)例，具有很好的參考價(jià)值，希望對大家有所幫助2017-11-11
詳解JavaScript前端如何實(shí)現(xiàn)截屏功能
這篇文章主要為大家詳細(xì)介紹了JavaScript前端如何實(shí)現(xiàn)截屏功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-04-04
JavaScript實(shí)現(xiàn)網(wǎng)頁五子棋小游戲
這篇文章主要為大家詳細(xì)介紹了JavaScript實(shí)現(xiàn)網(wǎng)頁五子棋小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
使用TextRange獲取輸入框中光標(biāo)的位...2006-10-10
javascript 實(shí)現(xiàn)子父窗體互相傳值的簡單實(shí)例
本篇文章主要是對javascript 實(shí)現(xiàn)子父窗體互相傳值的簡單實(shí)例進(jìn)行了介紹，需要的朋友可以過來參考下，希望對大家有所幫助2014-02-02
這篇文章主要介紹了一文弄懂JavaScript的繼承方式,在java面試過程中經(jīng)常被問到j(luò)avascript中有幾種繼承方式，每種繼承方式是怎么實(shí)現(xiàn)的，文中給大家講解的非常詳細(xì)，需要的朋友可以參考下2022-05-05
JavaScript實(shí)現(xiàn)隨機(jī)點(diǎn)名程序
這篇文章主要為大家詳細(xì)介紹了JavaScript實(shí)現(xiàn)隨機(jī)點(diǎn)名程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
用console.table()調(diào)試javascript
昨天我了解到Chrome調(diào)試工具一個小巧的調(diào)試方法，在WDCC期間， Marcus Ross（@zahlenhelfer） 介紹了，chrome調(diào)試工具各種調(diào)試方法，這個只是其中一種，現(xiàn)在我來給大家秀下。2014-09-09
這篇文章主要為大家詳細(xì)介紹了js版掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06