题目描述:
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。
指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……
在数学上，斐波那契数列以如下被以递推的方法定义：
F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
请求出该数列中第n个数字（n从1开始计数）是多少。
递推：
#include <iostream> using namespace std; int main() { int a = 0; int b = 1; // 1 int c = 1; // 2 int n, ans; cin >> n; if(n == 1) ans = 1; else{ for(int i = 2; i <= n; i++){ ans = a + b; a = b; b = ans; } } cout << ans << endl; return 0; }
递归：
#include <iostream> using namespace std; int fn(int n) { //递归出口1 if(n==0) return 0; //递归出口2 else if(n==1 ) return 1; else return fn(n-1)+fn(n-2); //递归关系式 } int main() { int n; //第几个数 int ans; cin>>n; ans=fn(n); cout<<ans<<endl; }
参考：蓝桥杯2022 冲刺班
