作者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://www.ptt.cc/bbs/Grad-ProbAsk/M.1560858516.A.EF8.html
→ zxc2179vbnm: 代入法就暴力法展開看規律ㄏㄏ 06/20 10:11
→ zxc2179vbnm: 感謝你的教學 06/20 10:11