[NOIP2007-普及] Hanoi双塔问题

题目描述

$A$ 、 $B$ 、 $C$ 三根柱子， $A$ 柱上叠着 $2n$ 个圆盘，共 $n$ 种尺寸，每种尺寸恰好两个相同且不加区分的圆盘。每次只能移动某柱最顶端的一个圆盘到另一柱顶，任何时刻三根柱都要保持上小下大。求把全部 $2n$ 个盘移到 $C$ 柱的最少移动次数 $A_n$ 。

输入一个正整数 $n$ （ $1 \le n \le 200$ ），输出 $A_n$ 。

样例输入 1：1，输出 2；样例输入 2：2，输出 6。

思路

把最大的 2 个盘看成整体：先花 $A_{n-1}$ 步把上面 $2(n-1)$ 个盘搬到 $B$ ，再各用 1 步把两个最大盘落到 $C$ 底，最后再花 $A_{n-1}$ 步把 $B$ 上的盘搬回 $C$ ，得 $A_n = 2A_{n-1} + 2$ ， $A_1 = 2$ 。展开递推得通项 $A_n = 2^{n+1} - 2$ 。 $n = 200$ 时约有 61 位十进制，超出 64 位整数，需要手写高精度。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19#!/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-02 07:19
# update_at: 2026-10-02 07:19

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    # 递推 A_k = 2*A_{k-1} + 2，通项 A_n = 2^(n+1) - 2
    print((2 << n) - 2)


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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * 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 13:51
 * update_at: 2026-10-06 13:51
 */
#include <cstdio>

typedef long long ll;

const int MAXL = 70; // n=200 时 2^201-2 约有 61 位十进制，开 70 位足够
const int BASE = 10; // 每位存一个十进制数字

int len;         // 高精度数的位数
int dig[MAXL];   // dig[i] 表示 10^i 位上的数字

// 高精度乘 2：直接按位翻倍再处理进位
void mul2() {
    int carry = 0;
    for (int i = 0; i < len; i++) {
        int cur = dig[i] * 2 + carry;
        dig[i] = cur % BASE;
        carry = cur / BASE;
    }
    if (carry > 0) {
        dig[len] = carry;
        len++;
    }
}

int main() {
    ll n; // 盘子的种类数
    scanf("%lld", &n);

    // 答案为 2^(n+1) - 2：先存数字 1，再乘 n+1 次 2
    dig[0] = 1;
    len = 1;
    for (ll i = 0; i <= n; i++) mul2();

    // 减 2（结果保证非负，因为 n >= 1 时 2^(n+1) >= 4）
    dig[0] -= 2;
    for (int i = 0; i < len; i++) {
        if (dig[i] < 0) {
            dig[i] += BASE;
            dig[i + 1] -= 1;
        }
    }
    while (len > 1 && dig[len - 1] == 0) len--; // 去掉前导零

    for (int i = len - 1; i >= 0; i--) printf("%d", dig[i]);
    printf("\n");
    return 0;
}

[NOIP2007-普及] Hanoi双塔问题

目录

题目描述

思路

参考代码