'[Public] 컴퓨터공학'에 해당되는 글 27건

  1. 2009.05.04 [알고리즘] 유클리드 호제법 (1)
2009.05.04 12:32

2009. 05. 04 ()






유클리드(B.C. 365 ~ B.C.300)는 기하학의 아버지라고 불리는 유명한 고대 수학자 그 중 가장 유명한 것이 13권으로 구성된 기하학 원본 그 책은 그 선배인 피타고라스 플라톤 히포크라테스등의 연구한 여러 가지의 자료를 정선하고 거기에 자신의 창작을 가미하여 조직적인 교과서로 편찬한 것으로 수학사상 최고의 성전 이라 할 수 있음

 

 

1.     최대공약수(GCD : Greatest Common Divisor)

 

-       정수 a, b의 약수 중에서 공통된 약수를 공약수라 하며 공약수중 가장 큰 수를 최대 공약수라고 한다.

 

-       최대공약수를 구하기 위해서는 다음과 같은 과정을 거쳐야 한다.

 

1.      정수 a의 약수로 구성된 집합 A를 구한다.

2.      정수 b의 약수로 구성된 집합 B를 구한다.

3.      정수 a b의 공약수로 구성된 집합 C를 구한다(집합 A와 집합 B의 교집합)

4.      집합 C에서 가장 큰 수인 c가 정수 a b의 최대공약수이다.

 

-       한계점

 

1.      정수와 약수를 구하는데 그 값이 매우 큰 경우에는 많은 시간이 걸린다.

2.      A 집합과 B 집합의 교집합을 구해서 공약수 집합인 C를 만드는데 시간이 오래 걸린다. A B 집합의 모든 요소들을 비교해서 같은 값을 찾는 작업이 집합내의 요소의 수가 많은 경우에는 많은 시간을 필요로 한다.

3.      공약수의 집합인 C에서 최대공약수인 C를 찾는데 대소 비교를 통해 가장 큰 수를 찾아야 하므로 많은 시간이 소요된다.

 

 

 

2.     유클리드 알고리즘

 

-       유클리드 호제법이라고도 불리우는 이 알고리즘은 주어진 서로 소가 아닌 두 수 a, b에 대해 최대공약수를 찾는 것으로 다음 두 규칙을 전제로 하고 있다.

 

1.     b a로 나눠서 떨어지면 두 수의 최대공약수는 b 이다.

2.     a b로 나눴을 때 나머지가 r이면, 두 수의 최대공약수는 r b의 최대공약수와 같다.

3.      

-       Ex) 1804 328의 최대공약수 구하기.

 

1.     1804 328로 나누었을 때의 나머지 r 164 이다.

2.     다음으로 328 164의 최대공약수를 구한다. 328 164로 나누었을 때의 나머지는 0이므로 최대공약수는 164 이다.

 

-       Ex) 120 50의 최대공약수 구하기

 

1.     120 50으로 나누었을 때의 나머지 r 20이다.

2.     다음으로 50 20의 최대공약수를 구한다. 50 20으로 나누었을 때의 나머지는 10이다.

3.     다음으로 20 10의 최대공약수를 구한다. 20 10으로 나누었을 때의 나머지는 0이므로 최대공약수는 10이 최대공약수 이다.

 

3.     소스

#include "stdafx.h"

#include <stdio.h>

 

int InputData();

 

int _tmain(int argc, _TCHAR* argv[])

{

 

        printf("============= 유클리드호제법==============\n");

        printf("최대공약수를구하려는두수를입력하시요\n");

 

        int a, b;

 

        printf("a = ");

        a = InputData();

        printf("b = ");

        b = InputData();

 

        int i = 0;

              

        while(b != 0)

        {

               i++;

               int c = b;

               b = a%b;

               a = c;

               printf("[%d]step (%d, %d)\n",i, a, b);

        }

 

        printf(" GCD = %d\n" , a);

       

        return 0;

}

 

int InputData()

{

        int i;

        scanf("%d", &i);

        return i;

}


 

Posted by 차출발 차출발

댓글을 달아 주세요

  1. hojun 2013.11.07 21:33  댓글주소  수정/삭제  댓글쓰기

    2-1을 보면 b를 a로 나누어 떨어지면 최대공약수는 b ...라고 돼 있는데, a 가 최대공약수가 됩니ㄷㅏ ^^