【ProjectEuler】ProjectEuler_053(1≦n≦100に対して、C(n,r)はどのくらい100万を超えていますか?)

// Combinatoric selections
//     Problem 53
//     There are exactly ten ways of selecting three from five, 12345:
//
// 123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
//
//     In combinatorics, we use the notation, 5C3 = 10.
//
//     In general,
//
//     nCr = n! / r!(n-r)!
//     ,where r  n, n! = n(n1)...321, and 0! = 1.
//     It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.
//
//     How many, not necessarily distinct, values of  nCr, for 1  n  100, are greater than one-million?
//
//   53:  1≤n≤100，C(n,r)     100 ？
//     12345             :
//
//      123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
//
//                   5C3 = 10   .
//
//              ：
//
//          nCr = n! / r!(n-r)!
//          ,  r  n, n! = n(n1)...321,   0! = 1.
//          n = 23             : 23C10 = 1144066.
//
//            nCr,  1 <= n <= 100，     100   ？       。
//

#include 
#include 
#include 
#include 

#include 

using namespace std;

//          
class DetailPrinter
{
public:
    void Start();
    void End();
    DetailPrinter();

private:
    LARGE_INTEGER timeStart;
    LARGE_INTEGER timeEnd;
    LARGE_INTEGER freq;
};

DetailPrinter::DetailPrinter()
{
    QueryPerformanceFrequency(&freq);
}

//************************************
// Method:    Start
// Access:    public
// Describe:           
// Returns:   void
//************************************
void DetailPrinter::Start()
{
    QueryPerformanceCounter(&timeStart);
}

//************************************
// Method:    End
// Access:    public
// Describe:           
// Returns:   void
//************************************
void DetailPrinter::End()
{
    QueryPerformanceCounter(&timeEnd);
    cout << "Total Milliseconds is " << (double)(timeEnd.QuadPart - timeStart.QuadPart) * 1000 / freq.QuadPart << endl;

    const char BEEP_CHAR = '\007';

    cout << endl << "By GodMoon" << endl << __TIMESTAMP__ << BEEP_CHAR << endl;

    system("pause");
}

/*************************    *********************************/

/*
 *         ，           1000000，               。
 */
 
//***********************************
// Method:    CombinationDouble
// Access:    public 
// Describe:      ，    double  
// Parameter: UINT32 n
// Parameter: UINT32 r
// Returns:   double
//************************************
double CombinationDouble(UINT32 n, UINT32 r)
{
    // C(n,r)=n!/r!/(n-r)!=(r+1)*(r+2)*...*n/1/2/.../(n-r)
    double result=1;

    for (UINT32 i=r+1;i<=n;++i)
    {
        result*=i;
    }

    UINT32 d=n-r;
    for (UINT32 i=2;i<=d;++i)
    {
        result/=i;
    }

    return result;
}

void TestFun1()
{

    cout << "TestFun1 OK!" << endl;
}

void F1()
{
    cout << "void F1()" << endl;

    // TestFun1();

    DetailPrinter detailPrinter;
    detailPrinter.Start();

    /*********************************    *******************************/
    const UINT32 BEGIN_NUM = 1;
    const UINT32 END_NUM = 100;

    const UINT32 LIMIT_NUM = 1000000;

    UINT32 count = 0;
    UINT32 r;

    for(UINT32 n = BEGIN_NUM; n <= END_NUM; ++n)
    {
        for(r = BEGIN_NUM; r <= n; ++r)
        {
            if(CombinationDouble(n, r) >= LIMIT_NUM)
            {
                ++count;
            }
        }
    }

    cout << "n   [" << BEGIN_NUM << "," << END_NUM << "]，C(n,r)  " << LIMIT_NUM << "     " << count << " " << endl;

    /*********************************    *******************************/

    detailPrinter.End();
}

//   
int main()
{
    F1();
    return 0;
}

/*
void F1()
n   [1,100]，C(n,r)  1000000     4075 
Total Milliseconds is 13.93

By GodMoon
Fri Apr  5 11:28:00 2013
*/