GESP-C++四级 题库
以下关于递推算法基本思想的描述,正确的是?( )
选项A,是分治;
选项C,是枚举;
选项D,是贪心;
本题答案为选项B。
小杨正在爬楼梯,需要爬n 阶才能到达楼顶。如果每次可以爬 1个或 2个台阶,下面代码采用递推算法来 计算 —共有多少种不同的方法可以爬到楼顶,则横线上应填写( )。
res表示当前到达第i层的方法数, f1表示到达前—层的方法数, f2表示到达上—层的方法数,所以本题选 择B 。
下面代码采用递推算法来实现整数 n 的阶乘 (ni=n×(n−1)×...×2×1),则横线上应填写( )。
阶乘的定义是:n! = n * (n-1) * (n-2) * … * 1。
在循环中,从2 到n,每次应将result 乘以当前的i,所以正确的填入应该是result *= i;。
下面关于递推的说法不正确的是( )。
自己调用自己是递归的表现,而不是递推,注意区分。
考虑用如下递推方式计算斐波那契数列,时间复杂度是 O(n)。
某算法的递推关系式为 T(n)=T(n−1)+n(n 为正整数)及 T(0)=1,则该算法的时间复杂度为 O(n2)。
递推算法通过逐步求解当前状态和前一个或几个状态之间的关系来解决问题。
递推算法通过利用已知的前一个或多个状态来逐步计算当前状态,从而解决问题。这种方法常用于动态规划和分治策略中,通过构建状态转移方程来有效地求解复杂问题。
以下代码用递推法求斐波那契数列的第n 项,时间复杂度为指数级。
迭代的方式计算斐波那契数列,时间复杂度为线性O(n),而不是指数级O(2^n)
数列 1, 1, 2, 3, 5, 8 ... 是以意大利数学家列昂纳多·斐波那契命名的数列,从第三个数开始,每个数是前面两项之和。如果计算该数列的第 n 项(其中 n>3)fib(n),我们采用如下方法:① 令 fib(1)=fib(2)=1 ②用循环 for i=3to n 分别计算 f(i) ③输出 fib(n)。这体现了递推的编程思想。