作者Honor1984 (奈何上天造化弄人？)
看板Grad-ProbAsk
标题Re: 离散 题库5-59题
时间Tue Jun 18 19:48:33 2019
※ 引述《zxc2179vbnm (多多绿Q)》之铭言：
: https://imgur.com/gallery/wJV96l2
: 请问这题用代入法解的出来吗
: 因为课本详解是用转换法 跟我用代换出来的差蛮多的
这题的问题是a_(n/2)
不能用平常的方式硬套处理
你的代入法是什麽？
令k = log n 其中log是以2为底的对数
=> n = 2^k
则a_n = a_(2^k) = b_k
a_(n/2) = a_(2^(k-1)) = b_(k-1)
所以原递回式可改写为
b_k = 2b_(k-1) + 2^k - 1
接下来就可以用平常解递回的方式处理
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 117.56.175.175 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1560858516.A.EF8.html
1F：→ zxc2179vbnm: 代入法就暴力法展开看规律ㄏㄏ 06/20 10:11
2F：→ zxc2179vbnm: 感谢你的教学 06/20 10:11