三种方法求解斐波那契数列

方法一：递推法

#include<bits/stdc++.h>
using namespace std;

int main(){
    int k;
    cin>>k;
    if(k==1||k==2) cout<<1;
    else{
        int fn,fn_1=1,fn_2=1;
        for(int i=3;i<=k;i++){
            fn=fn_1+fn_2;
			fn_2=fn_1;
            fn_1=fn;
        }
        cout<<fn;
    }
    return 0;
}

方法二：DP+记忆化搜索（防超时）

#include<bits/stdc++.h>
using namespace std;
int dp[50];

int feibo(int x){
	if(x==1 || x==2) dp[x]=1;
    if(!dp[x]) dp[x] = feibo(x-1)+feibo(x-2);
	return dp[x];
}

int main(){
    int k;
    cin>>k;
    cout<<feibo(k);
    return 0;
}

方法三：通项公式

#include<bits/stdc++.h>
using namespace std;

int main(){
    int k;
    cin>>k;
    cout<<round(1.0/sqrt(5)*(pow((1+sqrt(5))/2,k)-pow((1-sqrt(5))/2,k)));
    return 0;
}