CSP-J 卷

下列 C++ 代码用于求斐波那契数列，即第 $1$ 个数为 0，第 $2$ 个数为 1，从第三个数开始，依次是其前两个数之和。如果输入的值为大于 1 的正整数，该代码能实现所求。

01cin >> n;
02a = 0, b = 1;
03for (int j = 0; j < n; j++) {
04    cout << a << " ";
05    b = b + a;
06    a = b - a;
07}

在数学中 $N!$ 表示 $N$ 的阶乘，即 $1$ 到 $N$ 的乘积，如 $3!=1 \times 2 \times 3$。下面的 C++ 用于求 $1-N$ 的阶乘之和，如 $N$ 为 $3$，则是 $1!+2!+3!$。下面代码段补充选项后用于实现上述功能，其中不能实现阶乘和的选项是（ ）。

01int N;
02cin >> N;
03int tnt=0, nowNum = 1; //tnt保存求和之值，当前N的阶乘
04for (int i=1; i < N + 1; i++){
05    ____________ // 基于上一个计算出当前数的阶乘
06    ____________ // 从1到i每个数阶乘之和
07}
08cout << tnt;

小陈种植一批农作物，第一天需要浇水一次，随后的两天（第 $2$、第 $3$ 天），每天需要浇水 $2$ 次，再随后的 $3$ 天（第 $4$、第 $5$、第 $6$ 天），需要每天浇水 $3$ 次，这样持续下去，随后的 $n$ 天，每天需要浇水 $n$ 次。请问在 $100$ 天里，总共浇了多少次水（ ）。

某一系列数据的规律是从第 $3$ 个数值开始是前两个数之和。下面的代码求第 $N$ 个数的值，N 限定为大于 2。（ ）

01int start1; // 第1个数
02int start2; // 第2个数
03int N; //求N个数的值
04int tmp;
05cin >> start1 >> start2 >> N;
06for (int i = 2; i < N; i++){
07    tmp = start1 + start2;
08    start1 = start2;
09    start2 = tmp;
10}
11cout << start2;

在数学中 N! 表示 N 的阶乘，即 1 到 N 的乘积，如 $3!=1\times2\times3$ ，且 $0! = 1$ 。下面的两段 C++ 代码用于求 1 到 N 的阶乘之和，如 N 为 3，则结果是 9（ $1!+2!+3!$ 的值）。选项中的说法正确的是（ ）。

01// 实现1
02int i,N;
03cin >> N;
04int tnt = 0, last = 1;
05for (i = 1; i < N + 1; i++){
06    last *= i;
07    tnt += last;
08}
09cout << tnt << endl;

01// 实现2
02int i,N;
03cin >> N;
04int tnt = 0, tmp;
05for (i = 1; i < N + 1; i++){
06    tmp = 1;
07    for (int j = 1; j < i + 1; j++)
08    tmp *= j;
09    tnt += tmp;
10}
11cout << tnt << endl;

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

用递归法求 n 的阶乘，时间复杂度是 $O(n)$。

下面 C++ 函数中采用的算法是（ ）。

01int fib(int n)
02{
03    int i, f[n]={0, 1};
04
05    for(int i=2; i<=n; i++)
06        f[i]=f[i-1]+f[i-2];
07
08    return f[n];
09}

下面关于递推的说法不正确的是（ ）。

函数不可以调用自己。

一个一维数组，至少含有一个自然数 $N$，是一个合法的数列。可以在一维数组末尾加入一个自然数 $M$，$M$ 不能超过一维数组末尾元素的一半，形成一个新的合法的一维数组，如果 $N=6$，那么可以有 $6$ 个不同的合法数组。

下面代码采用递推算法来实现整数 $n$ 的阶乘（$n! = n \times (n-1) \times \ldots \times 2 \times 1$），则横线上应填写（ ）。

01int factorial(int n) {
02    int result = 1;
03    for (int i = 2; i <= n; i++) {
04        ____________  // 在此处填入代码
05    }
06    return result;
07}

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

以下代码用递推法求斐波那契数列的第 $n$ 项，时间复杂度为指数级。

01int fibonacci(int n) {
02    if (n == 0) return 0;
03    if (n == 1) return 1;
04
05    int f0 = 0; // F(0)
06    int f1 = 1; // F(1)
07    int current;
08
09    for (int i = 2; i <= n; i++) {
10        current = f0 + f1; // F(n) = F(n-1) + F(n-2)
11        f0 = f1;
12        f1 = current;
13    }
14
15    return current;
16}

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

01int fib(int n) {
02    if (n == 0 || n == 1)
03        return n;
04
05    int f1 = 0;
06    int f2 = 1;
07    int result = 0;
08    for (int i = 2; i <= n; i++) {
09        ____________    // 在此处填入代码
10    }
11    return result;
12}

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

某算法的递推关系式为 $T(n) = T(n - 1) + n$ （$n$ 为正整数）及 $T(0) = 1$，则该算法的时间复杂度为 $O(n^2)$。

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

01int f(int n) {
02    if (n == 1 || n == 2)
03        return n;
04
05    int f1 = 1;
06    int f2 = 2;
07    int res = 0;
08    for (int i = 3; i <= n; i++) {
09        ____________      // 在此处填入代码
10    }
11    return res;
12}

以下关于递推算法基本思想的描述,正确的是( )。

