专栏首页算法码上来具体数学-第2课(成套方法求解递归式)

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

原文链接:

具体数学-第2课 - WeiYang Bloggodweiyang.com

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

约瑟夫环推广

上一节课说到,约瑟夫环问题的解是

其中

写成二进制可以发现,

就是

的二进制循环左移1位。 现在做一下推广,求解如下递推式:

可以设

同样,令

可以解出

再从二进制角度理解一下,将递推式继续推广:

可以得到解为

递推式求和

求解如下递推式:

用成套方法求解,设

首先令

,可以得到

,所以

。 再令

,可以得到

,所以

。 最后令

,可以得到

,所以

,所以

再来一个更复杂的递推式:

同样的方法,设

首先令

,可以得到

,所以

。 再令

,可以得到

,所以

。 这时候能不能令

呢?答案是不能,因为如果

,那么

显然不可能成立。 观察系数,可以令

,可以得到

,所以

。 所以

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 具体数学-第11课(Stern-Brocot树和同余关系)

    开始走到它所在的结点。如果向左走就记为L,向右走记为R,最终可以得到一个L和R的序列。例如

    godweiyang
  • 【每日算法Day 86】面试经典题:把数字翻译成字符串

    给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有...

    godweiyang
  • 【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分

    移动是指选择任一行或列,并转换该行或列中的每一个值:将所有 都更改为 ,将所有 都更改为 。

    godweiyang
  • SSRF(服务器请求伪造)

    SSRF(Server-Side Request Forgery,服务器请求伪造)是一种由攻击者构造请求,由服务端发起请求的安全漏洞,一般情况下...

    Aran
  • 实时音视频SDK迎来最新的 6.8 版本

    腾讯实时音视频=TRTC,全称Tencent Real-Time Communication。拥有QQ十几年来在音视频技术上的积累,致力于帮助企业快速搭建低成...

    腾讯即时通信IM
  • 设计模式初探-代理模式

    是什么 代理模式是为一个对象提供一个代用品或占位符,以便控制对它的访问。 生活是一切东西的起源,在生活中也到处能看到代理模式的影子。 明星有经纪人作为代理,要联...

    IMWeb前端团队
  • 设计模式初探-代理模式

    生活是一切东西的起源,在生活中也到处能看到代理模式的影子。 明星有经纪人作为代理,要联系明星的档期其实是和经纪人联系,经纪人联系好之后,再有明星负责签约、演出。

    IMWeb前端团队
  • C#微信公众平台接入示例代码

    http://mp.weixin.qq.com/wiki/17/2d4265491f12608cd170a95559800f2d.html

    FreeTimeWorker
  • Spy Banker木马新变种Telax利用谷歌云服务器进行传播

    安全公司Zscaler发现一种新型恶意活动,它基于一种新型的Spy Banker网银恶意软件Telax,利用谷歌云服务器来驻留木马下载器,且主要通过社交媒体平台...

    FB客服
  • mac 在 home 目录下创建文件夹

    编译 /etc/auto_master 文件,注释掉或者移除以 /home 开头的那一行,保存。

    一个会写诗的程序员

扫码关注云+社区

领取腾讯云代金券