三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり,
それぞれ以下の式で生成される.
三角数 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桁の数からなる唯一の順序集合の和を求めよ.
#include <Windows.h>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
#include <numeric>
struct JyoutaiDef
{
std::vector<int> KakusuuVect;//訪問済の角数のVect
std::vector<int> ValVect;//訪問済の多角数値のVect
};
std::vector<int> CalcTakakusuu(int pKakusuu);
bool IsJyunkai(int pMatubi2,int pSentou2);
std::map<int,std::vector<int> > TakakusuuMap;
void main()
{
const int NeedsKakusuuCnt = 6;
for (int I = 3; I <= 8; I++) TakakusuuMap[I] = CalcTakakusuu(I);
std::stack<JyoutaiDef> stk;
JyoutaiDef WillPush;
for (std::vector<int>::iterator it = TakakusuuMap[3].begin(); it !=TakakusuuMap[3].end();it++){
WillPush.KakusuuVect = std::vector<int>(1,3);
WillPush.ValVect = std::vector<int>(1,*it);
stk.push(WillPush);
}
while (stk.empty() == false) {
JyoutaiDef Popped = stk.top(); stk.pop();
if (Popped.KakusuuVect.size() == NeedsKakusuuCnt) {
std::string WillOut = "Answer\n";
char wkCharArr[99];
for (int I = 0; I <= (int)Popped.KakusuuVect.size() - 1; I++) {
wsprintf(wkCharArr,"%d角数の%d,",Popped.KakusuuVect.at(I), Popped.ValVect.at(I));
WillOut += wkCharArr;
}
wsprintf(wkCharArr,"\n合計=%d",std::accumulate(Popped.ValVect.begin(),Popped.ValVect.end(),0));
WillOut += wkCharArr;
puts(WillOut.c_str());
continue;
}
for (int I = 3; I <= 8; I++) {
if (std::find(Popped.KakusuuVect.begin(),Popped.KakusuuVect.end(),I) != Popped.KakusuuVect.end())
continue;
for (std::vector<int>::iterator it = TakakusuuMap[I].begin(); it !=TakakusuuMap[I].end();it++){
int ValsCnt = Popped.ValVect.size();
int LastVal = Popped.ValVect.at(ValsCnt-1);
if (IsJyunkai(LastVal, *it) == false) continue;
if (ValsCnt == NeedsKakusuuCnt - 1 && IsJyunkai(*it, Popped.ValVect.at(0)) == false)
continue;
WillPush.KakusuuVect = Popped.KakusuuVect;
WillPush.KakusuuVect.push_back(I);
WillPush.ValVect = Popped.ValVect;
WillPush.ValVect.push_back(*it);
stk.push(WillPush);
}
}
}
}
std::vector<int> CalcTakakusuu(int pKakusuu)
{
std::vector<int> WillReturn;
int N=1,Result;
do {
if (pKakusuu==3) Result = N * (N + 1) / 2;
if (pKakusuu==4) Result = N * N;
if (pKakusuu==5) Result = N * (3 * N - 1) / 2;
if (pKakusuu==6) Result = N * (2 * N - 1);
if (pKakusuu==7) Result = N * (5 * N - 3) / 2;
if (pKakusuu==8) Result = N * (3 * N - 2);
if (1000 <= Result && Result <= 9999) WillReturn.push_back(Result);
N++;
}while (Result <= 9999);
return WillReturn;
}
bool IsJyunkai(int pMatubi2,int pSentou2)
{
return pMatubi2 % 100 == pSentou2 / 100;
}