本文实例讲述了 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 个数的最大公约数, 因而可以通过求多个数的最大公约数计算. 求多个数最大公约数可采用向量转换算法一次性求得.
PS: 这里再为大家推荐一款本站相关在线工具供大家参考:
在线最小公倍数 / 最大公约数计算工具:
http://tools.jb51.net/jisuanqi/gbs_gys_calc
更多关于 JavaScript 相关内容感兴趣的读者可查看本站专题:JavaScript 数学运算用法总结,JavaScript 数据结构与算法技巧总结,JavaScript 数组操作技巧总结,JavaScript 事件相关操作与技巧大全,JavaScript 操作 DOM 技巧总结及JavaScript 字符与字符串操作技巧总结
来源: http://www.jb51.net/article/139641.htm