递归算Fibonacci是个基础的东西……
这个代码在递归时使用了记忆化搜索,提高了效率。
以及,用Fib(n)=Fib(n+2)-Fib(n+1)定义了斐波那契数列的“负数项”,
通过性质Fib(-n)=(-1)^(n+1)*Fib(n)来算出负数项的斐波那契数。
#include<iostream>
#include<memory.h>//memset函数
using namespace std;
int FIB[1024];
int fib(int n)
{
if(n>2) return FIB[n]==-1?FIB[n]=fib(n-1)+fib(n-2):FIB[n];
else if(n<-2) return (2*((-n)%2)-1)*(fib(-n));
else return 1;
}
int main()
{
int n;
memset(FIB,-1,(sizeof(int))*1024);
FIB[1]=FIB[2]=1;
while(1)
{
cout<<"n=";
cin>>n;
cout<<"fib("<<n<<")="<<fib(n)<<endl;
}
return 0;
}