NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 26 题

#include <iostream> 
using namespace std; 
int fun(int n, int fromPos, int toPos) { 
 int t, tot; 
    if (n == 0) 
     return 0; 
    for (t = 1; t <= 3; t++) 
        if (t != fromPos && t != toPos) 
            break; 
    tot = 0; 
    tot += fun(n - 1, fromPos, t); 
    tot++; 
    tot += fun(n - 1, t, toPos); 
    return tot; 
} 
 
int main() { 
    int n; 
    cin >> n; 
    cout << fun(n, 1, 3) << endl; 
    return 0; 
} 

输入：5 输出：_________

这题看着像递归，其实命题人没想考你写递归式，而是想考你算汉诺塔移动次数的规律。拿到题先别急着套公式，数数 n=1,2,3 时各是多少，发现规律是 2^n - 1，直接代入 n=5 算出 31 就完事。

最容易栽跟头的就是死算递归，一层层展开 n=5 会算到几十层，手算容易乱。还有人会记错公式，把 2^n - 1 记成 2^n 或者 2^n + 1，或者以为每次移动只加 1 次大盘，忘了 n-1 个盘子要来回各一次，导致结果差了一倍。还有学生看到 fun(n-1, fromPos, t) 和 fun(n-1, t, toPos) 就以为这是两个独立过程，没意识到它们合起来才是把 n-1 个盘子从 from 移到 to 的完整步骤，中间夹着那个 tot++ 才是移大盘。

考点概念：汉诺塔递归计数

这道题考的是汉诺塔移动次数的规律。fun(n, fromPos, toPos) 这个函数名里就藏着线索：把 n 个盘子从 fromPos 移到 toPos。递归逻辑很清晰：先把上面 n-1 个盘子移到第三个柱子 t（辅助柱），再把最底下的那个大盘子移到目标柱 toPos，最后把那 n-1 个盘子从 t 移到 toPos。所以移动次数 T(n) = 2*T(n-1) + 1，展开就是 2^n - 1。

命题视角：为什么考这个？

命题人没想让你现场推导递归式，而是想考你观察规律的能力。汉诺塔是经典模型，但直接让你写递归式容易陷入死循环，所以给了你代码让你算结果。这题的坑在于：代码里那个 for 循环找 t 的过程虽然有点绕，但对结果毫无影响——t 永远是剩下的那个柱子。真正关键的是那个 tot++，它对应的是移动最底下的那个大盘子。很多人会忽略这一点，以为每次递归只加 1，或者以为 tot++ 是多余的，结果算出来的数就错了。