关于斐波那契的一些事
Fibonacci
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因[数学家]列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为兔子数列.
代码语言：javascript复制定义如下：
F(0) = 0 ,F(1) = 1;
f(n) = F(n-1) F(n-2)性质
代码语言：javascript复制1性质一：模除周期性
数列的数模除某个数的结果会呈现一定周期性，因为数列中的某个数取决与前两个数，一旦有连着的两个数的模除结果分别等于第0 第一项的模除结果，那麽代表着一个新的周期的的开始，如果模除n，则每个周期中的元素不会超过n×n;
性质二：黄金分割
随着i的增大F(n) / F(n-1) 接近于0.618
性质三：平方与前后项
从第二项开始，每个奇数项的平方都比前后两项之积多一，每个偶数项的平方比前后两项之积少一.
性质四：
斐波那契数列的第n 2项代表了集合{1，2，...n}中所有不包含相邻正整数的子集的个数.
性质五：求和
F1 F3 F5 F7 .... F(2*n-1) = F(2n) - F(2) F(1)
F2 F4 F6 F8 ... F(2n) = F(2n 1) - F(1)
F1^2 F2^2 F3^2 F4^2 ... Fn^2 = F(n)*F(n-1)
性质六：两倍项关系
F(2n) / F(n) = F(n-1) F(n 1)
性质七：尾数循环
个位数：周期60
最后两位：300
最后三位：1500
其他：
F(n-1) * F(n 1) - F(n)^2 = (-1)^n
F(1) 2F(2) 3F(3) ... nF(n) = nF(n 2) - F(n 3) 2Calculate
1,数学公式计算
double po(double a,int n)
{
for(int i =1;i<=n; i)
a*=a;
return a;
}
double solve1(int n)
{
return 1/sqrt(5)*(po(((1 sqrt(5))/2),n)-po(((1-sqrt(5))/2),n));
}2,递归
代码语言：javascript复制ll solve3(ll n)
{
if(n==0)
return 0;
else if(n==1||n==2)
return 1;
else
{
return solve3(n-1) solve3(n-2);
}
}3,递推
代码语言：javascript复制ll solve2(ll n)
{
F[0] = 0;
F[1] = 1;
F[2] = 1;
if(n==1||n==0||n==2)
return F[n];
else
{
for(ll i =3;i<=n; i)
{
F[i] = F[i-1] F[i-2];
}
return F[n];
}
}4,分治
代码语言：javascript复制ll solve4(ll n)
{
//分治
if(n == 0)
return 0;
if(n==1||n==2)
return 1;
ll first = 0;
ll second = 1;
while(0 < n--)
{
second = first;
first = second - first;
}
return first second;
}4，矩阵快速幂
代码语言：javascript复制
#include <iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int mod=10000;
int f=2;
struct node
{
ll materix[5][5];
};
node mul(node a,node b) //矩阵乘法
{
node res;
memset(res.materix,0,sizeof res.materix);
for(int i=1;i<=f;i )
for(int j=1;j<=f;j )
for(int k=1;k<=f;k )
res.materix[i][j]=(res.materix[i][j] a.materix[i][k]*b.materix[k][j])%mod;
return res;
}
node ksm(node a,ll b)
{
node ans;
memset(ans.materix,0,sizeof ans.materix);
for(int i=1;i<=f;i )
ans.materix[i][i]=1;
while(b)
{
if(b&1)
ans=mul(ans,a);
b>>=1;
a=mul(a,a);
}
return ans;
}
int main()
{
ll N;
while(cin>>N&&N!=-1)
{
if(N==1||N==2)
printf("1n");
if(N==0)
printf("0n");
else
{
node a,b;
a.materix[1][1]=1; a.materix[1][2]=1;
a.materix[2][1]=1; a.materix[2][2]=0; //a是那个幂矩阵，
b.materix[1][1]=1; b.materix[1][2]=0;
b.materix[2][1]=1; b.materix[2][2]=0; //b是最初始的矩阵
node ans = ksm(a ,N-2);
ans = mul(ans ,b) ;
printf("%dn",ans.materix[1][1] ) ;
}
}
return 0;
}
