1

再帰についてもっと理解するために、ハノイの塔の問題を実装していました。私は 3 ペグのケースを使用してそれを実装することができましたが、より多くのペグを使用したい場合 (より少ない動きを生成するため) は、私が持っているディスクの数を壊して1 つのペグに積み重ねる必要がある Frame-Stewart ソリューションを理解していますそして、元のペグからすべての中間ペグを使用して目的のペグにディスクを転送している間は、そのペグに触れないでください。しかし、関数として move(disks, 1, i, {2...K}) のようなものを記述する方法がわかりません。最初からペグの名前すら知らないのに、どうやって関数プロトタイプのすべてのペグの名前を書けばよいのでしょうか? 以下に 3 ディスク ソリューションについて考えたことを示しましたが、より一般的なケースについては助けが必要です。

// private member function: primitive/basic move of the top disk
    // from the source peg to the destination peg -- and legality-check
    void move_top_disk(int source, int dest)
    {
        cout << "Move disk " << towers[source].front() << " from Peg ";
        cout << source+1 << " to Peg " << dest+1;
        towers[dest].push_front(towers[source].front());
        towers[source].pop_front();
        if (true == is_everything_legal())
            cout << " (Legal)" << endl;
        else 
            cout << " (Illegal)" << endl;
    }

    // private member function: recursive solution to the 3 Peg Tower of Hanoi
    void move(int number_of_disks, int source, int dest, int intermediate)
    {
        if (1 == number_of_disks)
        {
            moves++;
            move_top_disk (source, dest);
        }
        else 
        {
            moves++;
            move (number_of_disks-1, source, intermediate, dest);
            move_top_disk (source, dest);
            move (number_of_disks-1, intermediate, dest, source);
        }
    }

6ペグのケースを解決するために、「移動」機能にどのような変更を加える必要があるのか​​ わかりません。ありがとう

4

1 に答える 1

2

コードの最後のブロックを変更する必要があります。移動する場所は、move-top-disk、move です。

そして、ここにNペグのハノイタワーの解決に関する記事があります：Kペグを備えたハノイの塔

于 2012-09-21T03:02:42.057 に答える