经典算法——斐波那契数列

斐波那契数列的经典解法是采用递归的方式：

f(n)=f(n-1)+f(n-2)   n>2

f(1)=1      n=1

f(2)=1      n=2

按照这个思路可以写出递归算法：

#include<iostream>
using namespace std;
int fabonacci(int n){
    if(n==1)
        return 1;
    else
    {
        if(n==2)
            return 1;
        else
            return fabonacci(n-1)+fabonacci(n-2);
    }
}
int main(){
    int number;
    cout<<"请输入一个数字"<<endl;
    cin>>number;
    cout<<fabonacci(number)<<endl;
    return 0;
}      

#include<iostream>
using namespace std;
int main(){
    int number;
    cout<<"请输入一个数字:"<<endl;
    cin>>number;
    int fabonacci[100];
    fabonacci[0]=1;
    fabonacci[1]=1;
    int i;
    for(i=2;i<number;i++)
        fabonacci[i]=fabonacci[i-1]+fabonacci[i-2];
    cout<<fabonacci[number-1]<<endl;
    return 0;
}