太原建站模板,网络软文营销是什么意思,苏州优化外包,网站建设网页设计面试题9#xff1a;斐波那契数列 题目一#xff1a;写一个函数#xff0c;输入n#xff0c;求斐波那契#xff08;Fibonacci#xff09;数列的第n项。斐波那契数列的定义如下#xff1a; ❖ 效率很低的解法#xff0c;挑剔的面试官不会喜欢
代码如下:
long long fib(…面试题9斐波那契数列 题目一写一个函数输入n求斐波那契Fibonacci数列的第n项。斐波那契数列的定义如下 ❖ 效率很低的解法挑剔的面试官不会喜欢
代码如下:
long long fib(unsigned int n)
{if (n 0) return 0;if (n 1) return 1;return fib(n - 1) fib(n - 2);
}❖ 面试官期待的实用解法
其实改进的方法并不复杂。上述递归代码之所以慢是因为重复的计算太多我们只要想办法避免重复计算就行了。 比如我们可以把已经得到的数列中间项保存起来如果下次需要计算的时候我们先查找一下如果前面已经计算过就不用再重复计算了。
更简单的办法是从下往上计算首先根据f0和f1算出f2再根据f1和f2算出f3……依此类推就可以算出第n 项了。很容易理解这种思路的时间复杂度是On。
实现代码如下
#include iostream
using namespace std;
typedef long long LL;LL fib(unsigned int n)
{int res[2] { 0,1 };if (n 2) return res[n];LL fibminone 1;LL fibmintwo 0;LL fibN 0;for (unsigned int i 2; i n; i){fibN fibminone fibmintwo;fibmintwo fibminone;fibminone fibN;}return fibN;
}测试用例 ● 功能测试如输入3、5、10等。 ● 边界值测试如输入0、1、2。 ● 性能测试输入较大的数字如40、50、100等。 本题考点 ● 考查对递归、循环的理解及编码能力。 ● 考查对时间复杂度的分析能力。 ● 如果面试官采用的是青蛙跳台阶的问题那同时还在考查应聘者的数学建模能力。
