2018년 4월 15일 일요일

[binomial_coefficient] 이항계수 [C 언어]

// 이항계수
#include 

// nCr = n-1Cr-1 + n-1Cr
long long binomial_coefficient(int n, int r)
{
  if (r == 0 || r == n)
    return 1;
    
  return binomial_coefficient(n-1, r-1) + binomial_coefficient(n-1, r);
}

#define MAX_SIZE 100
// cache
long long binomial_coefficient2(int n, int r)
{
  static long long cache[MAX_SIZE][MAX_SIZE] = { 0, };
  
  if (cache[n][r]) {
    return cache[n][r];
  }
  
  if (r == 0 || r == n)
    return 1;
    
  cache[n][r] = binomial_coefficient2(n-1, r-1) + binomial_coefficient2(n-1, r);
  return cache[n][r];
}
int main(void) {
  printf("Hello World\n");
  //printf("%lld\n", binomial_coefficient(100,52)); // 5C2
  printf("%lld\n", binomial_coefficient2(100,52)); // 5C2
  return 0;
}

댓글 없음 :

댓글 쓰기