이진-최대공약수 알고리즘.
최대공약수를 구하는 알고리즘에는 대표적으로 유클리드 호제법이 있다. 유클리드 호제법을 간단히 설명하면 다음과 같다. 1. 두 수 a,b를 입력받는다. 2. a가 b보다 크면 a를 b로 나눈 나머지를 구한다. b가 a보다 크면 그 반대로 한다. 3. 나누어서 얻는 나머지를 새로운 a, 원래 a,b중 작은값을 b로 하고 2번으로 돌아간다. 4. 만약 a나 b가 0이 되었다면 이 때의 나머지 b나 a의 값이 최대공약수이다. 이 알고리즘은 a와 b의 최대공약수나 a-b와의 최대공약수나 같다는 사실을 이용해서 쉽게 증명할수 있다. int gcd(int a,int b) { if(b==0)return a; return gcd(a,a%b); } 위 코드는 유클리드 호제법을 간단하게 c코드로 짜본것이다. (단 a>=b일..
프로그래밍/테크닉
2008. 12. 20. 22:01
