유클리드 알고리즘 을 상세 하 게 해석 하 다.

929 단어 알고리즘gcd
현재 두 개의 정수, a, b 가 있다.
a > b 라면 a = kb + q 가 있 습 니 다.
a 를 b 로 나 누 면 k 여 q, 즉 a% b = q 를 얻 을 수 있 습 니 다.
d 가 a 와 b 의 최대 공약수 라 고 가정 하면 a 는 d 에 의 해 정 제 될 수 있 고 b 도 d 에 의 해 정 제 될 수 있 으 며 q = a - kb 그래서 q 도 d 에 의 해 정 제 될 수 있 기 때문에 d 는 b 와 q 의 공약수 이다.
그래서 a 와 b 의 공약수 d 는 b 와 q (a% b) 의 공약수 이기 도 한다.
a2 = b, b2 = q, 나머지 를 구하 면 q2 = b% q.
이렇게 유추 하여 끊임없이 여 유 를 구하 다.
이때 이 bn 은 처음에 a 와 b 와 동시에 최대 공약수 d 가 있다.
그리고 bn 의 최대 공약 수 는 bn 이기 때문에 bn 은 a 와 b 의 최대 공약 수 이다.
코드 는 다음 과 같 습 니 다:
교체 판
int gcd (int a, int b)
{
	while (b != 0)
	{
		int temp = a;
		a = b;
		b = temp % b;
	}
	return a;
}

귀환 판
int gcd (int a, int b)
{
	if (b == 0)
	{
		return a;
	}
	return gcd (b, a % b);
}

코드 는 참고 만 할 수 있 습 니 다. 만약 에 부족 한 점 이 있 으 면 여러분 의 지 도 를 환영 합 니 다. 저 는 반드시 개선 하고 최적화 하 겠 습 니 다.
전재 하려 면 출처 를 밝 혀 주세요.
2015.2.9 검 은 준마
데이터 구조 - 링크 의 앞 삽입 법 과 뒤 삽입 법
poj 3487 & hdu 1914 안정 적 인 결혼 문제 안정 적 인 결혼 시스템

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage