# Fibonacci

```定义如下：
F(0) = 0 ,F(1) = 1;
f(n) = F(n-1)+F(n-2)```

# 性质

```1性质一：模除周期性

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)

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) +2```

# Calculate

## 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,递归

```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,递推

```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,分治

```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，矩阵快速幂

```
#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("1\n");
if(N==0)
printf("0\n");
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("%d\n",ans.materix[1][1] ) ;
}
}
return 0;
}```

0 条评论

• ### 树——构造遍历二叉树

构造二叉树，遍历二叉树，先序+中序构造二叉树后序遍历，中序+后序构造二叉树先序遍历。

• ### DFS

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜...

• ### 暑假（补）-5

DFS全称Deep First Search，是一种遍历或搜索树或图的算法。在解决问题上，利用递归调用自身函数（这种说法好像不正确，领悟思想就好了）来实现搜索的...

• ### C# WinForm PropertyGrid用法

关于C# PropertyGrid的用法没有找到，找到一个C++的用法。 模仿着使用了一下，感觉挺不错，分享一下。 基本用法： 拖个PropertyGr...

• ### 如何优雅的使用列表

经常写Python程序的人，列表应该是使用率最高数据结构的了。我们使用列表的过程中，生成列表方式有很多种，哪一种方式性能是最好的呢？可能很多人都没有关心过这个问...

• ### 全球最大的第一视角视频数据集开源，取自真实生活，还能提升厨艺

最近，一个有趣的视频数据集开源了，它不仅能助你研究生涯一臂之力，或许还能提升你的……嗯，厨艺。

• ### Yii2.0实现的批量更新及批量插入功能示例

本文实例讲述了Yii2.0实现的批量更新及批量插入功能。分享给大家供大家参考，具体如下：

• ### 谷歌资助的初创公司VeriFlix开发AI以检测假新闻

假新闻目前已造成了诸多困扰，如果新兴技术加剧了这种情况，那么它也可能会提供补救措施。特别是机器学习可能成为从虚构中分出真相的有力工具。

• ### 一些新旧视频质量评价指标

本文是来自SF VideoTechnology的演讲，演讲作者是 Elecard Group 创始人兼总裁Andrey Pozdnyakov。演讲主要介绍了一些...