首页 > 代码库 > 9.求斐波那契Fibonacci数列通项
9.求斐波那契Fibonacci数列通项
(1)递归实现:
#include<iostream>
using namespace std;
int Fibonacci(int);
int main()
{
int n;
cout<<"please input an number n: "<<endl;
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<Fibonacci(i)<<endl;
}
return 0;
}
int Fibonacci(int n)//运用递归求斐波那契数列
{
if(n<3)
{
return 1;
}else
{
return Fibonacci(n-1)+Fibonacci(n-2);
}
using namespace std;
int Fibonacci(int);
int main()
{
int n;
cout<<"please input an number n: "<<endl;
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<Fibonacci(i)<<endl;
}
return 0;
}
int Fibonacci(int n)//运用递归求斐波那契数列
{
if(n<3)
{
return 1;
}else
{
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
(2)数组实现:明显感觉数组效率要高很多
#include<iostream>
using namespace std;
int Fibonacci(int);
int main()
{
int n;
cout<<"please input an number: "<<endl;
cin>>n;
cout<<Fibonacci(n);
return 0;
}
int Fibonacci(int n)
{
if(n<1)
{
return -1;
}
if(n<3)
{
return 1;
}
int *a=new int[n];//开辟一块内存空间
a[0]=a[1]=1;
for(int i=2;i<n;i++)
{
a[i]=a[i-1]+a[i-2];
}
for(int j=0;j<n;j++)//输出所求数组
{
cout<<a[j]<<endl;
}
using namespace std;
int Fibonacci(int);
int main()
{
int n;
cout<<"please input an number: "<<endl;
cin>>n;
cout<<Fibonacci(n);
return 0;
}
int Fibonacci(int n)
{
if(n<1)
{
return -1;
}
if(n<3)
{
return 1;
}
int *a=new int[n];//开辟一块内存空间
a[0]=a[1]=1;
for(int i=2;i<n;i++)
{
a[i]=a[i-1]+a[i-2];
}
for(int j=0;j<n;j++)//输出所求数组
{
cout<<a[j]<<endl;
}
}
(3)运用向量:
#include<iostream>
#include<vector>//使用向量须声明
using namespace std;
int Fibonacci(int);
int main()
{
int n;
cout<<"please input an number: "<<endl;
cin>>n;
cout<<Fibonacci(n)<<endl;
return 0;
}
int Fibonacci(int index) //借用vector<int>实现
{
if(index<1)
{
return -1;
}
vector<int> a(2,1); //创建一个含有2个元素都为1的向量
a.reserve(3);//reserve(size)为当前vector预留至少共容纳size个元素的空间
for(int i=2;i<index;i++)
{
a.insert(a.begin(),a.at(0)+a.at(1));
a.pop_back();//pop_back()函数删除当前vector最末的一个元素
}
return a.at(0);//at() 函数 返回当前Vector指定位置loc的元素的引用
#include<vector>//使用向量须声明
using namespace std;
int Fibonacci(int);
int main()
{
int n;
cout<<"please input an number: "<<endl;
cin>>n;
cout<<Fibonacci(n)<<endl;
return 0;
}
int Fibonacci(int index) //借用vector<int>实现
{
if(index<1)
{
return -1;
}
vector<int> a(2,1); //创建一个含有2个元素都为1的向量
a.reserve(3);//reserve(size)为当前vector预留至少共容纳size个元素的空间
for(int i=2;i<index;i++)
{
a.insert(a.begin(),a.at(0)+a.at(1));
a.pop_back();//pop_back()函数删除当前vector最末的一个元素
}
return a.at(0);//at() 函数 返回当前Vector指定位置loc的元素的引用
}
(4)使用队列:
#include<iostream>
#include<queue>//使用队列须声明
using namespace std;
int Fibonacci(int);
int main()
{
int n;
cout<<"please input an number: "<<endl;
cin>>n;
cout<<Fibonacci(n)<<endl;
return 0;
}
int Fibonacci(int index) //队列实现
{
if(index<1)
{
return -1;
}
queue<int>q;
q.push(1);
q.push(1);
for(int i=2;i<index;i++)
{
q.push(q.front()+q.back());
q.pop();
}
return q.back();
#include<queue>//使用队列须声明
using namespace std;
int Fibonacci(int);
int main()
{
int n;
cout<<"please input an number: "<<endl;
cin>>n;
cout<<Fibonacci(n)<<endl;
return 0;
}
int Fibonacci(int index) //队列实现
{
if(index<1)
{
return -1;
}
queue<int>q;
q.push(1);
q.push(1);
for(int i=2;i<index;i++)
{
q.push(q.front()+q.back());
q.pop();
}
return q.back();
}
(5)迭代法:
#include<iostream>
using namespace std;
int Fibonacci(int);
int main()
{
int n;
cout<<"please input an number: "<<endl;
cin>>n;
cout<<Fibonacci(n)<<endl;
return 0;
}
int Fibonacci(int n) //队列实现
{
int i,a=1,b=1,c=1;
if(n<1)
{
return -1;
}
for(i=2;i<n;i++)
{
c=a+b; //辗转相加法(类似于求最大公约数的辗转相除法)
a=b;
b=c;
}
return c;
using namespace std;
int Fibonacci(int);
int main()
{
int n;
cout<<"please input an number: "<<endl;
cin>>n;
cout<<Fibonacci(n)<<endl;
return 0;
}
int Fibonacci(int n) //队列实现
{
int i,a=1,b=1,c=1;
if(n<1)
{
return -1;
}
for(i=2;i<n;i++)
{
c=a+b; //辗转相加法(类似于求最大公约数的辗转相除法)
a=b;
b=c;
}
return c;
}
(6)二分矩阵方法(我自己还不怎么懂。。。)?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。