C언어 예술가

유클리드의 호제법은 쉽게 말해서 최대공약수를 구하는 알고리즘이다. A와 B의 최대공약수를 구한다면, A=QB+R 위 식처럼 A와 B의 관계를 나타내도록한다.(A>B) 이상태에서 다시 제수(B)과 나머지(R)의 관계를 같은 형식으로 나타내보자. B=Q'R+R' 나머지로 제수를 계속해서 나눠간다. 이렇게 반복하다보면 언젠가 제수가 딱 떨어지는 순간이 생기게된다. 생각해 보면 모든 수에대하여 성립한다. 이 때 떨어지는 순간 제수가 최대 공약수가 된다는 것이 호제법이다. 연습삼아 유클리드 호제법으로 최대공약수를 구해보자. *제수:나누는 수 *피제수:나눔을 당하는수 *나머지:나머지 GCD(3,6) 2 = 6/3...0 나머지가 0일때 제수가 3이므로 GCD는 3 GCD(8,28) 3 = 28 / 8...4 2 =..

유클리드의 호제법을 이용한다. 우선 증명은 생략하자. 이걸 증명하는 건 그다지 효율적이지 않는듯하다. 외우자 무조건 1. 만약 A와 B 두 수가 있다고 가정하자. 2. A와 B 중 작은수로 큰수를 나누어 몫과 나머지를 구한다. 유클리드의 호제법! A=B*Q+R A와 B의 최대공약수는 Q와 R 의 최대공약수와 같다. // 여기서 A 와 B의 최대 공약수를 구하기를 원한다면Q와 R의 최대공약수를 구하자. 위 과정을 계속 반복한다. 원을 시작점을 중심으로 반대방향으로 A와 B의 속도로 두물체가 출발하였다. 계속해서 만날것이다. 그런데 만나는 위치가 시작점이 될 때 두 물체는 몇번을 만났는가? 해법 1.두물체의 최대 공약수를 구한다. 2. A와 B의 합을 최대공약수로 나눈 수가 두 물체가 만난 횟수가된다. 위 ..