十三师建设局网站,网站 502错误,大连公共资源交易中心,wordpress 4.8.2漏洞[定理1] 标准Fibonacci序列#xff08;即第0项为0#xff0c;第1项为1的序列#xff09;当N大于1时#xff0c;一定有f(N)和f(N-1)互质 其实#xff0c;结合“互质”的定义#xff0c;和一个很经典的算法就可以轻松证明对#xff0c;就是辗转相除法互质的定义就是最大公…[定理1] 标准Fibonacci序列即第0项为0第1项为1的序列当N大于1时一定有f(N)和f(N-1)互质 其实结合“互质”的定义和一个很经典的算法就可以轻松证明对就是辗转相除法互质的定义就是最大公约数为1 数学归纳法是很有用的证明方法我们接下来这个定理用数学归纳法就很好证明[定理2]若i为奇数 f(i)*f(i)f(i-1)*f(i1)1否则f(i)*f(i)f(i-1)*f(i1)-1对这个定理用数学归纳法可以轻松证明大家有兴趣可以自己尝试 [定理3] f(n)f(i)*f(n-i-1)f(i1)*f(n-i) f(n)f(1)*f(n-2) f(2)*f(n-1) f(2)*f(n-3) f(3)*f(n-2) f(3)*f(n-4) f(4)*f(n-3)看来没有错证明方法就是这样 这个公式也可以用来计算较大的fibonacci数除以某个数的余数 设in/2 不过为了保证计算能延续下去 需要每次保留三个值这样下一次计算就可以利用这三个值来求出两个值再相加就可以得到第三个值譬如计算出f(5),f(6),f(7)可以计算出f(11)、f(12)然后推出f(13)就是刚才洛奇的悲鸣(364738334)所提到的矩阵方法我们知道我们若要简单计算f(n)有一种方法就是先保存af(0),bf(1)然后每次设ab bab 并用新的a和b来继续这一运算 如果大家熟悉利用“矩阵”这一工具的话就知道如果把a、b写成一个向量[a,b]完成上述操作相当于乘以矩阵0 11 1也就是说如果我们要求第100个fibonacci数只需要将矩阵[0,1]乘上0 11 1的一百次方再取出第一项 因为我们知道矩阵运算满足结合律一次次右乘那个矩阵完全可以用乘上那个矩阵的N次方代替更进一步那个矩阵的N次方就是这样的形式f(n-1) f(n)f(n) f(n1) 而求矩阵的N次方由于矩阵乘法满足结合律所以我们可以用log(N)的算法求出——这个算法大家都会么一个是二分一个是基于二进制的求幂 二分的原理要求矩阵的N次方A(N)设iN/2若N%21 则 A(N)A(i)*A(i)*A(1)若N%20 则 A(N)A(i)*A(i) 基于二进制的原理将N拆为二进制数譬如131101那么 A^13 A^8 * A^4 * A^1 这里^表示幂运算 也就是说由A^1开始自乘得到A^2然后自乘得到A^4如果N对应位为1则将这个结果乘到目标上去 这样的话将所有乘法改为模乘就可以得到一个较大Fibonacci数除以M的余数 若不用递归其实类似 http://acm.pku.edu.cn/JudgeOnline/problem?id3070这里用的fib矩阵略有不同是f(n1) f(n)f(n) f(n-1)但实际上可以验证效果是一样的 这题是要求求F(n)的最后四位数所有乘法过程增加一个模10000的步骤即可大家可以收藏稍候AC 关于矩阵我们告一段落等下会回来继续探讨利用矩阵来解决复杂些的Fibonacci问题 http://acm.hdu.edu.cn/showproblem.php?pid1568我们来看这题这题要求求出Fibonacci某项的前四位 当然用矩阵也可以解决这道题——只要将乘法改为乘并保留前四位 我们采用double 保留整数部分四位 这题最好还是double吧 不过显然有更好的解法——如果我们知道Fibonacci序列的通项公式 F(n) (((1Sqrt(5))/2)^n - ((1-Sqrt(5))/2)^n)*1/Sqrt(5) 不过组合数学里也有这一公式的推导方法 叫做“线性齐次递推式” 这个解法的核心是通解是某个数的幂 将f(n)x^n代入递推方程可以解出三个通解 0和 (1sqrt(5))/2 通常把“0”称作平凡解那么特解就是通解的某个线性组合 再代入f(0)0 f(1)1就可以得出我们刚才的公式 不过通常情况下我们只需要记住那个公式就可以了 提醒大家记忆公式的时候千万别忘记了系数1/sqrt(5) 因为(1-sqrt(5))/2的绝对值小于1 所以当i较大的时候往往可以忽略掉这一项f(i)≈((1Sqrt(5))/2)^n/sqrt(5); 所以刚才列举出的HDOJ的1568可以很简单的30以内直接求解30以上采用这个公式还是用log(N)求幂的算法求解恩就是公式的前半部分 http://acm.hdu.edu.cn/showproblem.php?pid1021或http://acm.zju.edu.cn/show_problem.php?pid2060Fibonacci某项是否被3整除 [定理5] 标准Fibonacci序列对任意大于2的正整数的余数序列必然是以“0 1”为循环节开头的序列 显然0、1是序列开头也就是说序列开头就是循环节开头 循环长度的计算貌似是个比较难的问题我一时还没有想到有效解法不过要说明的是计算复杂度时这个循环节长度应该按复杂度O(N^2)计算 恩证明方法是利用同余定理、反证法还有我们之前证明过的相邻项一定互质的定理留给大家家庭作业 http://acm.hdu.edu.cn/showproblem.php?pid1588这是前天比赛关于Fibonacci的一道题大家先看看题。Description看后半部分就行了 现在告诉大家一种正确解法然后大家就可以去搞定这道题向别人炫耀了 首先我们将问题整理一下就是对等差数列 aik*ib求所有的f(ai)之和除以M的余数 当0iN 大家有没有想到因为ai是等差数列倘若f(ai)也是个等什么序列那说不定就有公式求了 f(ai)显然不是等差数列直接看上去也不是等比数列 但是如果把f(ai)换成我们刚才所说的Fibonacci矩阵呢 是的可是我们对矩阵是直接求幂即可由于矩阵加法的性质我们要求A^ai的右上角元素之和只要求A^ai之和的右上角元素 就矩阵这个东西来说完全可以看作一个等比数列首项是A^b公比是A^k项数是N 呵呵我们可以把问题进一步简化 因为矩阵的加法对乘法也符合分配律我们提出一个A^b来形成这样的式子A^b*( I A^k (A^k)^2 .... (A^k)^(N-1) ) A^b 和 A^k 显然都可以用我们之前说过的方法计算出来这剩下一部分累加怎么解决呢 简单起见设A^kB要求 G(N)I ... B^(N-1)设iN/2若N为偶数G(N)G(i)G(i)*B^i若N为奇数G(N)I G(i)*B G(i) * (B^(i1)) 呵呵这个方法就是比赛当时ACRush用的而农夫用的则是更精妙的方法大家可想知道 我们来设置这样一个矩阵B IO I其中O是零矩阵I是单位矩阵 将它乘方得到B^2 IBO I乘三方得到B^3 IBB^2O I乘四方得到B^4 IBB^2B^3O I 既然已经转换成矩阵的幂了继续用我们的二分或者二进制法直接求出幂就可以了 http://online-judge.uva.es/p/v110/11089.html大家来读读这一题 Fibinary数是指没有相邻的两个1的二进制数。给N求出第N大的Fibinary数 相对于二进制中每一位的值是2的幂十进制中每一位的值是十的幂Fibonacci进制是每一位的值是对应Fibonacci数的一种计数系统。 8 5 3 2 11 12 1 03 1 0 04 1 0 15 1 0 0 06 1 0 0 17 1 0 1 08 1 0 0 0 09 1 0 0 0 110 1 0 0 1 011 1 0 1 0 012 1 0 1 0 1以上是前12个数字对应的十进制到Fibonacci进制的表格 Fibonacci的运算方法很奇怪。首先它每一位上非0即1而且不同于二进制的逢二进一或者十进制的逢十进一它的进位方法是逢连续两个1则进1 譬如1010110 1011000 110000010000000 在最低位有个特殊情况最低位既可以逢2进1也可以和次低位一起逢相邻进1这种奇怪的进位方法换句话描述就是不存在两个连续的1因为Fibonacci数其实也增长很快int范围内好像只有46个本题只需要用最简单的办法转换成Fibonacii进制即可其中一题是http://www.mydrs.org/program/down/ahoi2004day1.pdf中的第二题叫做数字迷阵还有一题是PKU上的很出名的取石子问题http://acm.pku.edu.cn/JudgeOnline/problem?id1067 这题相当复杂大家可以自己思考往Fibonacci上想也可以阅读这里的论文http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/index.htmlhttp://acm.pku.edu.cn/JudgeOnline/problem?id2967 另外这题 可以利用Fibonacci判断数据范围进行优化设计。不过貌似可以水过去仅仅给大家提供个思路罢 关于Fibonacci和黄金分割还有很多更高明的结论和定理希望大家也继续讨论将自己的知识和他人共享http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/index.html中例3详细讲述了用生成函数来计算Fibonacci数公式的运算过程。http://acm.hdu.edu.cn/showproblem.php?pid1568Fibonacci 求fibonacci前4位 http://acm.hdu.edu.cn/showproblem.php?pid1588Gauss Fibonaccihttp://acm.pku.edu.cn/JudgeOnline/problem?id1067取石子问题http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/index.html 是报告http://acm.pku.edu.cn/JudgeOnline/problem?id3070Fibonacci矩阵http://acm.hdu.edu.cn/showproblem.php?pid1021或http://acm.zju.edu.cn/show_problem.php?pid2060Fibonacci某项是否被3整除http://acm.pku.edu.cn/JudgeOnline/problem?id2116Fibonacci进制计算http://acm.pku.edu.cn/JudgeOnline/problem?id2967利用Fibonacci判断数据范围进行优化设计。http://online-judge.uva.es/p/v110/11089.htmlFi-binary numbersFibonacci进制。http://www.mydrs.org/program/down/ahoi2004day1.pdf第二题 数字迷阵 这些是今天涉及到的资料和网页 转载于:https://www.cnblogs.com/Knuth/archive/2009/09/04/1559951.html
