Strange Towers of Hanoi

Description

Charlie Darkbrown sits in another one of those boring Computer Science lessons: At the moment the teacher just explains the standard Tower of Hanoi problem, which bores Charlie to death!

查理·达克布朗又坐在另一节枯燥的计算机科学课上：此刻老师正在讲解经典的汉诺塔问题，这让他感到无比厌烦！

The teacher points to the blackboard (Fig. 4) and says: “So here is the problem:

• There are three towers: A, B and C.
• There aredisks. The numberis constant while working the puzzle.
• All disks are different in size.
• The disks are initially stacked on tower A increasing in size from the top to the bottom.
• The goal of the puzzle is to transfer all of the disks from tower A to tower C.
• One disk at a time can be moved from the top of a tower either to an empty tower or to a tower with a larger disk on the top.

老师指着黑板（图 4）说道：” 问题如下：

• 有三座塔，分别是 A、B 和 C。
• 共有个圆盘，且在解决这个谜题的过程中的值保持不变。
• 所有圆盘的尺寸各不相同，
• 圆盘最初都按从上到下尺寸由小到大的顺序堆放在 A 塔上。
• 目标是将所有圆盘从 A 塔转移到 C 塔上。
• 每次只能移动一个圆盘，且只能将其从某座塔的顶端移到另一座空塔上，或者移到顶端有更大圆盘的塔上。”

So your task is to write a program that calculates the smallest number of disk moves necessary to move all the disks from tower A to C.”

因此，你的任务就是编写一个程序，计算出将所有磁盘从塔 A 移动到塔 C 所需的最少操作次数。

Charlie: “This is incredibly boring—everybody knows that this can be solved using a simple recursion.I deny to code something as simple as this!”

查理：” 这简直无聊至极——谁都知道用简单的递归就能解决这个问题。我可不会去写这么简单的东西！”

The teacher sighs: “Well, Charlie, let’s think about something for you to do: For you there is a fourth tower D. Calculate the smallest number of disk moves to move all the disks from tower A to tower D using all four towers.”

老师叹了口气说：” 好吧，查理，我们想想该让你做点什么吧：这里有第四座塔 D。请你计算出使用全部四座塔，将所有圆盘从 A 塔移到 D 塔所需的最少移动次数。”

Charlie looks irritated: “Urgh… Well, I don’t know an optimal algorithm for four towers… “

查理显得很恼火：” 呃……唉，我实在不知道针对四座塔的最优算法是什么……”

So the real problem is that problem solving does not belong to the things Charlie is good at. Actually, the only thing Charlie is really good at is “sitting next to someone who can do the job”. And now guess what — exactly! It is you who is sitting next to Charlie, and he is already glaring at you.

所以真正的问题在于，解决问题并非查理的强项。实际上，查理唯一擅长的事就是 “ 坐在能完成工作的人旁边 “。现在猜猜看——没错！你就坐在查理旁边，而他正在怒视着你。

Luckily, you know that the following algorithm works for: At firstdisks on tower A are fixed and the remainingdisks are moved from tower A to tower B using the algorithm for four towers.Then the remainingdisks from tower A are moved to tower D using the algorithm for three towers. At last thedisks from tower B are moved to tower D again using the algorithm for four towers (and thereby not moving any of thedisks already on tower D). Do this for alland find thewith the minimal number of moves.

幸运的是，你知道以下算法适用于的情况：首先在塔 A 上固定个盘子，然后用四塔算法将剩余的个盘子从塔 A 移到塔 B。接着用三塔算法将塔 A 上剩下的 k 个盘子移至塔 D。最后再用四塔算法将塔 B 中的个盘子移回塔 D（这样就不会移动已经位于塔 D 的那 k 个盘子）。对所有满足的值重复此过程，找出所需步数最少的 k 值。

So forandyou would first move 1 (3-2) disk from tower A to tower B using the algorithm for four towers (one move). Then you would move the remaining two disks from tower A to tower D using the algorithm for three towers (three moves). And the last step would be to move the disk from tower B to tower D using again the algorithm for four towers (another move). Thus the solution forandis 5 moves. To be sure that this really is the best solution foryou need to check the other possible values 1 and 3 for. (But, by the way, 5 is optimal… )

