编辑代码

using namespace std;
int fibonacci_recurse(int n)
{
	if(n<1)
	{
		return 0;
	}
	if(n==1||n==2)
	{
		return 1;
	}
	return fibonacci_recurse(n-1)+fibonacci_recurse(n-2);
}
int fibonacci_loop(int n)
{
	if(n<1)
	{
		return 0;
	}
	int first=1;
	int second=1;
	int ret=first;
	while(n>2)
	{
		ret=first+second;
		first=second;
		second=ret;
		--n;
	}
	return ret;
}
int fibonacci_recurse_optimized(int n,int first,int second)
{
	if(n<1)
	{
		return 0;
	}
	if(n==1)
	{
		return second;
	}
	else if(n==2)
	{
		return second;
	}
	else {
		int a=0;
		int b=2;
		int c=1;
		int d=3;
		for(;d<n+1;++d)
		{
			a=b+c;
			b=c;
			c=a;
		}
		return a;
	}
}
int main() {
   int n ;
   cin>>n;
   cout<<"Loop"<<n<<":"<<fibonacci_loop(n)<<endl;
   cout<<"Recurse"<<n<<":"<<fibonacci_recurse(n)<<endl;
   cout<<"Recure optimized"<<n<<":"<<fibonacci_recurse_optimized(n,1,1)<<endl;
}