유클리드 호제법
- 최초 등록일
- 2005.05.22
- 최종 저작일
- 2005.05
- 5페이지/ 한컴오피스
- 가격 2,000원
소개글
많은 도움이 되셨으면 좋겠네요^^
프로그램은 에러가 하나도 없습니다~
컴파일 실행환경
비쥬얼로 컴파일하시면 되요^^
본문내용
1.유클리드 호제법에 대한 정의
2.유클리드 호제법의 소스와 설명
3.소스에 대한 실행화면 캡쳐
4.느낀점
※유클리드 호제법이란?
<유클리드 호제법의 기본 목적은??>
목적은 두 수의 최대공약수를 찾아내는 것이다. 계산은 이미 배운 최대공약수를 구하는 방법에 비해 그렇게 효율적이지는 않지만, 단순한 계산의 반복이기 때문에 컴퓨터에서 잘 사용되는 알고리즘이기도 하다.
<유클리드 호제법의 기본 원리는??>
A 를 B 로 나눈 나머지가 C 일 때, (A와 B의 최대공약수) = (B와 C의 최대공약수)라는 사실과, P가 Q의 약수이면 P와 Q의 최대공약수는 P라는 사실이다. 이것을 이용해 연속적으로 나머지를 구해 가다가 나머지가 0 이 될 때, 즉 한쪽이 한쪽의 약수일 때 멈추어 최대공약수를 쉽게 구하는 것이다.
한 번 증명해보자.
A와 B의 최대공약수를 G라고 하면 각각 A=aG, B=bG (단, a, b는 서로 소)라고 쓸 수 있다. 그러면 위의 식은 다음과 같이 된다.
aG = bGQ + R
(a-bQ)G = R
좌, 우변 모두 정수이므로, G은 R의 약수여야 한다.
참고 자료
없음