2020-04-02 18:25 已编辑华东师范大学算法工程师

关注

具体数学-第2课（成套方法求解递归式）

原文链接：

具体数学-第2课 - WeiYang Blog

今天主要讲了关于递推式和求和的一些方法，主要是成套方法。

约瑟夫环推广

上一节课说到，约瑟夫环问题的解是
$f(n) = 2l + 1$
其中 $n = {2^m} + l$
将 $n$ 写成二进制可以发现， $f(n)$ 就是 $n$ 的二进制循环左移1位。
现在做一下推广，求解如下递推式：
$\begin{array}{l}f(1) = \alpha \\f(2n) = 2f(n) + \beta \\f(2n + 1) = 2f(n) + \gamma \end{array}$
可以设
$f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma$
同样，令 $n = {2^m} + l$
可以解出
$\begin{array}{l}A(n) = {2^m}\\B(n) = {2^m} - 1 - l\\C(n) = l\end{array}$
再从二进制角度理解一下，将递推式继续推广：
$\begin{array}{*{20}{l}}{f(j) = {\alpha _j},1 \le j < d}\\{f(dn + j) = cf(n) + {\beta _j},0 \le j \le d,n \ge 1}\end{array}$
可以得到解为
$f({({b_m}{b_{m - 1}} \ldots {b_1}{b_0})_d}) = {({\alpha _{{b_m}}}{\beta _{{b_{m - 1}}}}{\beta _{{b_{m - 2}}}} \ldots {\beta _{{b_1}}}{\beta _{{b_0}}})_c}$

递推式求和

求解如下递推式：
$\begin{array}{l}{R_0} = \alpha \\{R_n} = {R_{n - 1}} + \beta n + \gamma \end{array}$
用成套方法求解，设
${Rn} = A(n)\alpha + B(n)\beta + C(n)\gamma$
首先令 ${R_n} = 1$ ，可以得到 $\alpha = 1,\beta = 0,\gamma = 0$ ，所以 $A(n) = 1$ 。
再令 ${R_n} = n$ ，可以得到 $\alpha = 0,\beta = 0,\gamma = 1$ ，所以 $C(n) = n$ 。
最后令 ${R_n} = {n^2}$ ，可以得到 $\alpha = 0,\beta = 2,\gamma = - 1$ ，所以 $2B(n) - C(n) = {n^2}$ ，所以 $B(n) = ({n^2} + n)/2$

再来一个更复杂的递推式：
$\begin{array}{l}{R_0} = \alpha \\{R_n} = 2{R_{n - 1}} + \beta n + \gamma \end{array}$
同样的方法，设
${R_n} = A(n)\alpha + B(n)\beta + C(n)\gamma$
首先令 ${R_n} = 1$ ，可以得到 $\alpha = 1,\beta = 0,\gamma = -1$ ，所以 $A(n) - C(n) = 1$ 。
再令 ${R_n} = n$ ，可以得到 $\alpha = 0,\beta = -1,\gamma = 2$ ，所以 $2C(n) - B(n) = n$ 。
这时候能不能令 ${Rn} = {n^2}$ 呢？答案是不能，因为如果 ${R_n} = {n^2}$ ，那么
${n^2} = 2{(n - 1)^2} + \beta n + \gamma$ 显然不可能成立。
观察系数，可以令 ${R_n} = 2^n$ ，可以得到 $\alpha = 1,\beta = 0,\gamma = 0$ ，所以 $A(n) = 2^n$ 。
所以
$A(n) = {2^n},B(n) = {2^{n + 1}} - n + 2,C(n) = {2^n} + 1$

算法码上来文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。

全部评论

推荐最新楼层

不愿透露姓名的神秘牛友

11-29 12:39

华为工作体验

首先，工作强度嘛，因人而异。研发的基本上都是9-11-5的节奏，确实是最累的岗位，但转岗机会也多，激励措施还不错。我咋采购部，相比下来还算轻松。再说说工作氛围，我在不同的小组待过，整体感觉还不错。大部分同事都很和气，大家一起努力，甩锅的现象少。入职培训NEO做得很不错，培训结束后会有导师带你4-6个月，考核也很严格，基本上都能顺利转正。考核压力嘛，确实不小。每半年一次，强制比例分布，13-14级的校招员工升级速度相对快，但供应链的名额少于研发。绩效决定了在华为的发展，大家都很看重KPI，内卷和心理压力也是常态。

华为工作强度 840人发布

点赞评论收藏

分享

昨天 21:36

门头沟学院 Java

感觉现在也有挺多岗位招go的，如果转go能有多一点机会吗？学院本，有一段小厂的java实习

点赞评论收藏

分享

11-21 01:22

门头沟学院测试开发

真。。真扩招吗？

雷总发了个微博，说小米南京扩招，能不能把我扩进去啊

想润的芹菜人狠话不多：把程序员的价格打下来

点赞评论收藏

分享

11-14 08:35

河北地质大学华信学院网络工程师

大佬们帮忙看一下我的简历有问题吗

菜菜咪：1. 可以使用简历网站的模版，美观度会更好一点 2. 邮箱可以重新申请一个，或者用qq邮箱的别名，部分hr可能会不喜欢数字邮箱 3. 项目经历最好分点描述，类似的项目很多，可以参考一下别人怎么写的 4. 自我评价可加可不加，技术岗更看重技术。最后，加油，优秀士兵

点赞评论收藏

分享

不愿透露姓名的神秘牛友

11-26 18:54

秋招基本结束了…

说等下个版本吧的发呆爱好者很贪睡：佬最后去了哪家呀

点赞评论收藏

分享

评论

点赞

收藏

全站热榜

正在热议

# 拼多多求职进展汇总 #

238274次浏览 2041人参与

# ai智能作图 #

30846次浏览 369人参与

# 阿里云管培生offer #

63497次浏览 1764人参与

# 25届秋招总结 #

415173次浏览 4172人参与

# 实习，投递多份简历没人回复怎么办 #

2442470次浏览 34753人参与

# 地方国企笔面经互助 #

7095次浏览 17人参与

# 北方华创开奖 #

67359次浏览 554人参与

# 虾皮求职进展汇总 #

94810次浏览 770人参与

# 我在牛爱网找对象 #

74970次浏览 556人参与

# 机械求职避坑tips #

23910次浏览 250人参与

# 发工资后，你做的第一件事是什么 #

9617次浏览 43人参与

# 我的实习求职记录 #

6136872次浏览 84036人参与

# 25届机械人为了秋招做了哪些准备？ #

26533次浏览 364人参与

# 投格力的你，拿到offer了吗？ #

47569次浏览 337人参与

# 机械人怎么评价今年的华为 #

158133次浏览 1353人参与

# 实习想申请秋招offer，能不能argue薪资 #

36467次浏览 310人参与

# 华为工作体验 #

111975次浏览 867人参与

# 如果再来一次，你还会选择这个工作吗？ #

116996次浏览 1149人参与

# 在职场上，你最讨厌什么样的同事 #

6258次浏览 92人参与

# 国央企笔面经互助 #

88665次浏览 897人参与

# 软开人，秋招你打算投哪些公司呢 #

50035次浏览 588人参与

# 产运销实习日记 #

28288次浏览 326人参与

牛客网
牛客企业服务