我正在阅读RbESESEDWICK的C++书中的算法。本文运用分而治之的设计方法和递推法对河内城楼进行了详细的阐述。
下面的代码是这个问题的递归解决方案它指定每一步应移动哪个磁盘,以及移动的方向(+表示向右移动一个钉,在最右边的钉上时循环到最左边的钉;和-表示向左移动一个钉,在最左边的钉上时循环到最右边的钉)。
Disk3
Disk2
Disk1
Peg1 Peg2 Peg3
我的问题在上面作者所说的“循环到最左边的peg”是什么意思,当圆盘在左边的peg(即peg 1)上时,我们如何循环到最左边的peg?
作者还提到递归是基于以下思想的:要将n个磁盘向右移动一个钉,我们首先将顶部的n-1个磁盘向左移动一个钉,然后将顶部的n-1个磁盘向右移动一个钉,然后再将n-1个磁盘向左移动一个钉(在磁盘n上)。
我对上面的左右术语感到困惑。谁能解释一下吗?
void hanoi(int N, int d)
{
if (N == 0) return;
hanoi(N-1, -d);
shift(N, d);
hanoi(N-1, -d);
}
最佳答案
意思是:
右转:
peg1 -> peg2
peg2 -> peg3
peg3 -> peg1
向左骑自行车
peg1 -> peg3
peg2 -> peg1
peg3 -> peg2