#G102. GESP level4 递推算法

GESP level4 递推算法

GESP level4 - 递推算法

  1. 下面关于递推的说法不正确的是( )。 {{ select(1) }}
  • 递推表现为自己调用自己
  • 递推是从简单问题出发,一步步的向前发展,最终求得问题,是正向的
  • 递推中,问题的n要求是在计算中确定,不要求计算前就知道n
  • 斐波那契数列可以用递推实现求解
  1. 小杨正在爬楼梯,需要爬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;
    }
    {{ select(2) }}
  • res += f1 + f2; f1 = f2; f2 = res;
  • res = f1 + f2; f1 = f2; f2 = res;
  • res += f1 + f2; f2 = res; f1 = f2;
  • res = f1 + f2; f2 = res; f1 = f2;
  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;
    }
    {{ select(3) }}
  • result = f1 + f2; f1 = f2; f2 = result;
  • result += f1 + f2; f1 = f2; f2 = result;
  • result += f1 + f2; f2 = result; f1 = f2;
  • result = f1 + f2; f2 = result; f1 = f2;
  1. 下列递推关系式表示斐波那契数列的是( )。 {{ select(4) }}
  • F(n)=F(n-1)+F(n-2)+F(n-3)
  • F(n)=F(n-1)+F(n-2)
  • F(n)=F(n-1) * F(n-2)
  • F(n)=F(n-1) / F(n-2)
  1. 下面函数中采用的算法是( )。
    int fib(int n) {
    int i, f[n]={0, 1};
    for(int i=2; i<=n; i++)
    f[i]=f[i-1]+f[i-2];
    return f[n];
    }
    {{ select(5) }}
  • 递推
  • 递归
  • 迭代
  • 循环
  1. 递推是一种通过已知的初始值和递推公式,逐步求解目标值的算法。( ) {{ select(6) }}
  • 对
  • 错
  1. 数列1, 1, 2, 3, 5, 8 ... 是以意大利数学家列昂纳多·斐波那契命名的数列,从第三个数开始,每个数是前面两项之和。如果计算该数列的第n项(其中n>3)fib(n),我们采用如下方法:①令fib(1)=fib(2)=1 ②用循环for i=3 to n 分别计算f(i) ③输出fib(n)。这体现了递推的编程思想。( ) {{ select(7) }}
  • 对
  • 错
  1. 下面代码采用递推算法来实现整数的阶乘(n! = n × (n-1) ×...×2×1),则横线上应填写( )。
    int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
    // 在此处填入代码
    }
    return result;
    }
    {{ select(8) }}
  • result *= i;
  • result += i;
  • result *= result;
  • result += result;
  1. 某算法的递推关系式为T(n)=T(n-1)+n(n为正整数)及T(0)=1,则该算法的时间复杂度为( )。 {{ select(9) }}
  • O(n)
  • O(n²)
  • O(n log n)
  • O(log n)
  1. 递推算法通常有初始值。( ) {{ select(10) }}
  • 对
  • 错