c++ - プログラムがクラッシュする、ツリーが大きすぎる

Question

私は演習としてこの問題に答えようとしています:

ここに{50,25,10,5,1}セントのコインが箱に入っています.コインをグループ化して1ドルを生み出す方法の数を見つけるプログラムを書いてください.

私の解決策は、各エッジが上記の値のいずれかを持つツリーを作成することです。各ノードは、コインの合計を保持します。次に、このツリーにデータを入力し、合計が 100 になる葉を探すことができます。コードは次のとおりです。

class TrieNode
{
public:
    TrieNode(TrieNode* Parent=NULL,int sum=0,TrieNode* FirstChild=NULL,int children=0, bool key =false )
        :pParent(Parent),pChild(FirstChild),isKey(key),Sum(sum),NoChildren(children)
    {
        if(Sum==100)
            isKey=true;
    }
    void SetChildren(int children)
    {
        pChild = new TrieNode[children]();
        NoChildren=children;
    }
    ~TrieNode(void);

    //pointers
    TrieNode* pParent;
    TrieNode* pChild;

    int NoChildren;

    bool isKey;
    int Sum;
};

void Populate(TrieNode* Root, int coins[],int size)
{
    //Set children
    Root->SetChildren(size);

    //add children
    for(int i=0;i<size;i++)
    {
        TrieNode* child  = &Root->pChild[0];
        int c = Root->Sum+coins[i];
        if(c<=100)
        {
            child = new TrieNode(Root,c);

            if(!child->isKey) //recursively populate if not a key
                Populate(child,coins,size);
        }
        else 
            child = NULL;
    }
}

int getNumKeys(TrieNode* Root)
{
    int keys=0;

    if(Root == NULL)
        return 0;

    //increment keys if this is a key
    if(Root->isKey)
        keys++;

    for(int i=0; i<Root->NoChildren;i++)
    {
        keys+= getNumKeys(&Root->pChild[i]);
    }

    return keys;
}

int _tmain(int argc, _TCHAR* argv[])
{
    TrieNode* RootNode = new TrieNode(NULL,0);
    int coins[] = {50,25,10,5,1};
    int size = 5;

    Populate(RootNode,coins,size);
    int combos =  getNumKeys(RootNode);

    printf("%i",combos);

    return 0;
}

問題は、ツリーが非常に巨大であるため、数秒後にプログラムがクラッシュすることです。私はこれをWindows 7、クアッドコア、8GB RAMで実行しています。大まかな計算では、十分なメモリが必要であることがわかります。

私の計算は間違っていますか？アクセスできるメモリの量は OS によって制限されますか? このソリューションを使用している間に修正できますか?

すべてのフィードバックをお待ちしております。ありがとう。

Edit1: 上記のアプローチが間違っていることを確認しました。たった1コインのセットでツリーを構築しようとすることによって。コイン[] = {1};

アルゴリズムがまだ失敗していることがわかりました。Lenik と João Menighin からの投稿を読んだ後、両方のアイデアを結び付けて、任意のサイズの配列を取る再帰的なソリューションを作成するこのソリューションを思いつきました

//N is the total the coins have to amount to
int getComobs(int coins[], int size,int N)
{
    //write base cases
    //if array empty | coin value is zero or N is zero
    if(size==0 || coins[0]==0 ||N==0)
        return 0;


    int thisCoin = coins[0];
    int atMost = N / thisCoin ;

    //if only 1 coin denomination
    if(size==1)
    {
        //if all coins fit in N
        if(N%thisCoin==0)
            return 1;
        else
            return 0;
    }


    int combos =0;
    //write recursion
    for(int denomination =0; denomination<atMost;denomination++)
    {
        coins++;//reduce array ptr

        combos+= getComobs(coins, size-1,N-denomination*thisCoin);

        coins--;//increment array ptr
    }

    return combos;
}

すべてのフィードバックに感謝します

score 3 · Accepted Answer

ツリーのソリューションは、この問題に対して完全に間違っています。これは、10e6 のトラを捕まえて、1 頭のトラが必要だからという理由だけで、1 頭を除いてすべて手放すようなものです。非常に時間とメモリを消費します -- ノードの 99.999% は役に立たないため、最初から無視する必要があります。

別のアプローチは次のとおりです。

2 つを超える 50 セントを含む 1 ドルを作ることはできないことに注意してください
25 セント硬貨を 4 枚以上入れて 1 ドルを稼ぐことはできません。
気がつけば…（わかった？）

次に、ソリューションは簡単です。

