프로그래밍의 기초(의사 코드 트레이스)
두 정수 a, b를 뺄셈으로 같게 만들어 가는 다음 프로그램을 실행한 후의 k의 값은?
integer: a ← 48, b ← 18, k ← 0
while (a ≠ b)
if (a > b)
a ← a − b
else
b ← b − a
endif
k ← k + 1
endwhile- A3
- B4
- C6
정답과 해설 보기
정답: B. 4
큰 쪽에서 작은 쪽을 빼는 것을 둘이 같아질 때까지 반복하는, 뺄셈에 의한 유클리드 호제법입니다. (a, b)는 (48, 18) → (30, 18) → (12, 18) → (12, 6) → (6, 6)으로 바뀌고, 뺄셈은 4회이므로 k = 4입니다. 마지막의 a = b = 6이 최대공약수입니다. 나머지(mod)를 사용하는 호제법이라면 48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0의 3회로 끝납니다.