Back-End/Algorithm
Binomial Coefficient (recursive)
무지맘
2023. 3. 7. 00:46
1. Problem
- nCk를 계산해보자.
2. Input
1) 음이 아닌 정수 n
2) 음이 아닌 정수 k
- 이때 k <= n
3. Output
1) nCk의 값
- C는 수학에서 조합을 나타내는 기호로, nCk는 n!/(k!(n-k)!)으로 계산된다.
4. PseudoCode
int bin(int n, int k){
if(k==0 || n==k)
return 1;
else
return bin(n-1, k-1) + bin(n-1, k);
}
5. Example
class AlgoTest {
public static void main(String[] args){
System.out.println(bin(5,3)); // 10
}
static long bin(int n, int k) {
if(k==0 || n==k)
return 1;
else
return bin(n-1, k-1) + bin(n-1, k);
}
}
- T(n) = 2^n -1