Fibonacci相关题目

请分别设计一个递归和非递归算法来计算F(n)
F列可递归定义为：
n为大于等于0的整数
F(n)=n 当n=0,1,2
F(n)=F(n-1) - F(n-3) 当n>=3

constintMax=1000000;
boolgot[Max];
intgotVal[Max];

intCal(intn)...{
if(got[n])returngotVal[n];
got[n]=1;
returnCal(n-1)-Cal(n-3);
}

intmain()...{
intn;
got[0]=got[1]=got[2]=1;
gotVal[0]=0,gotVal[1]=1,gotVal[2]=2;
while(cin>>n,n>=0&&n<Max)...{
cout<<Cal(n)<<endl;
}
return0;
}

//non-recursive
constintMax=1000000;
intmax;
intF[Max];

intmain()...{
intn;
F[0]=0,F[1]=1,F[2]=2;
while(cin>>n,n>=0&&n<Max)...{
if(n<=max)...{
cout<<F[n]<<endl;
continue;
}
for(inti=max+1;i<=n;i++)F[i]=F[i-1]-F[i-3];
max=n;
cout<<F[n]<<endl;
}
return0;
}