Wednesday, June 13, 2012

Binomial Coefficients - Part 1

Implementation 1:
int factorial(int n){
 if (n <= 0) return 1;
    int f = 1;
    do { f *= n;} while (--n);
    return f;
}

int C(int n, int k){
    if (n < k) return 0;
    return fact(n)/(fact(k)*fact(n-k));
}
It works for n <= 12.

Implementation 2:

int C(int n, int k){
    if (n < k) return 0;
    if (k > n/2) k = n - k;
    int c = 1;
    for (int i = 1; i <= k; i++) c = (c*(n-i+1))/i; 
    return c;
}
It works for n <= 29.

The important thing to note here is that, because of the way the loop is written, the division never results in a non-integer. (Why? Think about it!)

No comments:

Post a Comment