[C언어] 열혈강의 C프로그래밍(윤성우 저) 도전! 프로그래밍 ONE. 도전3

도전 3. 두개의 정수를 입력받아서 최대 공약수(GCM)을 구하는 프로그램을 작성해 보자.

 

두가지 알고리즘이 있습니다. 

 

첫번째로. 노가다입니다. 

변수 n을 정하여, n을 1부터 1씩 늘려가면서 

두 정수에서 각각 n으로 나눠보아, 나머지가 0이 되면 그것은 공약수 입니다. 

이때 n을 작은수가 될때까지 늘려가면서 계속 나눠보아, 공약수중 제일 큰 수를 찾으면 그것이 최대공약수 입니다. 

 

두번째로는 유클리드 호제법이 있습니다. 

유클리드 호제법 개념에 관해서는 수학개념이므로, 엮인글에 있는 포스트를 참조하시기 바랍니다. 

또한 엮인글에 유클리드 호제법 알고리즘이 나와있는데!(이해하면 정말 쉽고 간단한 알고리즘입니다.) 

제가 설명할 알고리즘보다 시간 복잡도가 좀 높기 때문에 

여기서는 제가 할 알고리즘으로 풀어보겠습니다. 

 

 

의사코드 

 

첫번째 알고리즘 

두개의 정수를 입력받아서, 

큰수 작은수를 구분한 뒤, 

for(i가 1부터 ; 작은수가 될때까지 ; 1씩 증가) 

{

     큰수 작은수 둘다 n으로 나눈다. 

     if(나눈 값이 둘다 0인가?) 

           i는 최대공약수

} 

 

두번째 알고리즘 

두개의 정수를 입력받아서 

큰수 작은수를 구분한 뒤, 

while(나머지가 (알고리즘 상 작은수) 0이면 반복문 탈출) 

{ 

     큰수에서 작은수를 나눠 나머지를 구함. 

     작은수를 큰수로, 나머지를 작은수로 설정 

} 

큰수는 최대공약수 

 

의사코드만 보고는 잘 이해가 안갈 수도 있습니다.(내마음대로 했거덩ㅋㅋ) 

 

의사코드는 자기 스타일로 하시면 됩니다. 실제 C언어로 옮기는 과정을 도와주는 역할을 수행할 수 

있으면 되니깐요. 

 

실제 코드입니다. 

12~17번째줄까지는 오류처리 줄이고, 

19~20번째줄은 앞서 도전2에서 봤던 큰수 작은수 구분하는 코드이며 

22~29번째줄은 의사코드 안에 내용을 C언어로 바꾼것입니다.  

i를 1씩 늘려가면서, 두수를 나눠서 둘다 0이되는 경우에, 최대공약수로 넣는.. 그것을 반복입니다. 

i가 작은값이 될때까지.. 

지금보니까 또 실수가 있네요... 변수 선언에서 쓸모없는 변수 n을 선언함 ㅠㅠ 

 

실행결과입니다. 

 

두번째 알고리즘 코드입니다. 

21~26번째줄 내용이 다릅니다. 

큰수에서 작은수를 나눠 나머지를 구해놓고, 

작은수를 큰수로, 나머지를 작은수로 하여 

나머지가 0이 될때까지 반복하면 됩니다. 

나머지가 0이될때의 큰수가 최대공약수 입니다. 

 

실행결과입니다. 

 

이상입니다.