「Strange Towers of Hanoi 4」奇怪的汉诺塔

题目描述

有 4 根柱子 A、B、C、D 和 $n$ 个尺寸互不相同的圆盘，初始全部按"上小下大"叠在柱子 A 上。每次只能移动柱顶的一个圆盘，且只能放到空柱上或更大的圆盘上。对于 $1 \leqslant n \leqslant 12$ ，输出把全部圆盘从 A 搬到 D 所需的最小移动次数，每个 $n$ 占一行。

没有输入。

思路

四塔没有唯一中转柱，需要枚举"最大盘移动前已经搬走多少个最小盘" $k$ ：先用四塔把 $k$ 个最小盘搬到中转柱（ $f(k)$ 步），再用三塔把剩下 $n-k$ 个大盘搬到 D（ $2^{n-k}-1$ 步），最后用四塔把 $k$ 个最小盘接到 D（又是 $f(k)$ 步），取最小值： $f(n)=\min_{0\leqslant k<n}(2f(k)+2^{n-k}-1)$ ， $f(0)=0$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 09:57
# update_at: 2026-10-01 09:57

MAX_N = 12  # 题面要求输出 n = 1..12 的全部答案


def solve() -> None:
    """按四塔递推填出 f[1..MAX_N] 并逐行输出。"""
    f = [0] * (MAX_N + 1)  # f[n]：n 个盘从 A 柱搬到 D 柱的最少步数；f[0] = 0 表示空柱不用搬
    for n in range(1, MAX_N + 1):
        # 枚举第一个"拆点" k：先用四塔把 k 个最小盘搬到中转柱（f[k] 步），
        # 再用三塔把剩下 n-k 个大盘搬到 D 柱（1 << (n - k) 再减 1 步，此时中转柱被小盘占住），
        # 最后用四塔把 k 个最小盘接到 D 柱上（又是 f[k] 步）。
        # k = 0 对应"不借第四座塔"，即标准三塔搬法 2^n - 1 步，同样要参与取最小。
        f[n] = min(2 * f[k] + (1 << (n - k)) - 1 for k in range(n))
    print("\n".join(map(str, f[1:])))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
31
32
33
34
35/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:13
 * update_at: 2026-10-06 11:14
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 12; // 题目要求输出 n = 1..12 的答案

ll f[MAXN + 1]; // f[n] 表示 n 个盘从 A 柱搬到 D 柱的最少步数，f[0] = 0

int main() {
    // 四塔汉诺塔 Frame-Stewart 递推：
    // 先用四塔把 k 个最小盘搬到中转柱（f[k] 步），
    // 再用三塔把剩下 n-k 个大盘搬到 D 柱（2^{n-k} - 1 步），
    // 最后用四塔把 k 个最小盘接到 D 柱（又是 f[k] 步）。
    // k = 0 对应不借第四座塔，即标准三塔搬法。
    for (int n = 1; n <= MAXN; n++) {
        f[n] = (1LL << n) - 1; // 先取三塔上界
        for (int k = 0; k < n; k++) {
            ll cur = 2 * f[k] + (1LL << (n - k)) - 1;
            if (cur < f[n]) f[n] = cur;
        }
    }

    for (int n = 1; n <= MAXN; n++) {
        printf("%lld\n", f[n]);
    }
    return 0;
}

「Strange Towers of Hanoi 4」 奇怪的汉诺塔

目录

题目描述

思路

参考代码

「Strange Towers of Hanoi 4」奇怪的汉诺塔