【蓝桥杯】斐波那契数列

题目

相信小伙伴们都学过斐波那契数列，它是这样的一个数列： <math> <semantics> <mrow> <mn> 1 </mn> <mo separator="true"> , </mo> <mn> 1 </mn> <mo separator="true"> , </mo> <mn> 2 </mn> <mo separator="true"> , </mo> <mn> 3 </mn> <mo separator="true"> , </mo> <mn> 5 </mn> <mo separator="true"> , </mo> <mn> 8 </mn> <mo separator="true"> , </mo> <mn> 13 </mn> <mo separator="true"> , </mo> <mn> 21 </mn> <mo> ⋯ </mo> </mrow> <annotation encoding="application&#47;x&#45;tex"> 1,1,2,3,5,8,13,21\cdots </annotation> </semantics> </math>1,1,2,3,5,8,13,21⋯。

用 <math> <semantics> <mrow> <msub> <mi> f </mi> <mi> n </mi> </msub> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_n </annotation> </semantics> </math>fn​ 表示斐波那契数列的第 <math> <semantics> <mrow> <mi> n </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> n </annotation> </semantics> </math>n 项，则有： <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> <mo> = </mo> <msub> <mi> f </mi> <mn> 2 </mn> </msub> <mo> = </mo> <mn> 1 </mn> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_1 = f_2 = 1 </annotation> </semantics> </math>f1​=f2​=1， <math> <semantics> <mrow> <msub> <mi> f </mi> <mi> n </mi> </msub> <mo> = </mo> <msub> <mi> f </mi> <mrow> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> <mo> + </mo> <msub> <mi> f </mi> <mrow> <mi> n </mi> <mo> − </mo> <mn> 2 </mn> </mrow> </msub> <mo> ( </mo> <mi> n </mi> <mo> &gt; </mo> <mn> 2 </mn> <mo> ) </mo> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_n = f_{n-1} + f_{n-2} (n &gt; 2) </annotation> </semantics> </math>fn​=fn−1​+fn−2​(n>2)。

输入一个 <math> <semantics> <mrow> <mi> n </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> n </annotation> </semantics> </math>n，求出 <math> <semantics> <mrow> <msub> <mi> f </mi> <mi> n </mi> </msub> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_n </annotation> </semantics> </math>fn​ 对 <math> <semantics> <mrow> <mn> 1000000007 </mn> <mo> ( </mo> <mn> 1 </mn> <msup> <mn> 0 </mn> <mn> 9 </mn> </msup> <mo> + </mo> <mn> 7 </mn> <mo> ) </mo> </mrow> <annotation encoding="application&#47;x&#45;tex"> 1000000007(10^9+7) </annotation> </semantics> </math>1000000007(109+7) 取模结果。

输入格式

输入一个整数 <math> <semantics> <mrow> <mi> n </mi> <mo> ( </mo> <mn> 1 </mn> <mo> ≤ </mo> <mi> n </mi> <mo> ≤ </mo> <mn> 100000 </mn> <mo> ) </mo> </mrow> <annotation encoding="application&#47;x&#45;tex"> n(1 \le n \le 100000) </annotation> </semantics> </math>n(1≤n≤100000)。

输出格式

输入 <math> <semantics> <mrow> <msub> <mi> f </mi> <mi> n </mi> </msub> <mrow> <mi mathvariant="normal"> m </mi> <mi mathvariant="normal"> o </mi> <mi mathvariant="normal"> d </mi> </mrow> <mn> 1000000007 </mn> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_n \mathrm{mod} 1000000007 </annotation> </semantics> </math>fn​mod1000000007 的值。

样例输入

3

样例输出

2

题解

斐波那契数列的规则是

• <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> <mo> = </mo> <msub> <mi> f </mi> <mn> 2 </mn> </msub> <mo> = </mo> <mn> 1 </mn> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_1 = f_2 = 1 </annotation> </semantics> </math>f1​=f2​=1
• <math> <semantics> <mrow> <msub> <mi> f </mi> <mi> n </mi> </msub> <mo> = </mo> <msub> <mi> f </mi> <mrow> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> <mo> + </mo> <msub> <mi> f </mi> <mrow> <mi> n </mi> <mo> − </mo> <mn> 2 </mn> </mrow> </msub> <mo> ( </mo> <mi> n </mi> <mo> &gt; </mo> <mn> 2 </mn> <mo> ) </mo> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_n = f_{n-1} + f_{n-2} (n &gt; 2) </annotation> </semantics> </math>fn​=fn−1​+fn−2​(n>2)

我们用 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_1 </annotation> </semantics> </math>f1​ 存储两项和，前面的一项，用 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 2 </mn> </msub> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_2 </annotation> </semantics> </math>f2​ 存储两项和，后面的一项，所求和用 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_1 </annotation> </semantics> </math>f1​ 存储，由于当前 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_1 </annotation> </semantics> </math>f1​ 相对 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 2 </mn> </msub> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_2 </annotation> </semantics> </math>f2​ 是"后面"的一项了，所以将 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_1 </annotation> </semantics> </math>f1​ 和 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 2 </mn> </msub> </mrow> <annotation encoding="application&#47;x&#45;tex"> f_2 </annotation> </semantics> </math>f2​ 值互换

#include<iostream>
#include<algorithm>
using namespace std;
const int Mod = 1000000007;
int main(){
	int n;
	cin>>n;
	int f1 = 1;
	int f2 = 1;
	for(int i=3;i<=n;i++){
		f1 = (f1+f2)%Mod;
		swap(f1,f2);
	}
	cout<<f2%Mod;
	return 0;
}

返回目录，查看更多