🎉️ 程序设计-斐波那契数列

Question

小明最近学习了斐波那契数列。

斐波那契数列是指这样的数列：数列的第一个和第二个数都为 1，接下来每个数都等于前面 2个数之和。

给出一个正整数 k，要求斐波那契数列中第 k个数是多少。

输入格式
输入一行，包含一个正整数 k。（1≤k≤46）

输出格式
输出一行，包含一个正整数，表示斐波那契数列中的第 kk 个数。

输入样例
19
输出样例
4181

Answer 1

用递归方式解决，f(n)=f(n-1)+f(n-2)

#include<iostream> 
#include<stdio.h>
using namespace std;
 
//Fibonacci数列递归解法 C++ 实现
int Fib(int n) 
{
    if(n==1) 
        return 1;
    else if(n==2)
        return 1;
    else
        return Fib(n-1)+Fib(n-2);
}
int main()
{
    int k;
    cin>>k;
    cout<<Fib(k)<<endl;
    return 0;
}