'gcd'에 해당되는 글 1건

  1. 2008.11.28 유클리드 호제법 (1)
일반2008. 11. 28. 17:25
http://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

학교 졸업후 이걸 쓰는 분이 많지 않은 지라 대부분의 직딩들은 기억이 나지 않을 것이다.
간단히 이야기 하자면, 두 자연수의 최대공약수(gcd) 를 구하는 알고리즘이다.
최대공약수까지 모르신다면...흠...고통스럽다...
어쨌거나...
알고리즘의 핵심은 두 자연수중 큰 수에서 작은 수를 나누어 "나머지"를 구하는 데 있다. 몫은 중요하지 않다.
mod  또는 % 연산 등이라고 할까나...'
그리고 이전 연산의 값중 작은 값을 얻어진 나머지로 다시 나누어 나머지를 구한다.
그리고... 이런 연산의 무한 반복이다...
단, 무한 반복은 항상 조건식이 있다!!
조건은 나머지가 0 (=zero) 이면 종료된다는 것....

def gcd(m,n):
   while n != 0:   
      t = m%n
      m = n
      n = t        
   return abs(m)

예를 들어 두 자연수 1071 과  1029 의  gcd 를 구해보자.
 
1단계) 1071 % 1029 = 42 (% 는 나머지 구하는 연산)
2단계) 1029  % 42 = 21
3단계) 42 % 21 = 0 (드디어 나머지가 0이다!!)

그러면, 이때  gcd 는 21 이다.
  

'일반' 카테고리의 다른 글

에도가와 란포  (0) 2008.12.05
웹컴파스 삭제하기(Uninstall WebCompass)  (10) 2008.11.29
유클리드 호제법  (1) 2008.11.28
소수 수학 최대의 미스터리  (2) 2008.11.28
착각하는 뇌  (0) 2008.11.24
바퀴는 앞뒤로만 가는 것이 아니라능...  (0) 2008.11.11
Posted by 어쩌다보니 Jay Two

댓글을 달아 주세요

  1. 잘보고 갑니다.
    행복하세요 ^^/

    2008.11.28 17:38 신고 [ ADDR : EDIT/ DEL : REPLY ]