다음 fib() 함수는 피보나치 수열을 계산하는 C 코드이다. fib(… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 24년 1회차
다음 fib() 함수는 피보나치 수열을 계산하는 C 코드이다. fib(17)을 실행할 때 fib(8)과 fib(10)이 각각 호출되는 횟수를 바르게 연결한 것은?fib(8) fib(10)int fib(int n){
if(n==1 || n==2) return 1;
else return (fib(n-1) + fib(n-2));
}
1
52번 13번
2
52번 21번
3
55번 13번
4
55번 21번
해설
fib(17) 실행 시 fib(8)은 55회, fib(10)은 21회 호출된다.
fib(k)를 호출하는 것은 fib(k+1)과 fib(k+2)뿐이므로, 호출 횟수를 C(k)라 하면 , 이 되어 피보나치 수열을 이룬다. 즉 이다.
- 52회·13회 조합은 두 값이 모두 틀리다. 13회는 fib(11)의 호출 횟수이다.
- 52회·21회 조합은 fib(10)은 맞지만 fib(8)을 55회가 아닌 52회로 잡아 틀리다.
- 55회·13회 조합은 fib(8)은 맞지만 13회는 fib(11)의 호출 횟수이다.
오류나 개정된 내용이 보이면 알려주세요