입력 받은 두 수의 최대 공약수를 구하는 소스

/*  

     뺄셈으로 최대공약수를 구함

 

     흐름 1. 두 수를 입력 받는다.

           2. 두번째 입력 받은 수(b)가 첫번째 수(a)보다 크다면 두 값을 교환한다.

           3. 첫번째 받은 수에 첫번째 수에 두번째 수를 뺀 값을 저장한다.

           4. 그 값이 0이 아니라면, 2번째 단계로 돌아가고, 0이라면 b의 값이 최대공약수이다.

    

     예: 280, 30 → 280-30, 30 = 250, 30

                        250-30, 30 = 220, 30

                        220-30, 30 = 190, 30

                        190-30, 30 = 160, 30

                        160-30, 30 = 130, 30

                        130-30, 30 = 100, 30

                        100-30, 30 = 70, 30

                          70-30, 30 = 40, 30

                          40-30, 30 = 10, 30

                              10, 30 = 30, 10  → 두 수 교환

                          30-10, 10 = 20, 10

                          20-10, 10 = 10, 10

                          10-10, 10 =  0, 10  

                                0, 10 = 10, 0   

 

                     →  최대공약수: 10

                         

     평가: 입력받은 두 수의 차를 구하는 횟수가 적다면,

            단순처리(뺄셈과 교환)이기 때문에 무난한 속도를 보이지만..

            그 횟수가 많아 진다면 실행시간이 길어진다는 단점이 있다.

*/

 

#include <stdio.h>

 

int get_GCD(int a, int b)
{
    int t;

 

    while(a)
    {
       if(a<b)
       {
            t = a;
            a = b;
            b = t;
       }
     a = a-b;
    }
    return b;
}

void main(void)
{
        int a,b;
        puts("\n Get the GCD of two positive integer." /* Input 0 to end program"*/);

 

        while(1)
        {
           puts("\n\n ↓ Input two positive integer");
           scanf("%d %d", &a, &b);

 

           if(a<0 || b<0)
           {
               printf("'음수'는 입력하지 마세요.");
               continue;
            }

            if(a==0 || b==0)
            {
               printf("'0'은 입력하지 마세요.");
               continue;      
//            break;
            }
          printf("\n %d와 %d의 최대공약수는  %d (이)다.", a, b, get_GCD(a,b));
        }

}

 

 

===========================================================================================

 

/*

    

     두 수를 나눈 나머지 값을 이용한 최대 공약수 구하기

     

     흐름 1. 두 수를 입력 받는다.

            2. 두번째 입력 받은 수가 0이면 첫번째 수가 최대 공약수이다.

                0이 아니면 첫번째 입력한 수를 담고 있는 변수(a)에 a%b의 값을 대입한다.

                그리고 a와 b의 값을 교환한다.

            3. 2단계로 돌아간다.

 

*/

 

#include <stdio.h>

int get_GCD(int a, int b)
{
    int t;

   

    while(b)
    {
        t = a%b;
        a = b;
        b = t;
     }
   return a;
}

 

void main(void)
{
        int a,b;
        puts("\n Get the GCD of two positive integer." /* Input 0 to end program"*/);

      

        while(1)
        {
            puts("\n\n ↓ Input two positive integer");
            scanf("%d %d", &a, &b);

 

            if(a<0 || b<0)
            {
                printf("'음수'는 입력하지 마세요.");
                continue;
             }

            if(a==0 || b==0)
            {
                break;
            }
          printf("\n %d와 %d의 최대공약수는  %d (이)다.", a, b, get_GCD(a,b));
        }

}

 

=========================================================================================

 

/*

 

   함수의 재귀호출을 이용한 최대공약수를 구하는 방법

  

   평가: 실행속도는 준수하나....알고리즘의 최적화 단계에서는 피하는 것이 좋다. 

          재귀호출은 시스템 내부 스택을 사용하기 때문에 overflow로 인한

          에러를 유발시킬 수 있다. 

*/

 

 

#include <stdio.h>

 

int get_GCD(int a, int b)
{
      if(b==0)
          return a;
      else
          return get_GCD(b,a%b);
}

 

void main(void)
{
        int a,b;
        puts("\n Get the GCD of two positive integer." /* Input 0 to end program"*/);

      

        while(1)
        {
           puts("\n\n ↓ Input two positive integer");
           scanf("%d %d", &a, &b);

        

           if(a<0 || b<0)
           {
               printf("'음수'는 입력하지 마세요.");
               continue;
           }

  

           if(a==0 || b==0)
           {
               printf("'0'은 입력하지 마세요.");
               continue;      
//            break;
           }
         printf("\n %d와 %d의 최대공약수는  %d (이)다.", a, b, get_GCD(a,b));
        }
}

gcd2.cpp

0.0MB

GCD3.CPP

0.0MB

GCD.CPP

0.0MB