'Extended Euclid'에 해당되는 글 2건
2011/01/25 00:07
Linear Diophantine Equation (디오판토스 방정식) 푸는 방법에 관한 괜찮은 자료를 찾아서 한번 읽어봤다..
관련자료:
간단히 예를 들어보자..
을 만족하는 integer x, y 를 구하고 싶다면..
일단 GCD(3, 4) = 1 이므로 우선 다음 식을 풀어야한다..
Extended Euclid 에 의해서 x = -1, y = 1 을 구했다..
자, 이제 원래 식으로 환원하면.. x = -43, y = 43 이 나온다..
따라서 위 식을 만족하는 모든 integer (x, y) 는
즉,
(-43, 43),
(-39, 40),
(-35, 37),
...
...
이렇게 구할 수 있다.. ㅎㅎ
근데.. ax+ by = c 에서 x, y 를 구하는 법은 이해했는데..
ax - by = c 인 경우에는 어떻게 구하면 될까..???? -_-;
관련자료:
Introduction to Diophantine Equations.pdf간단히 예를 들어보자..
3x + 4y = 43
을 만족하는 integer x, y 를 구하고 싶다면..
일단 GCD(3, 4) = 1 이므로 우선 다음 식을 풀어야한다..
3x + 4y = 1
Extended Euclid 에 의해서 x = -1, y = 1 을 구했다..
자, 이제 원래 식으로 환원하면.. x = -43, y = 43 이 나온다..
따라서 위 식을 만족하는 모든 integer (x, y) 는
x = -43 + 4k,
y = 43 - 3k
(k = 임의의 정수)
y = 43 - 3k
(k = 임의의 정수)
즉,
(-43, 43),
(-39, 40),
(-35, 37),
...
...
이렇게 구할 수 있다.. ㅎㅎ
근데.. ax+ by = c 에서 x, y 를 구하는 법은 이해했는데..
ax - by = c 인 경우에는 어떻게 구하면 될까..???? -_-;
'Problem Solving > Algorithm notes' 카테고리의 다른 글
| Gaussian Prime (0) | 2011/04/03 |
|---|---|
| Floating point number 연산시 Epsilon을 더하는(또는 빼는) 이유.. (0) | 2011/03/02 |
| Linear Diophantine Equation (0) | 2011/01/25 |
| 점과 선분과의 거리 (0) | 2011/01/22 |
| Articulation Points (0) | 2010/11/21 |
| Konig's Theorem (0) | 2010/08/01 |
Trackback Address :: http://helloneo.pe.kr/trackback/397
