第七题（NOIP2015）

#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;
}

1. 【判断题】当n为小于1000的正整数时，将第9行和第11行一起去掉，程序输出结果为1。
   {{ select(1) }}

• 正确
• 错误

2. 【判断题】当n为小于1000的正整数时，将第9行或第11行中其中一行去掉，程序输出n。
   {{ select(2) }}

• 正确
• 错误

3. 【判断题】函数中的fromPos与toPos与答案无关。
   {{ select(3) }}

• 正确
• 错误

4. 【判断题】该程序的时间复杂度为O(2ⁿ)。
   {{ select(4) }}

• 正确
• 错误

5. 【选择题】fun(5, 1, 3)的值为（ ）。
   {{ select(5) }}

• 31
• 23
• 66
• 9

6. 【选择题】fun(n, 1, 3)的通项公式为（ ）。
   {{ select(6) }}

• fun(n-1,1,3) * 2+1
• 2 * n
• 2ⁿ-1
• ($(\frac{1+\sqrt{5}}{2})^{n}$-$(\frac{1-\sqrt{5}}{2})^{n}$)/ $\sqrt{5}$