2

私は、再帰的な方法を使用してハノイの塔の問題を解決するように求めている本の演習に取り組んでいます。私は解決策にたどり着きましたが、インターネットを閲覧した後に収集したことから、私の解決策は正しくない可能性があるということです。問題を解決するためのより良い/別の方法を知っている人はいますか? そして、改善のための提案はありませんか。（ところで、アウトプットは正しいです。具体的にどのペグではなく、どのタワーから別のペグが動いているかを伝えることだけが想定されています）

コードは次のとおりです。

#include <iostream>
#include <cmath>

using namespace std;

static int counter = 0;

void ToH(int dskToMv, int cLocation, int tmpLocation, int fLocation)
{
if (dskToMv == 0);
else
{
    if (dskToMv%2!=0)
    {
        cout << cLocation << "->" << tmpLocation << endl;
        cout << cLocation << "->" << fLocation << endl;
        cout << tmpLocation << "->" << fLocation << endl;
        ToH(dskToMv-1, cLocation, fLocation, tmpLocation);
    }
    else if (dskToMv%2==0)
    {
        counter++;
        if (counter%2==0)
            cout << fLocation << "->" << cLocation << endl;
        else
            cout << cLocation << "->" << fLocation << endl;
        ToH(dskToMv-1, tmpLocation, cLocation, fLocation);
    }
}
}

int main()
{
int x, j;
cout << "Enter number of disks: ";
cin >> x;
j = pow(2.0, x-1)-1;
if (x%2==0)
    ToH(j, 1, 2, 3);
else
    ToH(j, 1, 3, 2);
return 0;
}

このメソッドは再帰として認定されていますか?

4

5 に答える 5

6

あなたの質問に答えるには：はい、それは再帰として認定されています。関数が自分自身を呼び出すときはいつでも、それは再帰です。

そうは言っても、コードを大幅に削減できます。

#include <iostream>

using namespace std;

void ToH(int dskToMv, int cLocation, int tmpLocation, int fLocation)
{
    if( dskToMv != 0 ) 
    {
        ToH( dskToMv-1, cLocation, fLocation, tmpLocation );
        cout << cLocation << "->" << fLocation << endl;
        ToH( dskToMv-1, tmpLocation, cLocation, fLocation );
    }
}

int main()
{
    int x;
    cout << "Enter number of disks: ";
    cin >> x;
    ToH(x, 1, 2, 3);
    return 0;
}
于 2011-07-18T21:05:47.917 に答える
0

問題を再帰的に見ると、最も簡単です。

N 個のディスクを A から B に移動するには (C を使用):

  1. if (N > 1) N-1 ディスクを A から C に移動 (B を使用)
  2. 1枚のディスクをAからBに移動
  3. if (N > 1) N-1 ディスクを C から B に移動 (A を使用)

任意のコールについて、送信元または宛先ではないペグがアンシラリーです。

実際の質問に答えるには: はい、ソリューションは再帰的に見えますが、実際には必要以上に複雑です。

于 2011-07-18T21:08:39.543 に答える
0

すべての再帰メソッドには 3 つのステップがあります

1) チェック条件 2) チェック条件成立時の戻り値。3) メソッド自体の呼び出し

@ Stargazer712 ソリューションは完璧です。

于 2011-07-18T21:18:57.173 に答える