[zZ]常见递推关系解法 _递推关系有哪些解法-程序员宅基地

技术标签：转载 c

常见递推关系解法

1.  a[n+1]=a[n]+f(n)  ->  a[n]=a[1]+sum(f(k) |1<=k<n)
移项后叠加：a[n]=a[1]+sum(f(k) |1<=k<n)

2．a[n+1]=a[n]*f(n)  ->  a[n]=a[1]*mul(f(k) | 1<=k<n)
移项后叠乘：a[n]=a[1]*mul(f(k) | 1<=k<n)

3．a[n+1]=p*a[n]+q  ->  a[n]=a[1] + (a[2]-a[1])*(1- p^(n-1))/(1-p)
  相减得(a[n+1]-a[n])=p*(a[n]-a[n-1])，即b[n+1]=p*b[n];
  所以a[n+1]-a[n]=(a[2]-a[1])*p^n
  移项叠加得a[n] = a[1] + sum(a[k]-a[k-1] | 1<k<=n)
= a[1] + (a[2]-a[1])*(1- p^(n-1))/(1-p);

4．a[n+1]=p*a[n]+q(n)  ->  a[n]= ( a[1]/p + sum(q(k)/p^(k+1)) )*p^(n+1)
  两边除p^(n+1)得，a[n+1]/p^(n+1) = a[n]/p^n + q(n)/p^(n+1)
即b[n+1]=b[n]+q(n)/p^(n+1)，
形式同1，可解得：b[n]=b[1]+sum(q(k)/p^(k+1) | 1<=k<n)
所以a[n]=b[n]*p^(n+1);

5．a[n+1]=p(n)*a[n]+q(n)  ->  a[n]=(a[1]*f(1)+sum(q(k)/f(k+1))) / f(n)
令p(n)=f(n)/f(n+1)，则a[n+1]*f(n+1)=a[n]*f(n)+q(n)*f(n+1)
即b[n+1]=b[n]+q(n)*f(n+1)，形式同1。
可解得b[n]=b[1]+sum(q(k)/f(k+1))，a[n]=b[n]/f(n)
即a[n]=(a[1]*f(1)+sum(q(k)/f(k+1))) / f(n)

6．线性齐次递推关系(如a[n]=a[n-1]+2*a[n-2]+a[n-1])
  ①给出相应的特征方程(如x^3 - x^2 - 2*x - 1=0)，求解特征方程得到根h1,h2..
  ②如果没有重根，则直接代入初始条件解
a[n]=c1*(h1^n)+c2*(h2^n)+c3*(h3^n)+…的常数c1,c2,c3….可得通项公式。
  ③若有重根，比如h2=h3=h4≠h1，则——
a[n]=c1*(h1^n)+c2*(h2^n)+c3*n*(h3^n)+c4*(n^2)*(h4^n)，代入初始条件解出常数c1,c2…，可得通项公式。

7．当然也可以用矩阵乘法来logN解线性齐次递推关系：
对于a[n]=k1*a[n-1]+k2*a[n-2]+k3*a[n-4]，构造矩阵G
0  1  0  0
0  0  1  0
0  0  0  1
K3 0  k2  k1
在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。
最后An=A0*G^n为结果矩阵(A0为初始矩阵)

不过更多时候遇到的会是更复杂的递推关系，这时需要的是通过换元，待定系数构造，周期性甚至猜想，数学归纳等等方式技巧来灵活处理。
当然数据规模不太大的，或者递推关系增长很快的情况下也可以直接打表递推，不一定非要解出通项公式，事实上ACM中很多题都是这样。

作者：pumpkinsm@Pumpkin's
地址：http://ppksm.com/blog/read.php?158
欢迎转载，转载时请以链接形式注明作者和原始出处。=v=

本文链接：https://blog.csdn.net/muye67/article/details/6008102

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

【史上最易懂】马尔科夫链-蒙特卡洛方法：基于马尔科夫链的采样方法，从概率分布中随机抽取样本，从而得到分布的近似_马尔科夫链期望怎么求-程序员宅基地

文章浏览阅读1.3k次，点赞40次，收藏19次。虽然你不能直接计算每个房间的人数，但通过马尔科夫链的蒙特卡洛方法，你可以从任意状态（房间）开始采样，并最终收敛到目标分布（人数分布）。然后，根据一个规则（假设转移概率是基于房间的人数，人数较多的房间具有较高的转移概率），你随机选择一个相邻的房间作为下一个状态。比如在巨大城堡，里面有很多房间，找到每个房间里的人数分布情况（每个房间被访问的次数），但是你不能一次进入所有的房间并计数。但是，当你重复这个过程很多次时，你会发现你更有可能停留在人数更多的房间，而在人数较少的房间停留的次数较少。_马尔科夫链期望怎么求

