如题。
代码如下，vc6.0下编译通过。
#include<iostream>
#include<map>
using namespace std;
int stack = 0; // 记录堆栈的使用情况，每进入一次函数，就加1
map<int,int> m;
//单纯递归
int fibo(int n)
{
++stack;
if(n==1)
return 1;
if(n==2)
return 1;
if(n>2)
return fibo(n-2) + fibo(n-1);
return 0;
}
//利用迭代
int fibo2(int n)
{
++stack;
if(n==1)
return 1;
if(n==2)
return 1;
if(n>2)
{
int first=1,second=1,i=2,result=0;
while(i<n)
{
result = first + second;
first = second;
second = result;
if(++i==n)
return result;
}
}
}
//递归，但保存已经算过的结果，避免重复计算
int fibo3(int n)
{
++stack;
if(n==1)
return 1;
if(n==2)
return 1;
if(n>2)
{
if(m[n]==0)
{
cout<<"m["<<n<<"] does not exist,so create it"<<endl;
return m[n] = fibo3(n-2) + fibo3(n-1);
}
else
{
cout<<"m["<<n<<"] exists!"<<endl;
return m[n];
}
}
return 0;
}
int main()
{
cout<<"enter n:"<<endl;
int n;
cin>>n;
//cout<<"fibo("<<n<<") is "<<fibo(n)<<endl;
//cout<<"fibo("<<n<<") is "<<fibo2(n)<<endl;
cout<<"fibo("<<n<<") is "<<fibo3(n)<<endl;
cout<<"map used: "<<m.size()<<endl;
for(map<int,int>::iterator i=m.begin();i!=m.end();++i)
cout<<i->first<<": "<<i->second<<endl;
cout<<"stack size used: "<<stack<<endl;
}
算到40时，fibo1的表现差劲，近10秒才算出来，其他两个瞬间算出。