프로그래밍의 기초(의사 코드 트레이스)
다음 함수 c를 c(4, 2)로 호출했을 때, c가 호출되는 횟수(최초 호출 포함)는?
○integer: c(integer: n, integer: k)
if (k = 0 or k = n)
return 1
endif
return c(n − 1, k − 1) + c(n − 1, k)- A5
- B6
- C11
정답과 해설 보기
정답: C. 11
c(n, k)는 n개에서 k개를 고르는 조합의 수(이항 계수)를 파스칼의 삼각형 관계로 구합니다. c(4, 2)는 c(3, 1)과 c(3, 2)를 호출하고, 각각이 다시 c(2, 0)과 c(2, 1), c(2, 1)과 c(2, 2)를 호출하며, 2번 나타나는 c(2, 1)은 둘 다 c(1, 0)과 c(1, 1)을 호출합니다. 1을 반환하는 호출이 6회, 두 호출을 수행하는 호출이 5회로 합계 11회입니다. 반환값은 6이며, 1을 반환하는 호출의 횟수와 일치합니다.