Problem76 100の分割数の数を求める

問題

5は数の和として6通りに書くことができる:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
2つ以上の正整数の和としての100の表し方は何通りか.

ソース

#include <string>
#include <Windows.h>

//const int TargetVal = 5;
const int TargetVal = 100;

struct JyoutaiDef
{
    int Val;
    int SumVal;
    //std::string Keiro;
};

class CStack
{
private:
    JyoutaiDef JyoutaiDefArr[100+1];
    int ArrP;
public:
    CStack(){ArrP=-1;};
    int GetCount(){return ArrP+1;};
    void Push(JyoutaiDef& pJyoutai);
    JyoutaiDef Pop();
};

void CStack::Push(JyoutaiDef& pJyoutai)
{
    const int UB = sizeof(JyoutaiDefArr)/sizeof(JyoutaiDef);
    if(ArrP+1 > UB) puts("スタックのサイズ上限を超えました");
    else JyoutaiDefArr[++ArrP] = pJyoutai;
}

JyoutaiDef CStack::Pop()
{
    return JyoutaiDefArr[ArrP--];
}

void main()
{
    CStack Stack;
    JyoutaiDef WillPush;

    for (int I = 1; I <= TargetVal/2; I++) { //和の半分までループ
        WillPush.Val = I;
        WillPush.SumVal = I;
        //char wkCharArr[100];wsprintf(wkCharArr,"%d",I);
        //WillPush.Keiro = wkCharArr;
        Stack.Push(WillPush);
    }

    int AnsCnt = 0;
    while (Stack.GetCount() > 0){
        JyoutaiDef Popped = Stack.Pop();

        if (Popped.SumVal == TargetVal) {
            AnsCnt++;
            //printf("%d個目の組み合わせ%s\n",AnsCnt, Popped.Keiro.c_str());
            if(AnsCnt % 5000000 == 0) printf("%09d個目の組み合わせを発見。\n",AnsCnt);
            continue;
        }

        for (int I = Popped.Val; I <= TargetVal - 1; I++) {
            WillPush.Val = I;
            WillPush.SumVal = Popped.SumVal + I;
            //WillPush.Keiro = Popped.Keiro + "+";
            //char wkCharArr[100];wsprintf(wkCharArr,"%d",I);
            //WillPush.Keiro += wkCharArr;

            if (WillPush.SumVal <= TargetVal) Stack.Push(WillPush);
            else break;
        }
    }
    printf("Answer=%d\n",AnsCnt);
}

実行結果

省略
150000000個目の組み合わせを発見。
155000000個目の組み合わせを発見。
160000000個目の組み合わせを発見。
165000000個目の組み合わせを発見。
170000000個目の組み合わせを発見。
175000000個目の組み合わせを発見。
180000000個目の組み合わせを発見。
185000000個目の組み合わせを発見。
190000000個目の組み合わせを発見。
Answer=190569291

解説

深さ優先探索で全探索してます。

STLのStackはDebugビルドだと遅いので、
ビルトイン配列でStackのデータ構造を実装してます。