题目描述

• 有 3 根柱子(柱子 A, 柱子 B, 柱子 C) 和 n 块圆盘，每个圆盘的大小不同，初始状态下所有圆盘都在柱子A上，最大的圆盘放在最下面，最小的圆盘放在最上面
• 每一时刻你可以把某一根柱子顶端的圆盘移动到另一根柱子的顶端，目标是把所有盘子都移动到柱子C上
• 移动的过程中必须要保证较大的圆盘不会压在较小的圆盘上
• 请你求出最少需要移动的次数，并输出解决方案

• $n=3$ 时的方案

  

输入格式

输入一个整数 n 代表圆盘的数量

输出格式

输出一个回文质数的列表，一行一个。

3

A->C
A->B
C->B
A->C
B->A
B->C
A->C
7

提示

• 考虑 3 个圆盘的情况
  • 必须将 2 个小的圆盘，先借助柱子 C，从柱子A移动到柱子 B
  • 然后将最大的圆盘从柱子 A，移动到柱子 C
  • 然后再将 2 个小的圆盘，借助柱子 A，从柱子 B 移动到柱子 C
  • 至此，问题解决
• 假设函数 solve(n, A, B, C) 表示将 $n$ 个柱子从柱子 A，借助柱子 B，移动到柱子 C
  • 那么必须先将 $n-1$ 个小的圆盘，借助柱子 C，由柱子A 移动到柱子 B，solve(n - 1, A, C, B)
  • 在将最大的圆盘从柱子 A，移动到柱子 C
  • 最后将 $n-1$ 个小的圆盘，借助柱子 A，由柱子 B移动到柱子 C，solve(n - 1, B, A, C)

int solve(int n, string A, string B, string C) {
    // 第一步: 递归函数先写终止条件
    if (n == 1) {
        cout << A << "->" << C << endl;
        return 1;
    }
    // 第二步: 将问题分解成几个小问题
    // 那么必须先将 n-1 个小的圆盘，借助柱子 C，有柱子A 移动到柱子 B
    int ans = solve(n - 1, A, C, B);
    // 在将最大的圆盘从柱子 A，移动到柱子 C
    cout << A << "->" << C << endl; 
    // 最后将 n-1 个小的圆盘，借助柱子 A，由柱子 B移动到柱子 C
    int res = solve(n - 1, B, A, C);
    return ans + 1 + res;
}

数据规模与限制

• $1 \le n \le 10$
• 1s, 1024KiB for each test case.