분수 알고리즘에서 마지막으로 약분(reduce a Fraction to Lowest Terms) 을 합니다. 약분은 분자와 분모의 최대공약수(GCD, Great Common Divisor)로 나누는 것을 말합니다. 따라서 약분을 하기 위해서는 최대공약수를 구하면 됩니다. 약분, 최대공약수를 구하라. 최대공약수 구하기 1 최대공약수를 구하는 방법은 여러가지가 있는데 그 첫번째로 분자, 분모 두개를 동시에 나누었을때에 나머지가 없는 수를 구하면 됩니다. 1부터 시작해서 분자, 분모 두수중에 작은 수까지 대입해서 하나씩 나누어서 0이 되는지를 찾아보는 겁니다. 최대공약수를 구하는 무한대입법이라고 보시면 됩니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
def GCDbyDivide(num1, num2): ''' 최대공약수를 구하는 알고리즘. 두수를 나눗셈으로해서 가장큰 약수를 구하는 방법. ''' if num1 < 0: raise RuntimeError('num1 must be above 0') if num2 < 0: raise RuntimeError('num2 must be above 0') miniNum = min(num1, num2) maxDiv = 1 for i in range(1,miniNum+1): if num1%i == 0 and num2%i == 0: maxDiv = i return maxDiv |
작은 수가 무엇인지를 구하기 위해서 min 함수를 이용했습니다. 무한대입법을 […]