반응형
유클리드의 최대 공약수 알고리즘입니다.
알고리즘 문제
Euclid(a, b)
입력: 정수 a, b; 단 >= b >= 0
출력: 최대공약수(a, b)
if(b=0) return a
return Euclid(b, a mod b)
위 조건을 만족하는 함수를 짜서 출력을 해야됩니다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int gcdSubtract(int x, int y){ | |
int subTemp, min, max; | |
if (x > y) { max = x; min = y; } | |
else { max = y; min = x; } | |
subTemp = max - min; | |
if (min != 0) | |
gcdSubtract(subTemp, min); | |
else | |
return max; | |
} |
우선 b가 클 경우 a와 b를 바꾸어줘야됩니다.
Euclid(b, a mod b)에 대한 것이죠.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int gcdModulus(int x, int y){ | |
if (y != 0) | |
gcdModulus(y, x%y); | |
else | |
return x; | |
} |
조건이 만족했다면 위 함수를 호출하게됩니다.
그리고 메인함수에서 출력을 하게됩니다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int main(void) | |
{ | |
int gcdValue, num1, num2; | |
std::cout << "첫번째 수를 입력하시오: "; | |
std::cin >> num1; | |
std::cout << "두번째 수를 입력하시오: "; | |
std::cin >> num2; | |
//gcdValue = gcdModulus(num1, num2); | |
gcdValue = gcdSubtract(num1, num2); | |
std::cout << num1; | |
std::cout << "와"; | |
std::cout << num2; | |
std::cout << "의 최대공약수는 "; | |
std::cout << gcdValue; | |
std::cout << "이다."; | |
return 0; | |
} |
감사합니다.
도움이 되셨으면 공감과 감사의 덧글 부탁드립니다.
반응형
'공부 > 개발노트' 카테고리의 다른 글
[JAVA] 두 개의 class를 이용해서 출력해보자 (0) | 2016.09.06 |
---|---|
[JAVA] public을 이용해서 원의 지름을 구하여라 (0) | 2016.09.06 |
[C/C++] 재귀 함수를 활용한 알고리즘(팩토리얼 예제) (0) | 2016.09.01 |
[JAVA] 반복문 활용하기 (0) | 2016.08.31 |
[JAVA] switch문 활용해보기 (0) | 2016.08.30 |