유클리드 알고리즘
2008. 12. 6. 14:45ㆍ프로그래밍
반응형
유클리드 알고리즘은 주어진 두 정수 사이에 존재하는 최대공약수를 구하는 알고리즘이다.
1. 임의의 정수 m 과 n을 입력받는다.
2. m 을 n 으로 나누어 나머지를 r 에 입력한다.
3. r 이 0 이면 n 이 최대 공약수가 된다. r 이 0 이 아니면 m 에 n 을 입력하고, n 에 r 을 입력한 후 2번부터 다시 반복한다.
위의 C 코드는 아주 단순한 코드이지만 상당히 심플하게 최대공약수를 구할 수 있도록 되어있다.
이 코드보다 단순한 코드도 존재하지만 이 코드는 유클리드 알고리즘의 설명을 위해 알고리즘에 충실하게 짜여진 코드이다.
우선 두 수 중 큰 수를 m 에 입력하고 작은 수를 n 에 입력한다.(뭐 처음부터 그렇게 되어 있다면 swap이 필요없겠지만 말이다)
이제는 좀더 코드를 알차게 만들어보자
1. while 문에서 if() break; 문은 while문의 조건으로 빼면 더 좋지 않을까?
2. swap 코드는 필요한 코드인가 ?
위 두가지 문제를 해결하면
또 다른 방법은 재귀를 사용하는 방법이 있다.
반응형