0%

HDU 2064：汉诺塔Ⅲ 递归

发表于 分类于 Valine：

找规律水题

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2064

题意

汉诺塔问题变形，还是三根柱子，每次只能从中间的柱子移动到旁边的柱子，或者从旁边的柱子移动到中间。

思路

汉诺塔肯定就往递归上想。先分析简单情况，设结果为：

N = 1：f(1) = 2;显然

N = 2: f(2) = 8;以下用"大"、"小"的符号来图示：

​ 小大、空、空

  1. 大、小、空
  2. 大、空、小
  3. 空、大、小
  4. 空、小大、空
  5. 小、大、空
  6. 小、空、大
  7. 空、小、大
  8. 空、空、小大

然后思考递归的过程。参考经典汉诺塔的递归，每次递归关注的点在于最底下的盘子和上方的所有盘子。可以把N=2的情况中的"大"看做最底下的盘子，而"小"看成是上方的一摞盘子(子问题)。那么可以看出，”大“移动的次数为2次，其余6次都是"小"在移动。

因此我们只需抽象出每次移动"小"的操作，所对应的子问题的规模，便可列出递归方程式。由题意知，每次小的移动，都是进中间/出中间。而原问题是：从最左到最右。因而，当完成了一摞盘子“进中间”的操作后，只需把每个原子操作逆序执行（只不过对象换成另一根柱子），完成"出中间"的操作。因此，每个“进中间/出中间”的操作都是相同规模的子问题的一半，那么容易推导出递推式：

\[ f(n)=2 + 6 \times \frac 12 f(n-1)=2+3f(n-1) \]

验证一下N=1和N=2的情况，发现符合。从而代码易得。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll f(int n) {
    if (n == 1) {
        return 2;
    }
    else {
        return 2 + 3 * f(n - 1);
    }
}

int main() {
    int N;
    while (~scanf("%d", &N)) {
        printf("%lld\n", f(N));
    } 
    return 0;
}