大发彩票网首页
        当前位置:大发彩票网-建站教程-网站开发-JavaScript/Ajax教程-JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象,回归迭代和循环】

        JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象,回归迭代和循环】

        时间:2018-05-07来源:大发彩票网 www.lhltmj.com 作者:源码库 文章热度:

        大发彩票网 www.lhltmj.com 本文实例讲述了JavaScript求一组数的最小公倍数和最大公约数常用算法。分享给大家供大家参考,具体如下:

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

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

        (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 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('最小公倍数',arr_minMulti)
        
        

        2. object oriented 面向对象

        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)
        
        

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

        令[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<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的最大公约数和ai,(aj-ai) 的最大公约数必须相等,即(ai,aj)=(ai,aj-ai)成立。

        得证。

        定理2类似于矩阵的初等变换,即

        令一个向量的最大公约数为该向量各个分量的最大公约数。对于向量<a1,a2,..,an>进行变换:在一个分量中减去另一个分量,新向量和原向量的最大公约数相等。

        求多个数的最大公约数采用反复用最小数模其它数的方法,即对其他数用最小数多次去减,直到剩下比最小数更小的余数。令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个数的最大公约数,因而可以通过求多个数的最大公约数计算。求多个数最大公约数可采用向量转换算法一次性求得。

        希望本文所述对大家JavaScript程序设计有所帮助。


        注:相关教程知识阅读请移步到JavaScript/Ajax教程频道。
        相关JavaScript/Ajax教程
        热门标签

        JavaScript/Ajax教程Rss订阅JavaScript/Ajax教程搜索

        大发彩票网官网 | 大发彩票网平台 |
      • 暨南大学获企业捐赠3000万元助建传媒大厦 2018-09-24
      • 商业氛围薄弱开业一拖再拖 合肥凤凰文化广场“好牌”难打 2018-09-24
      • 李安获美国导演工会荣誉奖:以平常心看待 2018-09-24
      • 美民调显示北约国家民众对美“好感度”大幅下滑 2018-09-24
      • “洁净水 滋润未来”大学生水资源竞赛在沪启动 2018-09-24
      • 社区争取资金为困难居民送来电视冰箱 2018-09-24
      • 欧盟经济委员指美国对其贸易制裁“不合适” 2018-09-24
      • 云南腾冲市政协与梁河县政协联合开展南底河水环境保护调研
        同饮一河水共护母亲河
        2018-09-24
      • 奖励生二孩家庭,力度可以更大些 2018-09-19
      • 曝詹姆斯邀请杜兰特同去湖人 但遭后者拒绝 2018-09-19
      • 74家财险公司净利润不足6亿元 2018-09-19
      • 长生生物被证监会立案调查 2018-09-19
      • 国企改革"双百行动"正式启动 下半年有望明显提速 2018-09-19
      • “吃鸡”手游现“731部队” 韩开发商下架道歉 2018-09-16
      • 多省不动产登记联网提速 专家称房地产税渐近 2018-09-16