Problem15 Combinationを求める

問題

2×2のマス目の左上からスタートした場合、引き返しなしで右下にいくルートは6つある。
では、20×20のマス目ではいくつのルートがあるか。

ソース (対数を使用する方法)

#include <stdio.h>
#include <math.h>

void main()
{
    //const __int64 LenV = 2;
    const __int64 LenV = 20;
    double ProdVal = 0;

    for (double I = LenV*2; LenV < I; I--) {
        ProdVal += log10(I);
    }
    for (double I = 1; I<=LenV ; I++) {
        ProdVal -= log10(I);
    }

    __int64 Answer = (__int64)(pow(10,ProdVal)+0.5L);
    printf("ルートは%I64d通り\n",(__int64)Answer);
}

ソース (Vectorとマージソートもどきを使用する方法)

#include <stdio.h>
#include <vector>

void main()
{
    std::vector<__int64> ProdVect;
    std::vector<__int64> DeviVect;

    //const __int64 LenV = 2;
    const __int64 LenV = 20;
    __int64 ResultVal = 1;
    for(__int64 I = LenV*2; LenV < I; I--) ProdVect.push_back(I);
    for(__int64 I = 1; I <= LenV; I++) DeviVect.push_back(I);

    while (ProdVect.size() != 0 && DeviVect.size() != 0) {
        if (ProdVect.size() != 0) {
            ResultVal *= ProdVect.at(0);
            ProdVect.erase(ProdVect.begin());
        }
        for (int I = 0; I <= (int)DeviVect.size() - 1; I++) {
            if (ResultVal % DeviVect.at(I) == 0) {
                ResultVal /= DeviVect.at(I);
                DeviVect.erase(DeviVect.begin());
                break;
            }
        }
    }
    printf("ルートは%I64d通り\n",ResultVal);
}

実行結果

ルートは137846528820通り

解説

対数を使う方法のほうが行数は短いですが、
Vectorとマージソートもどきを使用する方法のほうが分かりやすいと思います。

MSDN --- log、logf、log10、log10f