首页 > 试题广场 >

给定下列递归算法的程序段，则f(20)的返回值为（）。 in

[单选题]

给定下列递归算法的程序段，则f(20)的返回值为（）。

int f(int n)
{
	if(n < 1) return 0;
	if(n <= 3) return 1;
	return f(n - 1) + f(n - 2) + f(n - 3);	
}

```
13745
```
```
25281
```
```
46499
```
```
85525
```

查看正确选项

WonderWu

这个和爬楼梯的算法问题差不多，需要推导出递推公式一个个计算（比较麻烦，有大佬有更好的方法的话欢迎补充）

理解题目：题目可以类比成爬楼梯的算法问题，一个人迈一步可以跨过1或2或3个台阶，现在一个人从20阶台阶高度下来，问一共有多少种走法可以走到台阶数为1到3之间的台阶。
初始化参数：
1. 首先显然，若人在台阶1到3之间（包括1和3）时已经符合要求，可以直接返回1，所以，f（1）到 f（3）= 1；
2. 当 n = 4时，走一步到3，走两步到2，走三步到1，三种走法都满足范围条件，所以 f（4） = 3；
3. 当 n = 5时，走一步到4，根据 ii 知道有3种方法，走两步到3，走三步到2，所以有5种方法，即 f（5） = 5；
4. 当 n = 6，7时，依照上述方法推导得 f（6） = 9 ，f（7）= 17（用于递推公式的验证，也可以运行代码求得）
推导递推公式
1. 根据上述规律（走了一步后到达前一个点，可以直接使用该点的f（n）值，走两步后……）
2. 所以当n >= 4时，f（n）= f（n-1）+f（n-2）+f（n-3）
3. 所以当n >= 5时，f（n-1）= f（n-2）+f（n-3）+f（n-4）
4. 两式相减得递推公式：f（n） = 2f（n-1）-f（n-4）
验证：
根据式子求得：
f（5）= 2f（4）-f（1）=2X3-1 =5
f（6）= 2f（5）-f（2）=2X5-1 =9
f（7）= 2*f（6）-f（3）=2X9-1 =17
（后续也是符合规律的，想验证的同学可以运行代码求得正确的数进行比较）
求解
然后……就开始痛苦的计算了，一个个进行递推
f（8） = 2Xf（7）- f（4） = 2X17 - 3 = 31
……（中间就省略了）
f（20） = 2f（19）- f（16）=2X25281 - 4063=46499