トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

Problem61 多角数の順序集合の和

問題

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり,
それぞれ以下の式で生成される.

三角数 Pn = n(n+1)/2   1, 3,  6, 10, 15, ...
四角数 Pn = n*n2       1, 4,  9, 16, 25, ...
五角数 Pn = n(3n-1)/2  1, 5, 12, 22, 35, ...
六角数 Pn = n(2n-1)    1, 6, 15, 28, 45, ...
七角数 Pn = n(5n-3)/2  1, 7, 18, 34, 55, ...
八角数 Pn = n(3n-2)    1, 8, 21, 40, 65, ...

3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.
 1  この集合は巡回的である. 最後の数も含めて, 各数の末尾2桁は次の数の先頭2桁と一致する
 2  それぞれ多角数である: 三角数8128,四角数8281,五角数2882が
                          それぞれ別の数字で集合に含まれている
 3  4桁の数の組で上の2つの性質をもつはこの組だけである.

三角数, 四角数, 五角数, 六角数, 七角数, 八角数が
全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.


ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    //const int NeedsKakusuuCnt = 3;
    const int NeedsKakusuuCnt = 6;

    struct JyoutaiDef
    {
        internal List<int> KakusuuList; //訪問済の角数のList
        internal List<int> ValList;     //訪問済の多角数値のList
    }

    static Dictionary<int, List<int>> TakakusuuDict = new Dictionary<int, List<int>>();

    static void Main()
    {
        CalcTakakusuu();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        foreach (int Each in TakakusuuDict[3]) {
            WillPush.KakusuuList = new List<int>() { 3 };
            WillPush.ValList = new List<int>() { Each };
            Stk.Push(WillPush);
        }

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (Popped.KakusuuList.Count == NeedsKakusuuCnt) {
                for (int I = 0; I <= Popped.KakusuuList.Count - 1; I++) {
                    Console.Write("{0}角数の{1},", Popped.KakusuuList[I], Popped.ValList[I]);
                }
                Console.WriteLine();
                Console.WriteLine("合計={0}", Popped.ValList.Sum());
                continue;
            }

            for (int I = 3; I <= 8; I++) {
                if (Popped.KakusuuList.Contains(I)) continue;

                foreach (int Each in TakakusuuDict[I]) {
                    int ValsCnt = Popped.ValList.Count;
                    int LastVal = Popped.ValList[ValsCnt - 1];

                    Func<int, int, bool> IsJyunkai = (pMatubi2, pSentou2) =>
                    {
                        return pMatubi2 % 100 == pSentou2 / 100;
                    };

                    if (IsJyunkai(LastVal, Each) == false) continue;
                    if (ValsCnt == NeedsKakusuuCnt - 1 && IsJyunkai(Each, Popped.ValList[0]) == false)
                        continue;

                    WillPush.KakusuuList = new List<int>(Popped.KakusuuList) { I };
                    WillPush.ValList = new List<int>(Popped.ValList) { Each };
                    Stk.Push(WillPush);
                }
            }
        }
    }

    static void CalcTakakusuu()
    {
        Action<List<int>, Func<int, int>> wkAct = (pList, pFunc) =>
        {
            int N = 1, Result;
            do {
                Result = pFunc(N++);
                if (1000 <= Result && Result <= 9999) {
                    pList.Add(Result);
                }
            } while (Result <= 9999);
        };
        for (int I = 3; I <= 8; I++) TakakusuuDict[I] = new List<int>();

        wkAct(TakakusuuDict[3], N => N * (N + 1) / 2);
        wkAct(TakakusuuDict[4], N => N * N);
        wkAct(TakakusuuDict[5], N => N * (3 * N - 1) / 2);
        wkAct(TakakusuuDict[6], N => N * (2 * N - 1));
        wkAct(TakakusuuDict[7], N => N * (5 * N - 3) / 2);
        wkAct(TakakusuuDict[8], N => N * (3 * N - 2));
    }
}


実行結果

3角数の8256,4角数の5625,7角数の2512,8角数の1281,6角数の8128,5角数の2882,
合計=28684


解説

FuncデリゲートとActionデリゲートは便利ですね。