[理工] 遞迴

[VB2005 (DaiJouBu)]

各位好 …

         An = 2A(n/2)+2

         A2=1
                               h    p
         (使用轉換法)  求 An= An + An

         這一題不知道是哪一個觀念不對。怎麼算都錯…

         有人可以算一次給我看嗎？  謝謝。


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.118.253.143
※ 編輯: VB2005          來自: 122.118.253.143      (09/20 12:33)
推 ddczx:An=2A(n/2)+2=4A(n/4)+4+2=8A(n/8)+8+4+2=.....
→ ddczx:=(n/2)A(2)+(n/2)+(n/4)+....+2=n/2+(n/2+2)*(logn-1)/2
→ ddczx:=n/4+logn+nlogn/4-1   (這裡的log都是以2為底)
推 ddczx:我把等比公式寫成等差了,應該是=n/2+2(1-2^(logn-1))/(1-2)
→ ddczx:=(3/2)n-2
→ VB2005:己經知道如何轉成bk=2b(k-1)+2，解完再轉回An了。
→ VB2005:感謝你的回答