三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり,
それぞれ以下の式で生成される.
三角数 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));
}
}