阅读程序

注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。

第7题【NOIP】2015

#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;
09	tot += fun(n - 1, fromPos, t);
	tot++;
11	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(7-1) }}

• 正确
• 错误

(2)当n为小于1000的正整数时，将第9行或第11行中其中一行去掉，程序输出n。()

{{ select(7-2) }}

• 正确
• 错误

(3)函数中的fromPos与toPos与答案无关。

{{ select(7-3) }}

• 正确
• 错误

(4)该程序的时间复杂度为O($2^n$)。

{{ select(7-4) }}

• 正确
• 错误

●选择题

5)fun(5,1,3)的值为()。

{{ select(7-5) }}

• 31
• 23
• 66
• 9

(6)fun(n,1,3)的通项公式为()

{{ select(7-6) }}

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