linux以root登陆命令,su命令和sudo命令，以及限制root用户登录-程序员宅基地

文章浏览阅读3.9k次。一、su命令su命令用于切换当前用户身份到其他用户身份，变更时须输入所要变更的用户帐号与密码。命令su的格式为：su [-] username1、后面可以跟 ‘-‘ 也可以不跟，普通用户su不加username时就是切换到root用户，当然root用户同样可以su到普通用户。 ‘-‘ 这个字符的作用是，加上后会初始化当前用户的各种环境变量。下面看下加‘-’和不加‘-’的区别：root用户切换到普通..._限制su root登陆

精通VC与Matlab联合编程（六）_精通vc和matlab联合编程六-程序员宅基地

文章浏览阅读1.2k次。精通VC与Matlab联合编程（六）作者：邓科下载源代码浅析VC与MATLAB联合编程浅析VC与MATLAB联合编程浅析VC与MATLAB联合编程浅析VC与MATLAB联合编程浅析VC与MATLAB联合编程　　Matlab C/C++函数库是Matlab扩展功能重要的组成部分,包含了大量的用C/C++语言重新编写的Matlab函数,主要包括初等数学函数、线形代数函数、矩阵操作函数、数值计算函数_精通vc和matlab联合编程六

Asp.Net MVC2中扩展ModelMetadata的DescriptionAttribute。-程序员宅基地

文章浏览阅读128次。在MVC2中默认并没有实现DescriptionAttribute（虽然可以找到这个属性，通过阅读MVC源码，发现并没有实现方法），这很不方便，特别是我们使用EditorForModel的时候，我们需要对字段进行简要的介绍，下面来扩展这个属性。新建类 DescriptionMetadataProvider然后重写DataAnnotationsModelMetadataPro..._asp.net mvc 模型description

领域模型架构 eShopOnWeb项目分析上-程序员宅基地

文章浏览阅读1.3k次。一.概述　　本篇继续探讨web应用架构，讲基于DDD风格下最初的领域模型架构，不同于DDD风格下CQRS架构，二者架构主要区别是领域层的变化。架构的演变是从领域模型到C..._eshoponweb

Springboot中使用kafka_springboot kafka-程序员宅基地

文章浏览阅读2.6w次，点赞23次，收藏85次。首先说明，本人之前没用过zookeeper、kafka等，尚硅谷十几个小时的教程实在没有耐心看，现在我也不知道分区、副本之类的概念。用kafka只是听说他比RabbitMQ快，我也是昨天晚上刚使用，下文中若有讲错的地方或者我的理解与它的本质有偏差的地方请包涵。此文背景的环境是windows，linux流程也差不多。官网下载kafka，选择Binary downloads Apache Kafka 解压在D盘下或者什么地方，注意不要放在桌面等绝对路径太长的地方打开conf_springboot kafka

随便推点

VS2008+水晶报表发布后可能无法打印的解决办法_水晶报表不能打印-程序员宅基地

文章浏览阅读1k次。编好水晶报表代码,用的是ActiveX模式,在本机运行,第一次运行提示安装ActiveX控件,安装后,一切正常,能正常打印,但发布到网站那边运行,可能是一闪而过,连提示安装ActiveX控件也没有,甚至相关的功能图标都不能正常显示,再点"打印图标"也是没反应解决方法是: 1.先下载"PrintControl.cab" http://support.businessobjects.c_水晶报表不能打印

一. UC/OS-Ⅱ简介_ucos-程序员宅基地

文章浏览阅读1.3k次。绝大部分UC/OS-II的源码是用移植性很强的ANSI C写的。也就是说某产品可以只使用很少几个UC/OS-II调用，而另一个产品则使用了几乎所有UC/OS-II的功能，这样可以减少产品中的UC/OS-II所需的存储器空间（RAM和ROM）。UC/OS-II是为嵌入式应用而设计的，这就意味着，只要用户有固化手段（C编译、连接、下载和固化）， UC/OS-II可以嵌入到用户的产品中成为产品的一部分。1998年uC/OS-II，目前的版本uC/OS -II V2.61，2.72。1.UC/OS-Ⅱ简介。_ucos