トップページに戻る    次の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桁の数からなる唯一の順序集合の和を求めよ.


ソース

#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;
}


実行結果

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


解説

mapコンテナは便利ですね。
MSDN --- mapコンテナ