1

だから私は関数 moveSingleDisk() が呼び出された回数を数えたいのですが、私はそれを理解できないようです...このコードを使用して:

#include <iostream>
using namespace std;

void moveTower(int n, char start, char finish, char temp, int count);
void moveSingleDisk(char moveFrom, char moveTo, int count);
void calcHanoi(int n);

int main (int argc, const char * argv[])
{
    calcHanoi(5);
    return 0;
}

void calcHanoi(int n)
{
    int count = 0;
    moveTower(n, 'A', 'B', 'C', count);
}

void moveTower(int n, char start, char finish, char temp, int count)
{
    if (n == 1) 
    {
        count++;
        moveSingleDisk(start, finish, count);
        return;
    }
    moveTower(n-1, start, temp, finish, count);
    count++;
    moveSingleDisk(start, finish, count);
    moveTower(n-1, temp, finish, start, count);
}

void moveSingleDisk(char moveFrom, char moveTo, int count)
{
    cout << count << ": " << moveFrom << " -> " << moveTo << endl;
}

次の出力が得られます。

1: A -> B
1: A -> C
2: B -> C
1: A -> B
2: C -> A
2: C -> B
3: A -> B
1: A -> C
2: B -> C
2: B -> A
3: C -> A
2: B -> C
3: A -> B
3: A -> C
4: B -> C
1: A -> B
2: C -> A
2: C -> B
3: A -> B
2: C -> A
3: B -> C
3: B -> A
4: C -> A
2: C -> B
3: A -> B
3: A -> C
4: B -> C
3: A -> B
4: C -> A
4: C -> B
5: A -> B

私は問題を追跡しようとしましたが、再帰により、この種のものを追跡することは非常に困難になります (少なくとも私にとっては)。

どんな助けや説明も大歓迎です！ありがとうございました ：）

4

3 に答える 3

3

の count 呼び出しが必要なだけの場合moveSingleDiskは、moveSingleDisk

static int count = 0;
count++;

この例を見てください。カウンターパラメーターを渡す必要はありません

#include <iostream>

using namespace std;

int f(){
  static int i = 0;
  cout << i++;
  return i < 5 ? f() : 5;
}

int main(){
  f();
  return 0;
}
于 2012-02-17T00:05:11.960 に答える
2

値で渡しcountているため、再帰呼び出しはmoveTowerそのローカル コピーを変更しません。代わりに参照渡し:

void moveTower(int n, char start, char finish, char temp, int & count)
                                                              ^

moveSingleDisk各呼び出しの前ではなく、内部でカウンターをインクリメントする方が少しきれいかもしれないので、呼び出しを見逃すことはありません。その場合、そこでも参照渡しする必要があります。

于 2012-02-16T23:36:58.017 に答える
1

再帰的なデータ/アルゴリズムを使用すると、機能的なアプローチでコードを簡素化できます。再帰関数からカウントを返し、ネストされたレベルを「集約」します。ただし、この方法では「歩数」の表示が失われます。

int moveTower(int n, char start, char finish, char temp);
int moveSingleDisk(char moveFrom, char moveTo);
void calcHanoi(int n);

int main (int argc, const char * argv[])
{
    calcHanoi(5);
    return 0;
}

void calcHanoi(int n)
{
    int count = moveTower(n, 'A', 'B', 'C');
}

int moveTower(int n, char start, char finish, char temp)
{
    if (n == 1) 
        return moveSingleDisk(start, finish);
    return
        moveTower(n-1, start, temp, finish) +
        moveSingleDisk(start, finish) +
        moveTower(n-1, temp, finish, start);
}

int moveSingleDisk(char moveFrom, char moveTo)
{
    cout << moveFrom << " -> " << moveTo << endl;
    return 1;
}
于 2012-02-17T00:03:52.677 に答える