Problem15 Combinationを求める

問題

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

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

using System;

class Program
{
    //const long LenV = 2;
    const long LenV = 20;

    static void Main()
    {
        double ProdVal = 0;
        for (long I = LenV + LenV; LenV < I; I--) {
            ProdVal += Math.Log10(I);
        }
        for (long I = 1; I <= LenV; I++) {
            ProdVal -= Math.Log10(I);
        }

        Console.WriteLine("ルートは{0}通り", Math.Pow(10, ProdVal));
    }
}

ソース (Listジェネリックとマージソートもどきを使用する方法)

using System;
using System.Collections.Generic;

class Program
{
    //const long LenV = 2;
    const long LenV = 20;

    static void Main()
    {
        var ProdList = new List<long>();
        var DeviList = new List<long>();

        long ResultVal = 1;
        for (long I = LenV + LenV; LenV < I; I--) {
            ProdList.Add(I);
        }
        for (long I = 1; I <= LenV; I++) {
            DeviList.Add(I);
        }

        while (ProdList.Count != 0 && DeviList.Count != 0) {
            if (ProdList.Count != 0) {
                ResultVal *= ProdList[0];
                ProdList.RemoveAt(0);
            }
            for (int I = 0; I <= DeviList.Count - 1; I++) {
                if (ResultVal % DeviList[I] == 0) {
                    ResultVal /= DeviList[I];
                    DeviList.RemoveAt(0);
                    break;
                }
            }
        }
        Console.WriteLine("ルートは{0}通り", ResultVal);
    }
}

実行結果

ルートは137846528820通り

解説

Listジェネリックとマージソートもどきを使用する方法が分かりやすいと思います。