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
2
3
4
해설
calculate(x, n)은 을 계산한다.
n이 0이면 1, 짝수이면 , 홀수이면 을 반환하는 분할 정복 거듭제곱이다.
예를 들어 n = 5이면 이다.
- : 재귀 호출 횟수가 로그에 비례할 뿐, 반환값은 곱셈의 누적이다.
- : 절반 지수의 결과를 다시 제곱하므로 지수가 줄지 않고 n이 된다.
- : x를 n회 더하는 것이 아니라 곱한다.
오류나 개정된 내용이 보이면 알려주세요