1

ハノイの塔問題に関するいくつかの議論を読みました。次のコードを使用した再帰的なソリューションを理解しています。

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if(nDisks == 1){
        cout << "Move the plate from " << source << " to " << dest << endl; 
    }
    else{
        Hanoi3(nDisks - 1, source, dest, intermed); 
        cout << "Move the plate from " << source << " to " << dest << endl; 
        Hanoi3(nDisks - 1, dest, intermed, source); 
    }
}

私が実際に行う必要があるのは、各ステップでタワーのある種の「イラスト」を出力することです。私はこれを達成するのに多くの問題を抱えています。インストラクターは、どのディスクがどのタワーにあるかを追跡するためにスタックを使用することを提案しましたが、スタック内の値を見つけて出力するには、一番上のエントリをポップして削除する必要があるため、これを出力するのに問題があります。私が正しく理解すれば、それらは失われます。

いずれにせよ、それは次のように始まるいくつかの解決策に私を導きました:

void Hanoi(int nDisks, stack<int> source, stack<int> intermed, stack<int> dest){
    if(nDisks == 1){
        dest.push(source.top()); 
        source.pop(); 
    }
    else{
        Hanoi(nDisks - 1, source, dest, intermed); 
        dest.push(source.top()); 
        source.pop(); 
        Hanoi(nDisks - 1, dest, intermed, source); 
    }
}

int main()
{

    int nDisks; 
    cout << "Enter the number of disks:    "; 
    cin >> nDisks; 

    stack<int> source, intermed, dest; 

    for(int i = nDisks; i >= 1; i--){
        source.push(i); 
    }

    Hanoi(nDisks, source, intermed, dest); 

    return 0;
}

これが間違っていることは十分承知しています。ソースにディスク番号を入力するのに適した場所がどこかわかりません。そして、毎回同じサイズのソース スタックを渡しています。誰かが私に何らかの方向性や何かを与えることができれば、それは本当に素晴らしいことです. ありがとうございました。

4

3 に答える 3

3

スタックへの参照を渡します。

stack<int>&

また、スタックではなくベクトルを使用して、タワーの現在のコンテンツを反復処理できるようにすることも検討してください。

PigBen の回答は、ディスクを中間タワーから宛先タワーに移動していないコードのバグも正しく識別します。

于 2010-12-19T02:24:38.777 に答える
1

スタックを参照して渡し、最後のステップで渡す順序を変更して、ソースを中間として使用して、intermedからdestに移動します。

void Hanoi(int nDisks, stack<int> &source, stack<int> &intermed, stack<int> &dest){
    if(nDisks == 1){
        dest.push(source.top()); 
        source.pop(); 
    }
    else{
        Hanoi(nDisks - 1, source, dest, intermed); 
        dest.push(source.top()); 
        source.pop(); 
        Hanoi(nDisks - 1, intermed, source, dest); 
    }
}

スタックを表示するには、スタックをコピーして、コピーからポップします。

于 2010-12-19T02:35:18.547 に答える
1

元のコードを検討してください。

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if(nDisks == 1){
        cout << "Move the plate from " << source << " to " << dest << endl; 
    }
    else{
        Hanoi3(nDisks - 1, source, dest, intermed); 
        cout << "Move the plate from " << source << " to " << dest << endl; 
        Hanoi3(nDisks - 1, dest, intermed, source); 
    }
}

それは正しくないので、おそらくあなたの先生が塔を提示することを提案する理由です。

お気づきのとおり、astd::stackはタワーの現在のディスクを表すために使用するのに適したコンテナですが、お気づきのとおり、aの要素をstd::stackポップせずに取得するのは完全に簡単ではありません。それらをポップして別のスタックに押し下げ、元に戻すことはできますが、一般的なケースでは非効率的であることは言うまでもなく、それは複雑でばかげています。そのため、クラスから派生しstd::stackてアクセスできるprotectedメンバー、つまり基になるコンテナがあります。c

には仮想メンバーがないstd::stackため、メンバーを作成する唯一の目的は、アクセスprotectedを少し難しくすることです。それは悪い設計上の決定だと思います。しかし、それはあなたが持っているものなので、

#include <iostream>
#include <string>
#include <stack>
#include <stddef.h>
using namespace std;

typedef ptrdiff_t   Size;
typedef Size        Index;

class IntStack
    : public stack<int>
{
public:
    Size count() const { return size(); }
    int at( Index i ) const { return c[i]; }
};

class Hanoi
{
private:
    IntStack    towers_[3];
    int         nDisks_;

public:
    Hanoi( int nDisks )
        : nDisks_( nDisks )
    {
        for( int disk = nDisks;  disk >= 1;  --disk )
        {
            towers_[0].push( disk );
        }
    }

    IntStack const& towers( Index i ) const { return towers_[i]; }
};

int main()
{
    int const   nDisksTotal = 2;

    Hanoi   puzzle( nDisksTotal );

    for( Index i = 0;  i < 3;  ++i )
    {
        IntStack const& tower   = puzzle.towers( i );
        Size const      nDisks  = tower.count();

        cout << "Tower " << i << ": ";        
        for( Index diskPos = 0;  diskPos < nDisks;  ++diskPos )
        {
            if( diskPos > 0 ) { cout << ", "; }
            cout << tower.at( diskPos );
        }
        cout << endl;
    }
}

このコードは、これらのスタックの要素にアクセスする方法を示しているだけであることに注意してください。

ディスプレイは、グラフィックなど、はるかに凝ったものにすることができます。

ソルバー関数をクラスのメンバーにすることをお勧めしますHanoi。そして、パズルの状態を表示するメンバー関数を追加します。後で、グラフィカルユーザーインターフェイスをサポートするために、それをコールバックに変換したい場合があります。

編集：うーん、別の答えがバグの「解決策」を示しているのがわかります。これにより、OPの学習経験と、タワーを表示する理由全体が削除されます。この回答は、バグが本物であることを意図的に確認するだけであり、代わりにOPが要求したもの、つまりスタックを効率的に表示する方法を示しています。

乾杯＆hth。、

于 2010-12-19T03:08:21.950 に答える