| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1997년11월02일(일) 16시06분26초 ROK 제 목(Title): Re: 프로그램 x:=X;y:=Y;u:=Y;v:=X; do the following while at least one condition holds: { if x>y then x:=x-y; v:=v+u; else if y<x then y:=y-x; u:=u+v; } print (x+y)/2; print (u+v)/2; x와 y만 주목해서 보면 바로 최대공약수를 구하는 루틴 그 자체고.. (따라서 x = y = (x+y)/2 = gcd(X, Y)) u와 v는 추측컨데 최소공배수... 돌려보니 맞는데, 증명하려니 귀찮군요. :) 그리고, u 값과 v 값이 틀리게 끝나는데, 그 평균이 최소공배수가 되다니... u, v 값의 정체는 무어죠? -- 박종대 |