Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 분수를 기약분수로 약분하는 방법 – GCD 활용 가이드

문제 개요

두 개의 정수 Num1과 Num2가 입력으로 주어집니다. 이 두 정수는 분수 Num1/Num2로 표현할 수 있으며, 목표는 이 분수를 더 이상 약분할 수 없는 기약분수(가장 간단한 형태)로 만드는 것입니다.

GCD(최대공약수)를 이용한 약분 원리

  • 두 수의 최대공약수(GCD)를 계산합니다.

  • 두 수를 각각 GCD로 나눕니다.

  • 나눈 결과인 몫을 변수에 다시 저장합니다.

  • 최종적으로 Num1/Num2가 기약분수가 됩니다.

여기서 사용되는 GCD 계산은 유클리드 호제법(Euclidean Algorithm)을 기반으로 하며, 시간 복잡도는 O(log(min(a, b)))로 매우 효율적입니다.

예제

입력 — Num1=22, Num2=10

출력 — Num1 = 11, Num2 = 5

기약분수 : 11/5

설명 — 22와 10의 GCD는 2입니다.
22÷2=11, 10÷2=5이므로 기약분수는 11/5입니다.

입력 — Num1=36, Num2=40

출력 — Num1 = 9, Num2 = 10

기약분수 : 9/10

설명 — 36과 40의 GCD는 4입니다.
36÷4=9, 40÷4=10이므로 기약분수는 9/10입니다.

알고리즘 접근 방식

이 접근 방식에서는 재귀 호출을 통해 먼저 입력받은 두 수의 GCD를 계산합니다. 그다음 두 수를 GCD로 나누어 몫을 구하고, 이 몫들이 곧 기약분수의 분자와 분모가 됩니다.

  • 입력 변수 Num1과 Num2를 받습니다.

  • findGCD(int a, int b) 함수는 num1과 num2를 인자로 받아 두 수의 최대공약수를 반환합니다.

  • b가 0이면 a를 반환하고, 그렇지 않으면 findGCD(b, a%b)를 재귀 호출합니다.

  • lowestFraction(int num1, int num2) 함수는 두 수를 입력받아 기약분수를 출력합니다.

  • GCD 값을 저장할 변수 denom을 선언합니다.

  • num1 = num1/denom, num2 = num2/denom으로 설정합니다.

  • num1과 num2를 출력합니다.

  • 기약분수를 num1/num2 형태로 출력합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
int findGCD(int a, int b) {
    if (b == 0)
        return a;
        return findGCD(b, a % b);
    }
    void lowestFraction(int num1, int num2){
        int denom;
        denom = findGCD(num1,num2);
        num1/=denom;
        num2/=denom;
        cout<< "Num1 = " << num1<<endl;
        cout<< "Num2 = " << num2<<endl;
        cout<< "Lowest Fraction : "<<num1<<"/"<<num2;
}
int main(){
    int Num1 = 14;
    int Num2 = 8;
    lowestFraction(Num1,Num2);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Num1 = 7
Num2 = 4
Lowest Fraction : 7/4