for( int fifty=0; fifty<3; fifty++) {
    for( int quarters=0; quarters<5; quarters++) {
        for( int dimes=0; dimes<11; dimes++) {
            for( int nickels=0; nickels<21; nickels++) {
                int sum = fifty * 50 + quarters * 25 + dimes * 10 + nickels * 5;
                if( sum <= 100 ) counter++;  // here's a combination!!
            }
        }
    }
}

なぜ私は 1 セント硬貨について何もしなかったのですか? 答えは簡単ですsum。が 100 未満になると、残りは 1 セントで埋められます。

ps。この解決策が単純すぎないことを願っています =)

score 2 · Accepted Answer

わかりました、これは完全な答えではありませんが、あなたを助けるかもしれません。健全性チェック（私が呼んでいるもの）を実行してみることができます。作成されたすべてのノードにstaticカウンターを配置しTrieNode、それがどれだけ大きくなるかを確認します。あなたがいくつかの計算をしたならば、あなたはそれがいくつかの異常な値に行くかどうかを知ることができるはずです。

システムは使用可能なメモリを制限できますが、それは本当に奇妙なことです。通常、ユーザー/管理者はいくつかの目的のためにそのような制限を設定できます。これは、専用のマルチユーザーシステムでよく発生します。他のことは、64ビットWindows環境で32ビットアプリを使用している可能性があります。その場合、memの制限は4GBになりますが、これも非常に奇妙です。ここでは、OSによる制限が問題になるとは思いません。

ちなみに。このコードですべてのオブジェクト指向プログラミングの概念をやや打ち負かしたことをご理解いただければ幸いです:)。

score 1 · Accepted Answer

解決策を見つけるためのはるかに簡単な方法があります：

#include <iostream>
#include <cstring>
using namespace std;
int main() {
    int w[101];
    memset(w, 0, sizeof(w));
    w[0] = 1;
    int d[] = {1, 5, 10, 25, 50};
    for (int i = 0 ; i != 5 ; i++) {
        for (int k = d[i] ; k <= 100 ; k++) {
            w[k] += w[k-d[i]];
        }
    }
    cout << w[100] << endl;
    return 0;
}

（ideoneへのリンク）

アイデアは、徐々に大きな額面でコインを追加することによって、変更を加えるためのいくつかの方法を段階的に構築することです。外側のループの各反復は、すでに得られた結果を通過し、新しく追加されたコインを使用して構築できる金額ごとに、現在のコインの値だけ小さい組み合わせを構築できる方法の数が追加されます。たとえば、現在のコインが5で、現在の金額が7である場合、アルゴリズムは構築可能なウェイの数を検索し、2それを構築可能なウェイの数に追加します7。現在のコインが25であり、現在の金額が73である場合、アルゴリズムは、以前に見つかった構築方法の数に対して、構築する方法の数48（）を検索します。73-2573。結局、の数字はw[100]1ドルを稼ぐ方法の数（292通り）を表しています。

score 1 · Accepted Answer

あなたのコードを分析するにはもっと時間が必要ですが、今のところ、これは古典的な動的プログラミングの問題であると言えます。ここでいくつかの興味深いテキストを見つけることができます:

http://www.algorithmist.com/index.php/Coin_Change

そしてここ

http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf

score 1 · Accepted Answer

私は本当に誰かが最も効率的でシンプルな可能な実装をしなければならないと信じています、それは lenik の答えの改善です :メモリ:
定数<-よくわからない

for(int fifty=0; fifty <= 100; fifty+=50)
    for(int quarters=0; quarters <= (100 - fifty); quarters+=25)
        for(int dimes=0; dimes <= (100 - fifty - quarters); dimes+=10)
            counter += 1 + (100 - fifty - quarters - dimes)/5;

これは定数時間で解けると思います。これは、任意の数列の和を線形式で表すことができるからです。

score 0 · Accepted Answer

問題は無限再帰かもしれません。どこでも c をインクリメントしておらず、ループは c<=100 で実行されます

編集1：かどうかはわかりません

int c = Root->Sum+coins[i];

実際には 100 を超えています。確認してください。

編集 2: Sum が正しく初期化されていなかったので、以下のコメントで修正されました。

編集 3: デバッグ方法- もう 1 つできることは、このツリーの印刷関数を作成するか、既存のコードの奥深くに進むにつれて各レベルで印刷することです。合計 10 回の反復後にループを終了するカウンターを追加します。プリントは、ガベージ値を取得しているか、c が正しい方向に徐々に増加しているかを示します。

c++ - プログラムがクラッシュする、ツリーが大きすぎる

6 に答える 6

Related

Reference