기약 분수 구하기

기약 분수

기약분수는 여러 분들이 초등학교때 많이 들어 봤을 겁니다.

 

기약분수: 분수로 표현된 분자와 분모가 1 이외의 공통된 약수로 더 이상 나누어 떨어지지 않는 형태가 된 것을 말한다. 분자와 분모를 1이외의 공통된 약수로 나누느 행위를 약분이라고 한다. 정수 a, b에 대해 분수 a/b가 기약 분수라는 것과 a,b가 서로 소 , 즉 최대공약수가 1이라는 것은 같은 말이다.

이렇듯 최대공약수를 구하는 방법을 알아야한다.

최대 공약수를 구하는 방법중에 대표적이고 유명한 유클리드 호제법에 대해 알아보자.

 

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

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

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

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

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

 

 

즉 재귀 호출로 2번 째 인자에 나머지를 넣고 계속 호출하다가 만약에 나머지가 0이라면 그때의 최대공약수를 반환합니다.

이를 통해 120과 32의 최대공약수를 구해보면

이러한 결과가 나옵니다.

 

이제 기약 분수를 구하는 코드로 가보시죠.

우선 최대 수를 넘지않는 기약분수를 구해야 합니다.

예를 들어 최대수가 5이면 5보다 작거나 같은 숫자를 이용해서 기약분수를 만들어야합니다.

ex) 0/1 . 1/2, 1/3 , 1/4. 2/3, 3/4, 1/5, 2/5, 3/5, 4/5, 1/1 => 총 11개

 

우선 접근방법은 메모장에 테스트 케이스 경우의 수, 최대 수들 입니다.

input.txt

 

3

5

10

15

우선 fropen함수로 파일을 열어 파일에 해당하는 숫자들을 scanf로 입력받습니다.

testCase테스트케이스 수를 입력받고 for문을 통해 그 경우의 수만큼 돌립니다.

Solutions는 개수를 셉니다.

maxNumber를 파일로부터 입력받고 이중 for문을 돌려 j는 분자 k는 분모로 최대 수까지만 돌립니다.

if문을 통해 최대공약수가 1일 경우에 기약분수 이기 때문에 개수도 증가시킵니다.

처음에는 무조건 0/1이 포함되고 마지막에는 1/1이 포함되므로 if문에 걸리지않고 for문에서도 걸리지않습니다. 마지막에 개수만 2개 증가시켜주변됩니다.

GCD(j,k)==1은 최대공약수가 1이므로 이때 찾은 기약분수를 출력해주고 개수를 증가시킵니다.

아래는 코드입니다.