斐波那契(Fibonacci)数列可以递归地定义为:
用递归算法求解F(5)时需要执行(63)次“+”运算,该方法采用的算法策略是(64)。
A.5
B.6
C.7
D.8
● 斐波那契(Fibonacci)数列可以递归地定义为:
?
用递归算法求解F(5)时需要执行 (63) 次“+”运算,该方法采用的算法策略是 (64) 。
(63)
A. 5
B. 6
C. 7
D. 8
(64)
A. 动态规划
B. 分治
C. 回溯
D. 分支限界
计算斐波那契数列第n项的函数定义如下: intfib(intn){ if(n==0)returnl; elseif(n==l)return2: elsereturnfib(n-1)+fib(n-2); } 若执行函数调用表达式fib(2),函数fib被调用的次数是()。
A.1
B.2
C.3
D.4
请在函数fun()的横线上填写若干表达式,使从键盘上输入一个整数n,输出n对应的斐波那契数列。斐波那契数列是一整数数列,该数列自第三项开始,每数等于前面两数之和,即0,1,1,2,3,5,8,13,21,34,55,…。
注意:部分源程序给出如下。
请勿改动主函数main和其他函数中的任何内容,仅在函数fun()的横线上填入所编写的若干表达式或语句。
试题程序:
include<stdio.h>
int fun(int n);
main()
{
int i,n=0;
scanf("%d",&n);
for(i=0;i<n; i++)
printf("%d",fun(i));
}
int fun(int n)
{
if(【 】)
return 0;
else
if(【 】)
return 1;
else
return【 】;
}
ax,其中max为某个约定的常数。(注意:本题所用循环队列的容世仅为k,则在算法执行结束时,留在循环队列中的元素应是所求k阶斐波那奥序列中的最后k项。
已知k阶斐波那契序列的定义为
试编写求k阶斐波那契序列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现。
试题四(共 15 分)
阅读以下说明和 C 函数代码,回答问题并将解答写在答题纸的对应栏内。
[说明]
著名的菲波那契数列定义式为
f1 = 1 f2 = 1 fn = fn-1 + fn-2 (n = 3,4,…)
因此,从第 1 项开始的该数列为 1,1,2,3,5,8,13,21,…。函数 fib1 和 fib2 分别用递归方式和迭代方式求解菲波那契数列的第 n 项(调用 fib1、fib2 时可确保参数 n 获得一个正整数) 。
[C函数代码]
[问题 1](6 分)
函数 fib1 和 fib2 存在错误,只需分别修改其中的一行代码即可改正错误。
(1)函数 fib1 不能通过编译,请写出 fib1 中错误所在行修改正确后的完整代码;
(2)函数 fib2 在n≤2 时不能获得正确结果,请写出 fib2 中错误所在行修改正确后的完整代码。
[问题 2](3 分)
将函数 fib1 和 fib2 改正后进行测试,发现前 46 项都正确,而第 47 项的值是一个负数,请说明原因。
[问题 3](6 分)
函数 fib1、fib2 求得菲波那契数列第 n 项(n>40)的速度并不相同,请指出速度慢的函数名,并简要说明原因。
A、1
B、2
C、3
D、4