#include <iostream>
using namespace std;
int FibonacciOne(int ); //递归算法
int FibonacciTwo(int ); //非递归算法
int main()
{
int n,m;
cout<<"请输入一个数n,递归计算前n项Fibonacci数列: ";
cin>>n;
for(int i = 1;i <= n;++i)
cout<<FibonacciOne(i)<<" "; //使用递归算法
cout<<endl;
cout<<"请输入一个数m,非递归计算前m项Fibonacci数列: ";
cin>>m;
for(int i = 1;i <= m;++i)
cout<<FibonacciTwo(i)<<" "; //使用非递归算法
cout<<endl;
return 0;
}
int FibonacciOne(int n) //递归算法
{
if(n == 1 || n == 2)
return 1;
else
return FibonacciOne(n-1)+FibonacciOne(n-2); //递归地计算
}
int FibonacciTwo(int n) //非递归算法
{
if(!n) return 0;
int* f = new int[n]; //新建一个临时数组,存放中间值
f[0] = 0;
f[1] = 1;
if(n == 1 || n == 2) return 1;
for(int i = 2;i <= n;++i) //循环计算从2到n的值
f[i] = f[i-1]+f[i-2];
int k = f[n]; //k等于第n个数列值
delete [] f; //释放临时数组空间
return k;
}
评论0