0

RobetSedwick による C++ の本でアルゴリズムを読んでいます。ここで筆者はハノイの塔について、分割統治法と再帰性を用いて説明しています。

次のコードは、問題に対する再帰的な解決策です。各ステップでどのディスクをシフトするか、どの方向に移動するかを指定します (+ はペグを 1 つ右に移動し、一番右のペグにある場合は一番左のペグに循環することを意味し、- はペグを 1 つ左に移動し、ペグを左に循環することを意味します)。一番左のペグの場合は一番右のペグ)。

Disk3          
Disk2
Disk1

Peg1      Peg2   Peg3

私の質問は、ディスクが左のペグ (つまり、ペグ 1) にある場合、「左端のペグへのサイクリング」の上で著者が何を意味するかです。

著者はまた、再帰は次のアイデアに基づいていると述べました。ディスクをもう 1 つ左に (ディスク N に) ペグします。

上記の左右の用語で混乱しています。誰でも説明してください。

void hanoi(int N, int d)
  {
    if (N == 0) return;
    hanoi(N-1, -d);
    shift(N, d);    
    hanoi(N-1, -d);
  }
4

1 に答える 1

2

それは単に意味します：

右へのサイクリング:

peg1 -> peg2
peg2 -> peg3
peg3 -> peg1

左へサイクリング

peg1 -> peg3
peg2 -> peg1
peg3 -> peg2
于 2012-09-07T12:01:18.880 に答える