Nim游戏，斐波那契数列前20项和求sg值

来源：蜘蛛抓取(WebSpider) 时间：2018-10-02 11:58 标签： 斐波那契数列前20项

[定理1] 标准Fibonacci序列（即第0项为0，第1项为1的序列）当N大于1时，一定有f(N)和f(N-1)互质

其实，结合“互质”的定义，和一个很经典的算法就可以轻松证明

对，就是辗转相除法互质的定义就是最大公约数为1

数学归纳法是很有用的证明方法，我们接下来这个定理用数学归纳法就很好证明：

f(4)*f(n-3)看来没有错，证明方法就是这样

这个公式也可以用来计算较大的fibonacci数除以某个数的余数

设i=n/2 不过，为了保证计算能延续下去 需要每次保留三个值

这样，下一次计算就可以利用这三个值来求出两个值，再相加就可以得到第三个值譬如，计算出f(5),f(6),f(7)，可以计算出f(11)、f(12)，然后推出f(13)就是刚才洛奇的悲鸣()所提到的矩阵方法我们知道我们若要简单计算f(n)，有一种方法就是先保存a=f(0),b=f(1)，然后每次设：a'=b

并用新的a'和b'来继续这一运算

如果大家熟悉利用“矩阵”这一工具的话，就知道，如果把a、b写成一个向量[a,b]，完成上述操作相当于乘以矩阵

1的一百次方，再取出第一项

因为我们知道，矩阵运算满足结合律，一次次右乘那个矩阵完全可以用乘上那个矩阵的N次方代替，更进一步，那个矩阵的N次方就是这样的形式：

而求矩阵的N次方，由于矩阵乘法满足结合律，所以我们可以用log(N)的算法求出——这个算法大家都会么？
一个是二分，一个是基于二进制的求幂

也就是说，由A^1开始，自乘得到A^2，然后自乘得到A^4，如果N对应位为1，则将这个结果乘到目标上去

这样的话，将所有乘法改为模乘，就可以得到一个较大Fibonacci数除以M的余数


这里用的fib矩阵略有不同，是

这题是要求求F(n)的最后四位数，所有乘法过程增加一个模10000的步骤即可，大家可以收藏稍候AC

关于矩阵我们告一段落，等下会回来继续探讨利用矩阵来解决复杂些的Fibonacci问题


我们来看这题，这题要求求出Fibonacci某项的前四位

当然，用矩阵也可以解决这道题——只要将乘法改为乘并保留前四位

我们采用double 保留整数部分四位 这题最好还是double吧

不过显然有更好的解法——如果我们知道Fibonacci序列的通项公式

不过组合数学里也有这一公式的推导方法 叫做“线性齐次递推式”

这个解法的核心是，通解是某个数的幂 将f(n)=x^n代入递推方程，可以解出三个通解 0和 (1+sqrt(5))/2

通常把“0”称作平凡解，那么特解就是通解的某个线性组合

再代入f(0)=0 f(1)=1，就可以得出我们刚才的公式

不过通常情况下，我们只需要记住那个公式就可以了

提醒大家，记忆公式的时候千万别忘记了系数1/sqrt(5)

所以，刚才列举出的HDOJ的1568，可以很简单的30以内直接求解，30以上采用这个公式，还是用log(N)求幂的算法求解
恩，就是公式的前半部分

[定理5] 标准Fibonacci序列对任意大于2的正整数的余数序列，必然是以“0 1”为循环节开头的序列

显然0、1是序列开头，也就是说序列开头就是循环节开头

循环长度的计算貌似是个比较难的问题，我一时还没有想到有效解法，不过，要说明的是，计算复杂度时，这个循环节长度应该按复杂度O(N^2)计算

恩，证明方法是利用同余定理、反证法，还有我们之前证明过的相邻项一定互质的定理，留给大家家庭作业


这是前天比赛关于Fibonacci的一道题，大家先看看题。

现在告诉大家一种正确解法，然后大家就可以去搞定这道题向别人炫耀了

首先，我们将问题整理一下，就是对等差数列 ai=k*i+b，求所有的f(ai)之和除以M的余数

大家有没有想到，因为ai是等差数列，倘若f(ai)也是个等什么序列，那说不定就有公式求了

f(ai)显然不是等差数列，直接看上去也不是等比数列

但是如果把f(ai)换成我们刚才所说的Fibonacci矩阵呢？

是的，可是我们对矩阵是直接求幂即可，由于矩阵加法的性质，我们要求A^ai的右上角元素之和，只要求A^ai之和的右上角元素

就矩阵这个东西来说，完全可以看作一个等比数列，

首项是：A^b公比是：A^k项数是：N

呵呵，我们可以把问题进一步简化

A^b 和 A^k 显然都可以用我们之前说过的方法计算出来，这剩下一部分累加怎么解决呢

简单起见，设A^k=B

呵呵，这个方法就是比赛当时ACRush用的
而农夫用的则是更精妙的方法，大家可想知道

我们来设置这样一个矩阵

B IO I其中O是零矩阵，I是单位矩阵

既然已经转换成矩阵的幂了，继续用我们的二分或者二进制法，直接求出幂就可以了

Fibinary数是指没有相邻的两个1的二进制数。给N，求出第N大的Fibinary数

相对于二进制中每一位的值是2的幂，十进制中每一位的值是十的幂，

1以上是前12个数字对应的十进制到Fibonacci进制的表格

Fibonacci的运算方法很奇怪。首先，它每一位上非0即1，而且不同于二进制的逢二进一或者十进制的逢十进一，它的进位方法是逢连续两个1，则进1

在最低位有个特殊情况，最低位既可以逢2进1，也可以和次低位一起逢相邻进1

这种奇怪的进位方法，换句话描述就是，不存在两个连续的1因为Fibonacci数其实也增长很快，int范围内好像只有46个，本题只需要用最简单的办法转换成Fibonacii进制即可其中一题是


中的第二题，叫做数字迷阵

还有一题是PKU上的很出名的取石子问题

这题相当复杂，大家可以自己思考，往Fibonacci上想，也可以阅读这里的论文：

另外这题 可以利用Fibonacci判断数据范围进行优化设计。不过貌似可以水过去，仅仅给大家提供个思路罢

关于Fibonacci和黄金分割，还有很多更高明的结论和定理，希望大家也继续讨论，将自己的知识和他人共享

中例3详细讲述了用生成函数来计算Fibonacci数公式的运算过程。Fibonacci


从1到n列出一堆石子所有可能的情况，在搜索小于这个i的所有斐波那契数,标记当前 i 减去斐波那契数产生子局面
的SG值，之后得到当前n的SG值

我要回帖

更多关于 斐波那契数列前20项 的文章

 

随机推荐