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   
输出：_________

请写出程序的输出结果。

答案

31

题解

考点定位

本题考「递归模拟」,对应大纲 4.2.3 递归（难度【4】）。

解题过程

fun(n,from,to)：n=0 返回 0；找中转柱 t；递归 fun(n−1,from,t)+1+fun(n−1,t,to)——汉诺塔移动次数 2ⁿ−1：

n=5 ⇒ 2⁵−1 = 31。

答案：31。

易错提醒

① 识别汉诺塔：三次调用中的中转柱选择；② 总移动次数 2ⁿ−1。