0

我正在阅读 RobetSedwick 的 C++ 书中的算法。在这里，作者正在解释河内塔使用分而治之的设计和重现。

以下代码是问题的递归解决方案。它指定在每个步骤中应该移动哪个磁盘，以及在哪个方向上（+ 表示向右移动一个钉子，当在最右边的钉子上时，循环到最左边的钉子；和 - 表示向左移动一个钉子，循环到最左边的钉子。当在最左边的钉子上时，最右边的钉子）。

Disk3          
Disk2
Disk1

Peg1      Peg2   Peg3

我的问题当磁盘位于左挂钩（即挂钩 1）上时，作者在“循环到最左边的挂钩”上方的意思是什么我们如何循环到最左边的挂钩？

作者还提到递归是基于以下思想：要将N个磁盘向右移动一个钉子，我们首先将顶部N-1个磁盘向左移动一个钉子，然后将N个磁盘向右移动一个钉子，然后移动N-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 回答