计算二项式系数C(n,k)

Binomial.cxx

#include <vector>
#include <iostream>
#include "d:/workspace/dxh/testUlt.h"
using namespace std;
 //计算二项式系数C(n,k)
int Binomial(int n, int k) {
    int result[n + 1][k + 1];
    for(int i = 0; i <= n; ++i)        //按行来填矩阵
    {
        for(int j = 0; j <= min(i, k); ++j)    // min(i,k)是这一行需要填的列数
        {
            if (j == 0 || j == i)
                result[i][j] = 1;
            else
                result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
        }
    }
    // for(int i = 0; i <= n; i++)        //按行来填矩阵
    // {
    //     for(int j = 0; j <= i; j++)        //按行来填矩阵
    //     {
    //         cout << result[i][j] << ",";
    //     }
    //     cout << endl;
    // }
    return result[n][k];
}
// Another XM
int fract(int n) {
    int ret = 1;
    while (n > 1) {
        ret *= n--;
    }
    return ret;
}
// more fast when n is bigger.
// but will over flow using math equatation n! / k! / (n-k)!..because n! may > MAX_INT
int C_N_K(int n, int k) {
    // return fract(n) / (fract(n - k) * fract(k));
    if (k == 0 || n == k)
        return 1;
    int ret = 1;
    for (int i = k + 1; i < n + 1; ++i){
        ret *= i;
    }
    return ret / fract(n - k);
}

int main()
{    
    TEST_BEGIN_N(1000)
        for(int i = 0; i <= 10; i++){
            C_N_K(10, i) ;
        }
    TEST_END_N
    TEST_BEGIN_N(1000)
        for(int i = 0; i <= 10; i++){
           Binomial(10, i) ;
        }
    TEST_END_N
    system("pause");
    return 0;
}