[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

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

智能推荐

WCE Windows hash抓取工具教程_wce.exe -s aaa:win-9r7tfgsiqkf:0000000000000000000-程序员宅基地

文章浏览阅读6.9k次。WCE 下载地址：链接：https://share.weiyun.com/5MqXW47 密码：bdpqku工具界面_wce.exe -s aaa:win-9r7tfgsiqkf:00000000000000000000000000000000:a658974b892e

各种“网络地球仪”-程序员宅基地

文章浏览阅读4.5k次。Weather Globe(Mackiev)Google Earth(Google)Virtual Earth(Microsoft)World Wind(NASA)Skyline Globe(Skylinesoft)ArcGISExplorer(ESRI)国内LTEarth(灵图)、GeoGlobe(吉奥)、EV-Globe(国遥新天地) 软件名称: 3D Weather Globe（http:/_网络地球仪

程序员的办公桌上，都出现过哪些神奇的玩意儿 ~_程序员展示刀,产品经理展示枪-程序员宅基地

文章浏览阅读1.9w次，点赞113次，收藏57次。我要买这些东西，然后震惊整个办公室_程序员展示刀,产品经理展示枪

霍尔信号、编码器信号与电机转向-程序员宅基地

文章浏览阅读1.6w次，点赞7次，收藏63次。霍尔信号、编码器信号与电机转向从电机出轴方向看去，电机轴逆时针转动，霍尔信号的序列为编码器信号的序列为将霍尔信号按照H3 H2 H1的顺序组成三位二进制数，则霍尔信号翻译成状态为以120°放置霍尔为例如不给电机加电，使用示波器测量三个霍尔信号和电机三相反电动势，按照上面所说的方向用手转动电机得到下图① H1的上升沿对应电机q轴与H1位置电角度夹角为0°，..._霍尔信号

个人微信淘宝客返利机器人搭建教程_怎么自己制作返利机器人-程序员宅基地

文章浏览阅读7.1k次，点赞5次，收藏36次。个人微信淘宝客返利机器人搭建一篇教程全搞定天猫淘宝有优惠券和返利，仅天猫淘宝每年返利几十亿，你知道么？技巧分享：在天猫淘宝京东拼多多上挑选好产品后，按住标题文字后“复制链接”，把复制的淘口令或链接发给机器人，复制机器人返回优惠券口令或链接，再打开天猫或淘宝就能领取优惠券啦下面教你如何搭建一个类似阿可查券返利机器人搭建查券返利机器人前提条件1、注册微信公众号(订阅号、服务号皆可)2、开通阿里妈妈、京东联盟、拼多多联盟一、注册微信公众号https://mp.weixin.qq.com/cgi-b_怎么自己制作返利机器人

【团队技术知识分享一】技术分享规范指南-程序员宅基地

文章浏览阅读2.1k次，点赞2次，收藏5次。技术分享时应秉持的基本原则：应有团队和个人、奉献者（统筹人）的概念，同时匹配团队激励、个人激励和最佳奉献者激励；团队应该打开工作内容边界，成员应该来自各内容方向；评分标准不应该过于模糊，否则没有意义，应由客观的基础分值以及分团队的主观综合结论得出。应有心愿单激励机制，促进大家共同聚焦到感兴趣的事情上；选题应有规范和框架，具体到某个小类，这样收获才有目标性，发布分享主题时大家才能快速判断是否是自己感兴趣的；流程和分享的模版应该有固定范式，避免随意的格式导致随意的内容，评分也应该部分参考于此；参会原则，应有_技术分享

随便推点

O2OA开源企业办公开发平台：使用Vue-CLI开发O2应用_vue2 oa-程序员宅基地

文章浏览阅读1k次。在模板中，我们使用了标签，将由o2-view组件负责渲染，给o2-view传入了两个参数：app="内容管理数据"和name="所有信息"，我们将在o2-view组件中使用这两个参数，用于展现“内容管理数据”这个数据应用下的“所有信息”视图。在o2-view组件中，我们主要做的事是，在vue组件挂载后，将o2的视图组件，再挂载到o2-view组件的根Dom对象。当然，这里我们要在我们的O2服务器上创建好数据应用和视图，对应本例中，就是“内容管理数据”应用下的“所有信息”视图。..._vue2 oa

[Lua]table使用随笔-程序员宅基地

文章浏览阅读222次。table是lua中非常重要的一种类型，有必要对其多了解一些。

JAVA反射机制原理及应用和类加载详解-程序员宅基地

文章浏览阅读549次，点赞30次，收藏9次。我们前面学习都有一个概念，被private封装的资源只能类内部访问，外部是不行的，但这个规定被反射赤裸裸的打破了。反射就像一面镜子，它可以清楚看到类的完整结构信息，可以在运行时动态获取类的信息，创建对象以及调用对象的属性和方法。

Linux-LVM与磁盘配额-程序员宅基地

文章浏览阅读1.1k次，点赞35次，收藏12次。Logical Volume Manager，逻辑卷管理能够在保持现有数据不变的情况下动态调整磁盘容量，从而提高磁盘管理的灵活性/boot分区用于存放引导文件，不能基于LVM创建PV（物理卷）：基于硬盘或分区设备创建而来，生成N多个PE，PE默认大小4M物理卷是LVM机制的基本存储设备，通常对应为一个普通分区或整个硬盘。创建物理卷时，会在分区或硬盘的头部创建一个保留区块，用于记录 LVM 的属性，并把存储空间分割成默认大小为 4MB 的基本单元（PE），从而构成物理卷。

车充产品UL2089安规测试项目介绍-程序员宅基地

文章浏览阅读379次，点赞7次，收藏10次。4、Dielecteic voltage-withstand test 介电耐压试验。1、Maximum output voltage test 输出电压试验。6、Resistance to crushing test 抗压碎试验。8、Push-back relief test 阻力缓解试验。7、Strain relief test 应变消除试验。2、Power input test 功率输入试验。3、Temperature test 高低温试验。5、Abnormal test 故障试验。

IMX6ULL系统移植篇-系统烧写原理说明_正点原子 imx6ull nand 烧录-程序员宅基地

文章浏览阅读535次。镜像烧写说明_正点原子 imx6ull nand 烧录