因此，当且时，首先需使用四塔算法执行一次移动，将 1 个圆盘（3-2）从塔 A 移到塔 B。接着，使用三塔算法执行三次移动，将剩余的 2 个圆盘从塔 A 移到塔 D。最后再使用四塔算法执行一次移动，将该圆盘从塔 B 移到塔 D。这样一来，且的最优解就是 5 次移动。为确认这确实是的最佳解，还需检验取 1 和 3 时的其他可能情况。（不过顺便说一句，5 次移动已经是最优解了……）

Input

There is no input.

Output

For each n (1 <= n <= 12) print a single line containing the minimum number of moves to solve the problem for four towers and n disks.

Limit

Analysis

首先，可能会想通过 DFS 实现，不过时间复杂度可能会比较高（因为不好标记状态）。一个剪枝思路是随递归记录当前操作次数，另外维护一个全局变量用于记录直到现在已经得到的最优解。当当前操作次数大于等于直到现在已经得到的最优解时可以直接放弃后续递归。

上述思路确实效率很低，最大的问题是 没有明确的结束条件，所以这个解法应该果断放弃。

根据例子来分析，假设盘片从 1 开始由小到大编号：
当时，只需要从 A 柱移动到 D 柱即可。
当时，先将 1 从 A 柱移动到 B/C 柱，然后将 2 从 A 柱移动到 D，最后将 1 移动到 D。
当时，先将 1 从 A 柱移动到 B/C 柱，然后将 2 从 A 柱移动到 C/B 柱，将 3 从 A 移动到 D 柱子，将 2 移动到 D，最后将 1 移动到 D。

可以发现，在过程中会出现可用柱规模缩短的情况，以时为例，将 1 从 A 柱移动到 B/C 柱时，剩余的盘片都在 A 且只剩余两个柱可用，忽略盘片 1，那么问题变成了 n = 2 情况的三柱汉诺塔问题。如果知道的三柱汉诺塔问题的最优解，那么再加上将 1 移动到 D 的一次就好了。

对于的三柱汉诺塔问题（A、B、C 柱），最优解是将 1 从 A 移动到 B，将 2 从 A 移动到 C，最后将 1 移动到 C。其中出现了二柱汉诺塔问题。

所以，我判断本题可以通过递推实现。

尝试以上述思路继续分析，当时，会发现有多种解法：

• 可以将 1 从 A 移动到 B，那么剩下的 2、3、4 变成了的三柱汉诺塔问题。
• 可以将 1、2 看作的四柱汉诺塔问题，将 1、2 放在 B 柱后， 3、4 看作的三柱汉诺问题，最后将 1、2 看作四柱汉诺塔问题放到 D
• 可以将 1、2、3 看作的四柱汉诺塔问题…

即，对于 A 柱上的初始盘可以划分为两组进行

那么我们定义一个数组用于存储各种情况的最优解：

其中表示柱的规模，表示盘片个数

初始状态（需按顺序赋值）：
，

递推公式：

Solve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
#include <cstring>

const int S = 5;
const int N = 13;

int dp[S][N];

int main () {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::memset(dp, 0x3f, sizeof dp);

    for(int i = 0; i < S; ++i)
        dp[i][1] = 1;

    for(int s = 3; s < S; ++s) {
        for(int n = 2; n < N; ++n) {
            for(int k = 1; k < n; ++k) {
                dp[s][n] = std::min(dp[s][n], dp[s][k] * 2 + dp[s - 1][n - k]);
            }
        }
    }

    for(int n = 1; n < N; ++n)
        std::cout << dp[4][n] << '\n';
    
    return 0;
}

补充：以上算法即 Frame-Stewart 算法，是 J.S. Frame 和 B.M. Stewart 在 1941 年各自独立提出的。在长达几十年的时间里，数学界和计算机界都只敢猜测这是多柱汉诺塔的最优解（即 Frame-Stewart 猜想），但一直无法严格证明。直到 2014 年，法国数学家 Thierry Bousch 才严格证明了当（四柱）时，Frame-Stewart 算法给出的确实是最小步数。而对于的情况，它到底是不是绝对的最优解，至今在数学界仍是一个未完全证明的问题。

Ref

Nowcoder: Strange Towers of Hanoi
Acwing: Strange Towers of Hanoi