[Javascript | 분수의 덧셈] - 유클리드 알고리즘 및 재귀함수

#분수의 덧셈

 

문제

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

 

접근

(1)유클리드 호제법(while문 및 재귀함수)을 통해 최대공약수를 구한 후, (2) 최대공약수로 약분한 분자와 분모를 배열 데이터로 출력함. 참고로 기약 분수는 분자 분모 최대공약수가 1인 경우를 말함.

---

＃관련 학습

 

1-1)while문 - while(조건식){반복할 코드}

while문은 '조건식'의 결과가 true 인경우 코드 블록을 반복적으로 수행합니다.

추가로 초기화구문 및 종료조건(break문), 증감식이 들어가야 한다. 

[Javascript] 반복문(2) - while

1-2)break문

break문은 if, switch, for,while문등에서 break문을 만나면 바로 빠져나가는 명령문 입니다. 

continue문과 함께 설명되어 있음.

https://www.pinkcoding.com/class/web/JavaScript/js-continue-break/

2)재귀함수

function f(n) {
    if (n <= 1) {
       return 1 // 종료 조건
    }
    return n + f(n-1) // 재귀함수
}
console.log(f(100)) //5050

함수가 자신을 다시 호출하는 구조로 만들어진 함수이며 종료조건을 설정해줘야 함.

[Javascript] 재귀함수

3)유클리드 알고리즘 -최대공약수 구하기

유클리드 호제는 재귀호출로 이루어집니다. 나누어서 떨어질 때까지 반복합니다.

 

1071과 1029의 최대공약수를 구하면

1071과 1029은 나누어 떨어지지 않으므로 나눈 나머지를 구한다. 42

1029는 42와 나누어 떨어지지 않으므로 나눈 나머지를 구한다. 21

42는 21로 나누어 떨어진다. 따라서 21이 최대공약수이다.

 

function gcd(a, b) {
  const remainder = a % b;  // 1번
  if (remainder === 0) return b;  // 2번
  return gcd(b, remainder);  // 3번
}

[Javascript] 최대공약수 알고리즘 (with 유클리드 알고리즘)

---

#풀이

 

최대공약수로 약분한 분자와 분모를 배열 데이터 출력과 관련하여 어렵게 생각할 필요가 없었다

function solution(numer1, denom1, numer2, denom2) {
    const a = numer1*denom2 + numer2*denom1
    const b = denom1*denom2
    //최대공약수 구하기
    function gcd(a, b) {
    const remainder = a % b;  
    if (remainder === 0){return b}  //종료 조건
    else {return gcd(b, remainder)}; //재귀 함수
    }
   return  [a/gcd(a,b), b/gcd(a,b)]
}

다른 풀이는 다음과 같다.

function fnGCD(a, b){
    return (a%b)? fnGCD(b, a%b) : b;
}

function solution(denum1, num1, denum2, num2) {
    let denum = denum1*num2 + denum2*num1;
    let num = num1 * num2;
    let gcd = fnGCD(denum, num); //최대공약수

    return [denum/gcd, num/gcd];
}

---

#기타 참고링크

 

기약 분수 구하기