GESP 4级客观题｜递推｜课后作业

考试频率：高频。本卷共 6 题。

1. 下⾯代码采⽤递推算法来计算斐波那契数列 $f(n) = f(n-1) + f(n-2)$ ，则横线上应填写（ ）。

int fib(int n) {
    if (n == 0 || n == 1)
        return n;

    int f1 = 0;
    int f2 = 1;
    int result = 0;
    for (int i = 2; i <= n; i++) {
        ________________________________     // 在此处填入代码
    }
    return result;
}

//A:
result = f1 + f2;
f1 = f2;
f2 = result;

//B:
result += f1 + f2;
f1 = f2;
f2 = result;

//C:
result += f1 + f2;
f2 = result;
f1 = f2;

//D:
result = f1 + f2;
f2 = result;
f1 = f2;

{{ select(1) }}

• A
• B
• C
• D

2. 数列 1, 1, 2, 3, 5, 8 ... 是以意大利数学家列昂纳多·斐波那契命名的数列，从第三个数开始，每个数是前面两项之和。如果计算该数列的第 n 项（其中 n>3）fib(n)，我们采用如下方法：① 令 fib(1)=fib(2)=1 ②用循环 for i=3to n 分别计算 f(i) ③输出 fib(n)。这体现了递推的编程思想。

   {{ select(2) }}

• 对
• 错

3. ⼀个⼀维数组，⾄少含有⼀个⾃然数N，是⼀个合法的数列。可以在⼀维数组末尾加⼊⼀个⾃然数M，M不能超过⼀维数组末尾元素的⼀半，形成⼀个新的合法的⼀维数组，如果N=6，那么可以有6个不同的合法数组。

   {{ select(3) }}

• 对
• 错

4. 递推算法通过逐步求解当前状态和前⼀个或⼏个状态之间的关系来解决问题。

   {{ select(4) }}

• 对
• 错

5. 递推是⼀种通过已知的初始值和递推公式，逐步求解⽬标值的算法。

   {{ select(5) }}

• 对
• 错

6. 小杨正在爬楼梯，需要爬 $n$ 阶才能到达楼顶。如果每次可以爬 1个或 2个台阶，下面代码采用递推算法来计算一共有多少种不同的方法可以爬到楼顶，则横线上应填写（ ）。

int f(int n)
{
    if (n == 1 || n == 2)
        return n;

    int f1 = 1;
    int f2 = 2;
    int res = 0;
    for (int i = 3; i <= n; i++)
    {
        ________________________________ // 在此处填入代码
    }
    return res;
}

//A:
res += f1 + f2;
f1 = f2;
f2 = res;

//B:
res = f1 + f2;
f1 = f2;
f2 = res;

//C:
res += f1 + f2;
f2 = res;
f1 = f2;

//D:
res = f1 + f2;
f2 = res;
f1 = f2;

{{ select(6) }}

• A
• B
• C
• D