JS에서 최소 공배수와 최대 공약수를 찾는 방법

이번에는 JS에서 최소공배수와 최대공약수를 구하는 방법을 알려드리겠습니다. JS에서 최소공배수와 최대공약수를 구하는 주의사항은 무엇인가요? , 살펴 보겠습니다.

이 방법은 배수의 최소 공배수를 찾는 변환 알고리즘에서 비롯됩니다(자세한 내용은 부록 참조)

최소 공배수에 대한 알고리즘은 최대 공약수에서 변환됩니다. 최대 공약수는 다음 단계를 통해 얻을 수 있습니다.

(1) a1, a2,...,an 중에서 0이 아닌 가장 작은 항 aj를 찾습니다. 0이 아닌 최소 항이 여러 개인 경우 하나를 선택합니다. (2) aj 이외의 모든 0이 아닌 항 ak of는 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

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;">2. 객체 지향<strong><a href="http://www.php.cn/code/327.html" target="_blank"></a><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입니다. 2의 차수를 최대값으로 포함하는 숫자가 있고, 차수를 포함하는 숫자가 2개 있습니다. 소수에 관한 최소값은 2입니다. 인수 3의 차수는 각각 0, 1, 0입니다. 한 숫자에는 3차가 최대값으로 포함되고, 3차가 최소값으로 포함되는 숫자는 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(하나 이상의 항목)의 경우 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)이 성립됩니다.

인증을 받으세요.

숫자가 2개인 경우의 정리 1은 [a,b]=ab/(ab/a,ab/b)=ab/(b,a)=ab/(a,b), 즉 [a, b] =ab/(a,b). 따라서 정리 1은 두 숫자 [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 Evolution 및 Division 연산이 필요합니다.

이 글은 두 수의 유클리드 나눗셈을 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)의 인수여야 합니다. 즉, aj의 공통 인수이기도 합니다( 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,... 중에서 0이 아닌 가장 작은 항 aj를 찾습니다. .,an, 0이 아닌 최소 항이 여러 개 있는 경우 하나를 선택하세요.

(2) aj를 제외한 다른 모든 0이 아닌 항 ak는 aj를 제외한 다른 0이 아닌 항이 없으면 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) 최소 non-가 여러 개인 경우 a1, a2,..,an에서 0이 아닌 최소 항 aj를 찾습니다. 0 항 중 하나를 선택합니다.

(4) aj를 제외한 다른 모든 0이 아닌 항 ak는 ak mod aj로 대체됩니다. aj를 제외한 다른 0이 아닌 항이 없으면 (6)으로 이동합니다.

(5) 이동 (3)

으로

(6) 최소 공배수는 m/aj입니다

위 알고리즘은 VC 환경에서 고급 언어로 프로그래밍하고 구현한 것입니다. 표준 방법과 비교하여 성별이 올바른 것으로 확인되었습니다. 표준 계산 방법은 다음과 같습니다. 난수 5개의 최소공배수를 구하는 것은 두 숫자의 최소공배수를 4번 구하여 구하고, 두 숫자의 최소공배수는 두 숫자의 최대공약수를 구하여 구하는 것입니다.

5. 결론

배수의 최소공배수를 계산하는 것은 일반적인 기본 연산입니다. n개의 수의 최소공배수는 다른 n개의 수의 최대공약수로 표현할 수 있으므로, 배수의 최대공약수를 구하여 계산할 수 있습니다. 여러 숫자의 최대 공약수를 찾으려면 벡터 변환 알고리즘을 사용하여 한 번에 찾을 수 있습니다.

이 기사의 사례를 읽은 후 방법을 마스터했다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!

추천 자료:

노드에서 비동기를 사용하여 동시성을 제어하는 ​​방법

Vue+better-scroll을 사용하여 알파벳순 인덱스 탐색을 구현하는 방법

위 내용은 JS에서 최소 공배수와 최대 공약수를 찾는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!