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带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。

全部评论

推荐最新楼层

04-07 20:56

蚂蚁集团_后端开发

蚂蚁实习内推—蚂蚁内推码

第一天来到工位的时候闹了个笑话，入职当天每个人工位上都有个新橙子，只有我的已经发霉好多天了，一开始还以为是什么新奇的抹茶橘子，我说大厂就是不一样进入大楼可以看到装修很新很华丽，当然每层也有贴心的空气检验合格报告工位很舒适，入职时配备了一台MacBook Air M3以及一台27寸2K显示器楼内有健身房、篮球场、食堂，还有不定期的小游戏小抽奖。（只是食堂有点小价格有点高东西有点少三天就吃腻了，还好有餐补让人好受些蚂蚁是有点强度的，但是能给的待遇感觉基本拉满了，各种细节，在里面上班会有一种你只要专心做好自己的工作，其他的都不用操心 ，看明年我会给大家分享啥，希望明年还能给大家继续分享...

蚂蚁集团公司福利 178人发布

点赞评论收藏

分享

04-11 17:47

众安集团_测试开发工程师(准入职员工)

银泰百货内推银泰百货内推

杂乱无章说说真实工作感受~感觉银泰这边的氛围真的好养老啊，周围都是90上下的哥哥姐姐们，没有之前实习的公司那么卷 晚饭和小伙伴聚了个餐，比起“百货中心”，我可能更喜欢“mall”目前来看，我的工作强度还不大，按时下班真的爽工作环境超棒，银泰百货的氛围时尚又热闹。很轻松有米拿😌符合现在对工作的一切期待 工位也在非常无人的地方 很自由 爽！不仅公司对百姓福利好 对员工福利和关怀也没得说 每周五公司都有沙龙暖心活动 让大家放松 节假日发个不停的礼金 不卷不pua的职场环境 轻松愉快的工作氛围 真的为阿里银泰点个赞银泰百货2025届校园招聘正式启动关于我们：银泰百货成立于1998年，是一家全面架构在...

银泰百货公司氛围 26人发布

点赞评论收藏

分享

03-25 16:22

南华大学 Java

投简历不是挺轻松的吗，感觉我一天可以投上千个

恶龙战士：招呼语换一下

点赞评论收藏

分享

03-29 18:50

武汉理工大学 Java

27届勇闯实习之被干碎

小厂面经，也是我的处女面（30min）1.自我介绍2.spring boot的自动装配原理（好多类和接口的单词都忘了全称是啥了，就说了记得的单词，流程应该说对了吧）3.有用过redis吗？主要是用在实现什么功能（说了技术派用redis的zset来实现排行榜）5.有了解过Redisson吗？讲一下对于分布式锁的了解以及在什么场景下应用（说了秒杀场景）6.对mysql有了解吗？包括它的索引优化和创建（把想起来的全说了）7.了解设计模式吗？比如单例模式，为什么要使用单例模式，它的优点是什么（昨天刚看的设计模式）8.工厂模式有了解吗？主要的使用场景是？（也是昨天刚看的）9.场景题：有7个服务器，需要在早上十点定时的向数据库中的用户表中的用户发短信，如果做到发送的消息不重复，且如果发送失败了需要知道是到哪个用户失败了，这样下次就直接从这个用户开始（我答了用spring task来实现定时，用分布式锁来保证只有一份服务器可以发送消息，用消息队列来存储消息，然后用消息确认机制来保证错误信息的记录，以及在数据库或者业务层面完成消息消费的幂等性）10.场景题：如果在系统启动的时间就将数据库的所有用户相关的信息都读到一个hashmap中（这个没啥思路，没答好）27届的投了一个星期终于有一个面试了，大部分公司都只招26的

inari233：已oc，拒了

查看9道真题和解析

点赞评论收藏

分享

04-11 17:45

TCL科技集团股份有限公司_AI算法工程师(准入职员工)

TCL内推TCL内推码

体验贴1.TCL实业加不加班? 加班还是有的，但是要看部门，软工、信息部门基本都会加1至2个小时，像我这种人力文职类的，基本都是下班半个小时内就走啦，除非有时特别忙，加班不是强制的，事情做完就可以走。 上下班都需要打卡，不过一个月允许有三次异常哦，不扣工资的！ 2.工资待遇怎么样? 待遇还是挺不错，深圳这边，校招普遍都是10k以上，目前我见过最高的是 18k 3.福利待遇有哪些? 六险一金，还包含商业保险。住房公积金比例是5% 有免费的班车，可以去各个地方，各个时间都有！ 还有免费的健身房，俱乐部（比如羽毛球、瑜伽、舞蹈等等） 深圳TCL园区超级大，里面什么都有，吃饭地方很多，也很便宜 加班到...

TCL公司福利 309人发布

点赞评论收藏

分享

评论

点赞

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 春招进度记录 #

43799次浏览 352人参与

# 打工人的工作餐日常 #

31005次浏览 282人参与

# 实习进度记录 #

44095次浏览 351人参与

# 软开人，说说你的烦心事 #

35184次浏览 221人参与

# 你想吐槽公司的哪些规定 #

11391次浏览 40人参与

# 诺瓦星云求职进展汇总 #

188051次浏览 1620人参与

# 打工人的精神状态 #

38801次浏览 777人参与

# 一觉醒来，秋招难度下降一万倍…… #

60864次浏览 529人参与

# 荣耀求职进展汇总 #

825987次浏览 4668人参与

# 机械制造秋招总结 #

47008次浏览 462人参与

# 机械校招之路总结 #

85260次浏览 1829人参与

# 滴！实习打卡 #

601604次浏览 6391人参与

# 如何KTV领导 #

47318次浏览 373人参与

# 查收我的offer竞争力报告 #

155294次浏览 963人参与

# 参加完秋招的机械人，还参加春招吗？ #

38081次浏览 454人参与

# 研究所笔面经互助 #

62528次浏览 418人参与

# 我在牛爱网找对象 #

167947次浏览 1247人参与

# 秋招感动瞬间 #

18849次浏览 184人参与

# 我在牛客求捞 #

37074次浏览 199人参与

# 工作经验重要还是工资重要？ #

70891次浏览 667人参与

牛客网
牛客企业服务