下述斐波那契数列计算的时间复杂度是( )。

01int fibonacci(int n) {
02    if (n == 0) return 0;
03    if (n == 1) return 1;
04    return fibonacci(n - 1) + fibonacci(n - 2);
05}

以下程序中使用了递推方式计算阶乘($n! = 1 \times 2... \times n$),计算结果正确。

01int factorial(int n) {
02    int res = 1;
03    for (int i = 0; i < n; ++i) {
04        res *= i;
05    }
06    return res;
07}

小杨正在爬楼梯，需要 $n$ 阶才能到达楼顶，每次可以爬 $1$ 阶或 $2$ 阶，求小杨有多少种不同的方法可以爬到楼顶，横线上应填写（ ）。

01int climbStairs(int n) {
02    if (n <= 2) return n;
03    int prev2 = 1;
04    int prev1 = 2;
05    int current = 0;
06    for (int i = 3; i <= n; ++i) {
07        ____________    // 在此处填入代码
08
09    }
10    return current;
11}

递推是在给定初始条件下，已知前一项（或前几项）求后一项的过程。

给定函数 climbStairs(int n) 的定义如下，则 climbStairs(5) 的返回值是（ ）。

01int climbStairs(int n) {
02    if(n <= 2) return n;
03    int a = 1, b = 2;
04    for(int i = 3; i <= n; i++) {
05        int temp = a + b;
06        a = b;
07        b = temp;
08    }
09    return b;
10}

考虑用如下递推方式计算斐波那契数列，时间复杂度是 $O(n)$。

01int n = 10;
02int f[20];
03f[0] = 0;
04f[1] = 1;
05for (int i = 2; i <= n; i++)
06    f[i] = f[i - 1] + f[i - 2];

关于递推算法的描述，正确的是（ ）。

执行 climb(6) 的返回值为（ ）。

01int climb(int n){
02    if(n <= 2) return n;
03    int a = 1, b = 2, c = 0;
04    for(int i = 3; i <= n; i++){
05        c = a + b;
06        a = b;
07        b = c;
08    }
09    return c;
10}

下面用递推方式计算斐波那契数列第 $n$ 项的程序，时间复杂度是 $O(2^n)$。

01int fib(int n) {
02    if (n <= 1) return n;
03    int f0 = 0, f1 = 1, cur = 0;
04    for (int i = 2; i <= n; i++) {
05        cur = f0 + f1;
06        f0 = f1;
07        f1 = cur;
08    }
09    return cur;
10}

小杨的机器人正在能量踏板上跳跃，踏板编号为 $1,2,3,\ldots$。跳到第 $n$ 块踏板的方案数满足递推式 f(n) = f(n - 1) + f(n - 2)。若 f(1) 为 1，f(2) 为 2，则运行以下代码计算 jump(5) 的结果是（ ）。

01int jump(int n) {
02    if (n <= 2)
03        return n;
04    int a = 1, b = 2, c = 0;
05    for (int i = 3; i <= n; i++) {
06        c = a + b;
07        a = b;
08        b = c;
09    }
10    return c;
11}

递归函数在调用自身时，必须满足（ ），以避免无限递归？

在 C 语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。

下面 C++ 代码用于求斐波那契数列，该数列第 $1$、$2$ 项为 $1$，以后各项均是前两项之和。函数 fibo() 属于（ ）。

01int fibo(int n) {
02    if (n <= 0)
03        return 0;
04    if (n == 1 || n == 2)
05        return 1;
06
07    int a = 1, b = 1, next;
08    for (int i = 3; i <= n; i++) {
09        next = a + b;
10        a = b;
11        b = next;
12    }
13    return next;
14}

下面 C++ 代码用于求斐波那契数列，该数列第 $1$、$2$ 项为 $1$，以后各项均是前两项之和。下面有关说法错误的是（ ）。

01int fiboA(int N)
02{
03    if (N == 1 || N == 2)
04        return 1;
05    return fiboA(N - 1) + fiboA(N - 2);
06}
07int fiboB(int N)
08{
09    if (N == 1 || N == 2)
10        return 1;
11    int last2 = 1, last1 = 1;
12    int nowVal = 0;
13    for (int i = 2; i < N; i++)
14    {
15        nowVal = last1 + last2;
16        last2 = last1;
17        last1 = nowVal;
18    }
19    return nowVal;
20}

阅读下面的 C++ 代码，执行后其输出是（ ）。

01int stepCount = 0;
02int fracA(int N)
03{
04    stepCount += 1;
05    cout << stepCount << "->";
06    int rtn = 1;
07    for (int i = 1; i <= N; i++)
08        rtn *= i;
09    return rtn;
10}
11int fracB(int N)
12{
13    stepCount += 1;
14    cout << stepCount << "->";
15    if (N == 1)
16        return 1;
17    return N * fracB(N - 1);
18}
19int main()
20{
21    cout << fracA(5);
22    cout << "<====>";
23    cout << fracB(5);
24    return 0;
25}

以下 C++ 代码能以递归方式实现斐波那契数列，该数列第 $1$、$2$ 项为 $1$，以后各项均是前两项之和。

01int Fibo(int N)
02{
03    if (N == 1 || N == 2)
04        return 1;
05    else
06    {
07        int m = fiboA(N - 1);
08        int n = fiboB(N - 2);
09        return m + n;
10    }
11}