题目描述
以下数列0 1 1 2 3 5 8 13 21 …被称为斐波纳契数列。
这个数列从第3项开始,每一项都等于前两项之和。
输入一个整数N,请你输出这个序列的前N项。
样例
输入例子:5
输出:0 1 1 2 3
算法1
时间复杂度
2次线性的复炸度
2*n
计算就是o(n);
C++ 代码(开数组计算)
#include <iostream>
using namespace std;
int dp[10010];
int main()
{
int n;
cin>>n;
dp[0]=0;
dp[1]=1;
for(int i=2;i<=n;++i)
{
dp[i]=dp[i-1]+dp[i-2];
}
for(int i=0;i<n;++i) cout<<dp[i]<<' ';
return 0;
}
算法2
利用滚动数组
时间复杂度
边输入边输出,一次o(n)不开数组,空间o(1)
参考文献
C++ 代码
#include <iostream>
using namespace std;
int main()
{
int n,a=0,b=1,c;
cin>>n;
for(int i=0;i<n;++i)
{
if(i==0) //特殊判断一下,输出如果数据是0就是第一个输出0
{
cout<<0<<" ";
continue;
}
else if(i==1)//特殊判断,输出如果是1就输出一
{
cout<<1<<" ";
continue;
}
c=a+b;//
cout<<c<<" ";
a=b;
/*
c代表f(n),a代表f(n-1),b代表f(n-2),这样a+b=c就是f(n-1)+f(n-2)=f(n)
接下来求f(n+1),f(n+1)就是f(n)+f(n-1);
f(n)就是c;
f(n-1)就是b;
没有a的事情,所以把a赋值为b,b赋值为c,c变为a+b;
*/
b=c;
}
return 0;
}