斐波那契数列
前言
说实话写本文的时候Chuck心里是很虚的，因为数学是Chuck内心永远的伤。因为当初玩过ACM所以学了些数学相关的算法，斐波那契算法就是其中之一，然而现在这部分已经忘得差不多了。数学功底还不错的可以多看看，实在看不懂的话应该也不会有太大影响，在实际面试中尚未碰到有面试官问斐波那契数列的题。
正文
斐波那契数列都不陌生，该类型的题目在面试中被问到的几率不是很高，但其实现相对简单，在一些对数学有一定要求的企业可能会考到。其大致主要分为以下题型：
1.求具体某项的值（一般在45项以内，打表即可）
2.求具体某一项模K（通常是个大数项，一般采用矩阵法）
3.求斐波那契前几位数字（例如：HDU 的 3117 题）
4.求解 Fibonacci 的后多少位，这个和取模类似
5.求前n项和（矩阵法）
最常用最好用的——矩阵法
矩阵法涉及矩阵运算的实现，对于代码准确性有较高要求，且基于矩阵的斐波那契公式推导可以考验编程者的数学思维。
斐波那契数列
当所求项数很小的时候，一般采用打表法即逐项计算即可，但斐波那契数列增长迅速，对于一般的数列而言，到第50项时数字就已经非常之巨大，因此需要一种更高效的算法来求解。
以HIT OJ 2060为例
Input
The input contains several test cases. Each test case consists of two non-negative integer numbers a and b (0 ≤ a ≤ b ≤1,000,000,000). Input is terminated by a = b = 0.
Output
For each test case, output S mod 1,000,000,000, since S may be quite large.
Sample Input
1 1
3 5
10 1000
0 0
Sample Output
1
16
496035733
题意：给定整数a,b求斐波那契数列第a项到第b项的和，对1,000,000,000取模
进行一波推导
s(n)=s(n-1)+F(n-1)+F(n-2)
{ 0 , 1 , 0 { F(0) { F(1)
1 , 1 , 0 x F(1) = F(2)
0 , 1 , 1 } s(1) } s(2) }
以此类推
{ 0 , 1 , 0 ^n-1 { F(0) { F(n - 1)
1 , 1 , 0 x F(1) = F( n )
0 , 1 , 1 } s(1) } s( n ) }
不信可以自己推推看。
代码实现：
#include <iostream>
#define mod 1000000000
#define max 3
using namespace std;
typedef struct //建立3x3的矩阵
{
long long m[max][max];
}matrix;
matrix p={0,1,0, //按之前推导的定义矩阵p
1,1,0,
0,1,1};
matrix q={1,0,0, //矩阵q为单位阵
0,1,0,
0,0,1};
matrix juzhenchengfa(matrix a,matrix b) //矩阵乘法
{
int i,j,k;
matrix c;
for(i=0;i<max;i++)
{
for(j=0;j<max;j++)
{
c.m[i][j]=0;
for(k=0;k<max;k++)
{
c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;
}
c.m[i][j]=(c.m[i][j]%mod+mod)%mod;
}
}
return c;
}
//矩阵幂运算，数学不好的我选择背模版
matrix quickpow(long long n)
{
matrix a=p,b=q;
while(n>=1)
{
if(n&1) b=juzhenchengfa(a,b);
n>>=1;
a=juzhenchengfa(a,a);
}
return b;
}
int main()
{
long long s,e,sum,sum1;
matrix tmp,tmp1;
while(cin>>s>>e)
{
if(s==0&&e==0) break;
tmp=quickpow(e);
sum=(tmp.m[2][0]+tmp.m[2][1]+2*tmp.m[2][2])%mod;
tmp1=quickpow(s-1);
sum1=(tmp1.m[2][0]+tmp1.m[2][1]+2*tmp1.m[2][2])%mod;
cout<<(sum-sum1)%mod<<endl;
}
}
其实斐波那契数列代码实现最难理解的就是quickpow()函数，对于奇数和偶数的处理略有不同，但代码量并不大，可以考虑背模版记忆。
例2：As we all known , the Fibonacci series : F(0) = 1, F(1) = 1, F(N) = F(N - 1) + F(N - 2) (N >= 2).Now we define another kind of Fibonacci : f(0) = 1 , f(1) = 1 , f(N) = X * f(N - 1) + Y * f(N - 2) (N >= 2).And we want to Calculate S(N) , S(N) = f(0)2 +f(1)2+……+f(n)2.
Input ：There are several test cases. Each test case will contain three integers , N, X , Y, N(2<= N <= 2^31 – 1 X : 2<= X <= 2^31– 1 Y : 2<= Y <= 2^31 – 1 )
Output :For each test case , output the answer of S(n).If the answer is too big , divide it by 10007 and give me the reminder.
其实就是斐波那契公式发生了点变化，这种情况下只需要对原有矩阵进行修改即可：
{ 1 , 1 , 0 , 0, { s(n-1) { s(n) { s(n-1)+f^2(n-1)
0 , x^2 , y^2 , 2*x*y, f^2(n-1) f^2(n) x^2*f^2(n-1)+2*x*y*f(n-1)*f(n-2)+y^2*f^2(n-2)
0 , 1 , 0, 0, x f^2(n-2) = f^2(n-1) = f^2(n-1)
0 , x^2 , 0 , y } f(n-1)*f(n-2) } f(n)*f(n-1)} x^2*f(n-1)+y*f(n-1)*f(n-2) }
#include <iostream>
#include <stdio.h>
#include <cstring>
#define Mod 10007
using namespace std;
const int MAX = 4;
typedef struct
{
int m[MAX][MAX];
} Matrix;
Matrix P={1,1,0,0,
0,0,0,0,
0,1,0,0,
0,0,0,0};
Matrix I={1,0,0,0,
0,1,0,0,
0,0,1,0,
0,0,0,1};
Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法
{
int i,j,k;
Matrix c;
for (i = 0 ; i < MAX; i++)
for (j = 0; j < MAX;j++)
{
c.m[i][j] = 0;
for (k = 0; k < MAX; k++)
c.m[i][j] += (a.m[i][k]* b.m[k][j])%Mod;
c.m[i][j] %= Mod;
}
return c;
}
Matrix quickpow(long long n)
{
Matrix m = P, b = I;
while (n >= 1)
{
if (n & 1)
b = matrixmul(b,m);
n = n >> 1;
m = matrixmul(m,m);
}
return b;
}
int main()
{ int n,x,y,sum;
Matrix b;
while(cin>>n>>x>>y)
{
sum=0;
x=x%Mod;
y=y%Mod;
P.m[1][1]=(x*x)%Mod;
P.m[1][2]=(y*y)%Mod;
P.m[1][3]=(2*x*y)%Mod;
P.m[3][1]=x;
P.m[3][3]=y;
b=quickpow(n);
for(int i=0;i<4;i++)
sum+=b.m[0][i]%Mod;
cout<<sum%Mod<<endl;
}
return 0;
}
