如何用模板搭建网站,怎样开公众号,制作网页网站的软件,自助智能建站系统#xff08;一#xff09;Fibonacci数列f[n]f[n-1]f[n-2],f[1]f[2]1的第n项的快速求法#xff08;不考虑高精度#xff09;. 解法#xff1a; 考虑12的矩阵【f[n-2],f[n-1]】。根据fibonacci数列的递推关系#xff0c;我们希望通过乘以一个22的矩阵#xff0c;得到矩阵【…一Fibonacci数列f[n]f[n-1]f[n-2],f[1]f[2]1的第n项的快速求法不考虑高精度. 解法 考虑1×2的矩阵【f[n-2],f[n-1]】。根据fibonacci数列的递推关系我们希望通过乘以一个2×2的矩阵得到矩阵【f[n-1],f[n]】【f[n-1],f[n-1]f[n-2]】 很容易构造出这个2×2矩阵A即 所以有【f[1],f[2]】×A【f[2],f[3]】 又因为矩阵乘法满足结合律故有 【f[1],f[2]】×A n-1【f[n],f[n1]】 这个矩阵的第一个元素即为所求。 至于如何快速求出A n-1相信大家都会即递归地n为偶数时An(A n/2)2n为奇数时An(A n/2)2*A。 问题一解决。 二数列f[n]f[n-1]f[n-2]1,f[1]f[2]1的第n项的快速求法不考虑高精度. 解法 仿照前例考虑1×3的矩阵【f[n-2],f[n-1],1】希望求得某3×3的矩阵A使得此1×3的矩阵乘以A得到矩阵【f[n-1],f[n],1】【f[n-1],f[n-1]f[n-2]1,1】 容易构造出这个3×3的矩阵A即 问题二解决。 三数列f[n]f[n-1]f[n-2]n1,f[1]f[2]1的第n项的快速求法不考虑高精度. 解法 仿照前例考虑1×4的矩阵【f[n-2],f[n-1],n,1】希望求得某4×4的矩阵A使得此1×4的矩阵乘以A得到矩阵 【f[n-1],f[n],n1,1】【f[n-1],f[n-1]f[n-2]n1,n1,1】 容易构造出这个4×4的矩阵A即 问题三解决…… 四数列f[n]f[n-1]f[n-2],f[1]f[2]1的前n项和s[n]的快速求法不考虑高精度. 解法 虽然我们有S[n]F[n2]-1但本文不考虑此方法我们想要得到更一般的方法。 考虑一的矩阵A容易发现我们要求【f[1],f[2]】×AA2A3…AN-1。很多人使用一种很数学的方法构造一个2r*2rr是A的阶数这里为2的矩阵来计算这种方法比较麻烦且很慢这里不再介绍。下面考虑一种新方法。 仿照之前的思路考虑1×3的矩阵【f[n-2],f[n-1],s[n-2]】我们希望通过乘以一个3×3的矩阵A得到1×3的矩阵 【f[n-1],f[n],s[n-1]】【f[n-1],f[n-1]f[n-2],s[n-2]f[n-1]】 容易得到这个3×3的矩阵是 然后…………容易发现这种方法的矩阵规模是(r1)*(r1)比之前流行的方法好得多。 五数列f[n]f[n-1]f[n-2]n1,f[1]f[2]1的前n项和s[n]的快速求法不考虑高精度. 解法 结合三四容易想到…… 考虑1×5的矩阵【f[n-2],f[n-1],s[n-2],n,1】, 我们需要找到一个5×5的矩阵A使得它乘以A得到如下1×5的矩阵 【f[n-1],f[n],s[n-1],n1,1】 【f[n-1], f[n-1]f[n-2]n1,s[n-2]f[n-1],n1,1】 容易构造出A为 然后……问题解决。 一般地如果有f[n]p*f[n-1]q*f[n-2]r*ns 可以构造矩阵A为 q0001p100001000r0100s011更一般的对于f[n]Sigma(a[n-i]*f[n-i])Poly(n)其中0i某常数c, Poly (n)表示n的多项式我们依然可以构造类似的矩阵A来解决问题。 设Degree(Poly(n))d, 并规定Poly(n)0时d-1此时对应于常系数线性齐次递推关系。则本方法求前n项和的复杂度为 ((c1)(d1))3*logn 此方法高效、一般、统一、和谐 转载于:https://www.cnblogs.com/zgmf_x20a/archive/2009/03/21/1418143.html
