Fibonacci

关于斐波那契的一些事

Fibonacci

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因[数学家]列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为兔子数列.

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

性质

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) +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 条评论
登录 后参与评论

相关文章

  • 树——构造遍历二叉树

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

    AngelNH
  • DFS

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

    AngelNH
  • 暑假(补)-5

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

    AngelNH
  • Java——DESUtil加解密工具类

    执笔记忆的空白
  • C# WinForm PropertyGrid用法

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

    静谧的小码农
  • 如何优雅的使用列表

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

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

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

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

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

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

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

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

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

    用户1324186

扫码关注云+社区

领取腾讯云代金券