유클리드 알고리즘 (뒤 집기 알고리즘: 최대 공약수 알고리즘)
1847 단어 알고리즘
유클리드
증명: a 는 a = kb + r 로 표시 할 수 있 으 며, r = a mod b
d 가 a, b 의 공약수 라 고 가정 하면
a % d == 0 , b% d = = 0, r = a - kb, 그러므로 r% d = = 0
따라서 d 는 (b, a mod b) 의 공약수 이다.
d 가 (b, a mod b) 의 공약수 라 고 가정 하면
b % d == 0 , r % d == 0 ，하지만 a = kb + r 그래서 a% d = = 0
그래서 d 도 (a, b) 의 공약수 이다.
따라서 (a, b) 와 (b, a mod b) 의 공약수 가 같 고 그 최대 공약수 도 반드시 같 으 며 증 거 를 얻 을 수 있다.
유클리드 알고리즘 은 바로 이 원리 에 근거 하여 만 든 것 이다.
/*==================================================*\
| GCD
\*==================================================*/
int gcd(int x, int y)
{
if (!x || !y) return x > y ? x : y;
for (int t; t = x % y; x = y, y = t);
return y;
}}
/*==================================================*\
| GCD
\*==================================================*/
int kgcd(int a, int b)
{
if (a == 0) return b;
if (b == 0) return a;
if (!(a & 1) && !(b & 1))
return kgcd(a>>1, b>>1) << 1;
else if (!(b & 1))
return kgcd(a, b>>1);
else if (!(a & 1))
return kgcd(a>>1, b);
else return
kgcd(abs(a - b), min(a, b));
}
/*==================================================*\
| GCD
| x, y gcd(a, b) = a * x + b * y;
\*==================================================*/
int extgcd(int a, int b, int & x, int & y)
{
if (b == 0)
{
x=1; y=0;
return a;
}
int d = extgcd(b, a % b, x, y);
int t = x; x = y; y = t - a / b * y;
return d;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
