斐波那契数列
2014年蓝桥杯本科C/C++组预赛第9题是很好的一道关于斐波那契(Fibonacci)数列的题目。本文将从这一题目出发,探讨一些与斐波那契数列相关的性质。
题目
题目链接:斐波那契 http://lx.lanqiao.org/problem.page?gpid=T121
题目内容:
问题描述
斐波那契数列大家都非常熟悉。它的定义是:
对于给定的整数
公式如下:
但这个数字依然很大,所以需要再对
- 输入格式 输入为一行用空格分开的整数 n m p (
) - 输出格式 输出为1个整数,表示答案
- 样例输入
2 3 5
- 样例输出
0
- 样例输入
15 11 29
- 样例输出
25
Fibonacci数列
通过递推式和特征方程,不难得到Fibonacci数列的通项公式为:
根据Fibonacci数列的递推关系,可以使用矩阵乘法的方法来在O(log n)的时间复杂度内求得Fibonacci数列的第 n 项的值。具体算法:
Fibonacci数列有很多很有用的性质,首先根据Fibonacci数列的递推关系,有:
那么,由此得到:
从这个等式可以推出:
这个性质非常重要,通过这个性质,可以将Fibonacci数列前
与上式同理,不难得到:
此外,Fibonacci数列还有以下这些有用的性质:
常用的还有下列结论:
由上式稍作变换,便有
这两个公式都可以通过数学归纳法证明。
题目分析
通过上面的Fibonacci数列前N项求和公式,可以将原来的问题简化成
因此,当
那么对于本题呢?题目中
上文中,我们已经将问题规约为求解
如果
结合前面提到了快速幂模的方法,这个问题是容易的。我们还有以下结论(推导过程参见文末参考 2):
- 当
为奇数时, - 当
为偶数时,
-
如果
为偶数,那么如果 和 都是偶数,那么结果应该是: -
如果
为奇数,那么:- 如果
和 都是偶数,那么结果应该是: - 如果
是偶数, 是奇数,那么结果应该是: - 如果
是奇数, 是偶数,那么结果应该是:- 如果
是奇数,结果为 - 如果
是偶数,结果为
- 如果
- 如果
和 都是奇数,那么结果应该是:- 如果
是奇数,结果为 - 如果
是偶数,结果为
- 如果
- 如果
-
如果 m 是偶数,那么:
- 如果
是奇数,那么结果应该是:- 如果
是奇数,结果为 - 如果
是偶数,结果为
- 如果
- 如果
是偶数,那么结果应该是:
- 如果
至此,本题基本解决完毕。
其他的细节
这道题的数据量非常大,因此在其他的一些地方也应该充分注意,才有可能通过全部测试点。
- 使用矩阵快速幂模来求解某一项的值。
- 64位整数的二进制分解乘法(
long long
乘以long long
会导致溢出)。
long long multiply(long long a, long long b) {
long long ans = 0;
a %= MOD;
while(b) {
if(b & 1) {
ans = (ans + a) % MOD;
b--;
}
b >>= 1;
a = (a + a) % MOD; // a *= 2
}
return ans;
}
题目Accept代码:PREV_29.cpp
Fibonacci另一种快速算法
在http://www.zhihu.com/question/29215494看到了另一种基于分治的Fibonacci数列第n项的方法:
double Fibonacci(int n){
double x = 1.0, y = 1.0, a = 0, b = 1.0,t;
while (n>0)
{
if (n & 1){
t = a*x + b*y;
a = x*(b - a) + a*y;
b = t;
}
t = 2 * x*y - x*x;
y = x*x + y*y;
x = t;
n >>= 1;
}
return a;
}
关于该算法的解释如下图所示: