프로그래밍의 기초(의사 코드 트레이스)

÷는 나눗셈이며, 정수형 변수(인수 포함)에 대입할 때는 소수점 이하를 버린다. 다음 함수 pow를 pow(2, 10)으로 호출했을 때, pow가 호출되는 횟수(최초 호출 포함)는?

○integer: pow(integer: x, integer: n)
  if (n = 0)
    return 1
  endif
  integer: h ← pow(x, n ÷ 2)
  if (n mod 2 = 0)
    return h × h
  endif
  return h × h × x

정답과 해설 보기

정답: A. 5

pow(x, n)은 x의 n제곱을, n을 절반으로 한 pow(x, n ÷ 2)의 결과를 제곱하여 구합니다(n이 홀수이면 x를 한 번 더 곱합니다). n은 10, 5, 2, 1, 0으로 바뀌고 n = 0에서 재귀가 멈추므로, 호출되는 횟수는 5회입니다. 반환값은 2¹⁰ = 1024입니다. x × pow(x, n − 1)처럼 n을 1씩 줄이면 n = 10부터 0까지 11회 호출됩니다. n을 절반씩 줄이면 호출 횟수는 대략 log₂ n에 비례합니다.

÷는 나눗셈이며, 정수형 변수(인수 포함)에 대입할 때는 소수점 이하를 버린다. 다음 함수 pow를 pow(2, 10)으로 호출했을 때, pow가 호출되는 횟수(최초 호출 포함)는?

프로그래밍의 기초(의사 코드 트레이스)의 다른 문제