B4579 [GESP202609 四级] 新汉诺塔 题解

· · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

先看最大的盘子。它在最下面，所以要移动它，必须先把上面的小盘子全部搬走。它要落到的柱子也必须空着，否则就会把大盘压在小盘上。三个柱子只有一个可以放这些小盘子，这就帮我们确定了每一步该怎么做。

搬一整叠盘子时，需要记住两种情况。第一种是搬到沿箭头的下一根柱子，例如从 A 到 B；第二种是搬到再下一根柱子，例如从 A 到 C。三个柱子连成一个圈，从哪根出发，搬法的道理都一样。假设少一个盘子时，这两种情况分别最少需要 f 次和 g 次，接下来利用这两个答案，多算一层。

先算从 A 搬到 B。要让最大的盘子从 A 到 B，小盘子必须先从 A 搬到 C，需要 g 次。然后最大盘从 A 到 B，用 1 次。最后小盘子从 C 搬到 B，沿箭头要经过 A，也是第二种情况，需要 g 次。合起来，新答案是 g+1+g=\boxed{2g+1}。

再算题目要求的从 A 搬到 C。最大盘不能直接从 A 到 C，必须先到 B，再到 C。整个过程是：

  1. 小盘子从 A 搬到 C，需要 g 次，让最大盘能够移动。
  2. 最大盘从 A 搬到 B，用 1 次。
  3. 小盘子从 C 搬到 A，需要 f 次，让柱子 C 空出来。
  4. 最大盘从 B 搬到 C，用 1 次。
  5. 小盘子从 A 搬到 C，需要 g 次，叠在最大盘上。

把这些次数加起来，新答案就是 g+1+f+1+g=\boxed{2g+f+2}。

为什么这样得到的是最少次数？最大盘第一次移动前，小盘必须让路；最大盘最后一次移动后，小盘必须搬到它上面。这两头的工作都省不掉。最大盘如果多绕一圈，小盘还得在它的几次移动之间额外让路，却不能省掉开头和结尾的工作。所以多绕圈不会更省，按上面的步骤走就可以。

没有盘子时，不需要移动，所以开始时 f = 0、g = 0。根据这两个数，可以算出 1 个盘子的答案，再算 2 个盘子的答案，一直算到 n 个。例如，1 个盘子时是 f = 1、g = 2；2 个盘子时，g 就是 2\times2+1+2=7。

每轮都要先算好两个新答案，再一起换掉旧答案。代码用 nf、ng 暂时保存新结果，防止第二个计算不小心用了已经改过的 f。最后输出 g，因为题目要的是从 A 搬到 C。

参考代码：


for (int i = 1; i <= n; ++i) {
    // 先用小一层的答案，算出这一层的两个答案。
    long long nf = ________;
    long long ng = ________;
    f = nf;
    ________;
}