calculate() 함수의 기능을 표현하는 수식으로 옳은 것은? (단… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 15년 1회차
calculate() 함수의 기능을 표현하는 수식으로 옳은 것은? (단, n은 양수만을 허용한다)
double calculate(float x, int n)
{
double t;
if (n < 0) exit(1);
if (n == 0) return 1.0;
else if (n % 2 == 0) {
t = calculate(x, n / 2);
return t * t;
}
else
return x * calculate(x, n - 1);
}
1
xlog⁡2nx\log_2 n
2
xlog⁡2nx^{\log_2 n}
3
xnxn
4
xnx^n
해설

calculate(x, n)은 xnx^n을 계산한다.

n이 0이면 1, 짝수이면 (xn/2)2(x^{n/2})^2, 홀수이면 x⋅xn−1x \cdot x^{n-1}을 반환하는 분할 정복 거듭제곱이다.

예를 들어 n = 5이면 x⋅(x2)2=x5x \cdot (x^2)^2 = x^5이다.

  • xlog⁡2nx\log_2 n: 재귀 호출 횟수가 로그에 비례할 뿐, 반환값은 곱셈의 누적이다.
  • xlog⁡2nx^{\log_2 n}: 절반 지수의 결과를 다시 제곱하므로 지수가 줄지 않고 n이 된다.
  • xnxn: x를 n회 더하는 것이 아니라 곱한다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 15년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기