JSで最小公倍数と最大公約数を見つける方法

今回はJSで最小公倍数と最大公約数を求める方法を紹介します。 以下はJSで最小公倍数と最大公約数を求めるための注意点です。 、見てみましょう。

この方法は、複数の数値の最小公倍数を見つけるための変換アルゴリズムに由来しています (詳細については付録を参照)

最小公倍数のアルゴリズムは、最大公約数から変換されます。最大公約数は次の手順で取得できます:

(1) a1、a2、...、an の中から最小の非ゼロ項 aj を見つけます。複数の最小の非ゼロ項がある場合は、いずれかを選択します
。 (2) aj 以外の他のすべての非ゼロ項 ak of は ak mod aj に置き換えられます。 aj 以外に他の非ゼロ項がない場合は、(4)
(3) に進みます。 ) a1,a2,..., an の最大公約数は aj です

私は公倍数と公約数を見つけるために 2 つのバージョンの

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. 関数セット関数

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. オブジェクト指向

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 は非負の整数です。 2 つの数値 a、b の場合、[a, b] = ab/(a, b) であるため、2 つの数値の最小公倍数は最大公約数を使用して計算できます。ただし、複数の数値の場合、[a1,a2,..,an]=M/(a1,a2,..,an) は成立せず、M は a1,a2,..,an の積になります。たとえば、[2,3,4] は 24/(2,3,4) と等しくありません。つまり、2 つの数の最大公約数と最小公倍数の関係は、単純に n 個の数の場合に拡張することはできません。

ここでは、複数の数の最小公倍数と複数の数の最大公約数の関係について説明します。 2 つの数値の最大公約数と最小公倍数の関係を n 個の数値の場合に拡張します。これに基づいて、n 個の数値の最大公約数を求めるベクトル変換アルゴリズムを使用して、複数の数値の最小公倍数を計算します。

1．複数の数値の最小公倍数と複数の数値の最大公約数の関係

a1、a2、..、an、a1、a2、..、an 内の 1 つ以上の数値の素因数を p とします。 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 です。最大値として 2 の次数を含む数値が 1 つあり、次数を含む数値が 2 つあります。素数について 因数 3 の次数はそれぞれ 0、1、0 であり、最大値として 3 の次数を含む数が 1 つと、最小値として次数を含む数が 2 つあります。 。

最大公約数については、a1、a2、...、anに含まれる素因数のみが含まれ、各素因数の次数はa1、a2、...、anの素因数の最小次数となります。 、最小次数が 0 は [1] が含まれないことを意味します。

最小公倍数の場合、a1、a2、...、anに含まれる素因数のみが含まれ、各素因数の次数はa1、a2、...、の素因数の最高次数になります。 [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 のうちの aj 以外です。 a2,..,an の n-1 項の 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)が成立する。

認定を取得しましょう。

2 つの数の場合の定理 1 は、[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) の最大公約数を求める従来の方法は、2 つの数値の最大公約数を複数回求めることです。つまり、

(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 回の進化と除算の操作が必要です。

この記事では、2 つの数のユークリッド除算を n 数のユークリッド除算に拡張します。つまり、n 数のユークリッド除算を一度に使用して、n 数の最大公約数を計算します。基本的な方法は、最小のものを繰り返し使用することです。他を変調する数値 計算は、次の定理 2 に基づいて数値法を使用して実行されます。

定理 2: 複数の非負の整数 a1、a2、...、an について、aj>ai、i が j に等しくない場合、a1、a2、...、an 内の aj を aj-ai に置き換えます。 、およびその最大公約母 数値は変更されません。つまり、(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 は行列の初等変換、つまり

ベクトルの最大公約数をベクトルの各成分の最大公約数とする。ベクトル の場合、変換: 1 つの成分を別の成分から減算し、新しいベクトルは元のベクトルの最大公約数に等しくなります。

複数の数値の最大公約数を求めるには、他の数値を最小の数値で繰り返し変調する方法を使用します。つまり、最小の数値より小さい余りが残るまで、最小の数値で他の数値を複数回減算します。 n 個の正の整数を a1、a2、...、an とします。複数の数値の最大公約数を見つけるアルゴリズムは次のように記述されます:

(1) a1、a2、...の中から最小の非ゼロ項 aj を見つけます。 .,an, 最小の非ゼロ項が複数ある場合は、いずれかを選択します

(2) aj 以外に非ゼロ項がない場合、aj を除く他のすべての非ゼロ項 ak は、ak mod aj に置き換えられます。 (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 を見つけます。ゼロ項の場合は、任意の 1 つを取得します

(4) aj を除く他のすべての非 0 項 ak は、ak mod aj に置き換えられます。aj 以外に他の非 0 項がない場合は、(6) に進みます

(5) (3)へ

(6) 最小公倍数は m/aj です

上記のアルゴリズムは、5 つの乱数の最小公倍数を見つける例の複数のグループを通じて、VC 環境の高級言語でプログラムおよび実装されました。標準的な方法と比較し、正しい性別であることが確認されました。標準的な計算方法は、5 つの乱数の最小公倍数を求めるには 2 つの数の最小公倍数を 4 回求めることで得られ、2 つの数の最小公倍数は 2 つの数の最大公約数を求めることで得られます。

5. 結論

複数の数値の最小公倍数を計算することは、一般的な基本操作です。 n 個の数値の最小公倍数は、他の n 個の数値の最大公約数として表現できるため、複数の数値の最大公約数を求めることで計算できます。複数の数値の最大公約数を見つけるには、ベクトル変換アルゴリズムを使用して、すべてを一度に見つけることができます。

この記事の事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、php 中国語 Web サイトの他の関連記事に注目してください。

推奨読書:

ノードで async を使用して同時実行性を制御する方法

Vue+better-scroll を使用してアルファベット順のインデックス ナビゲーションを実装する方法

以上がJSで最小公倍数と最大公約数を見つける方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。