作者lovefo (lovefo)
看板Grad-ProbAsk
標題Re: [理工] [離散]-遞迴
時間Mon Mar 22 15:02:55 2010
※ 引述《gn00618777 (123)》之銘言：
: A =2A + n-1 a1=0
: n n/2
: 我是用疊代法去做= =，算的似乎太慢，用特解的列法我不會列 請教教我 謝謝...
像這種遞迴 我都是用特徵方程式 去做
雖然比較慢 但是我比較算的出答案
用疊代法 有時感覺疊不出解答(我實在沒有慧根)
A =2A + n-1 a1=0
n n/2
令n=2^k , k= lg n
A =2A + (2^k) -1
2^k 2^k-1
令B = A
k 2^k
B = 2 B + (2^k) -1 , B = 0
k k-1 0
(h)
B = C * 2^k
k 0
(p)
B = (d k) * 2^k + d 帶回原式
k 1 2
(d n) * 2^k + d = 2 * ((d k) * 2^k + d ) + (2^k) -1
1 2 1 2
化簡一下 得 d = 1
1
d = 1
2
B = C * 2^k + (k) * 2^k + 1
k 0
B = 2C + 1 = 0 , C = -1
0 0 0
B = -1 * 2^k + (k) * 2^k + 1
k
所以: (k = lg n )
A = -n + (lg n * n) + 1 ,n<= 1
n
算到最後都有一點亂了
也不知道對不對 給你參考 參考
--
一切....
似乎不再那麼重要....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.230.14.141
※ 編輯: lovefo 來自: 125.230.14.141 (03/22 15:06)
→ chris750630:好像正確了.. 應該是降啦... 03/22 15:08
推 gn00618777:這個之前我就po過了，回答的也是你= ="，老問題..特解 03/22 15:09
→ gn00618777:那邊不懂位啥要這樣列... 03/22 15:09
→ lovefo:因為我只會這種基本題... 03/22 15:12
推 gn00618777:用疊代法比較慢吧..這種比較快 03/22 15:36
推 flyguava:你初始不是只有B1嗎? 為何是代B0進去??倒數3.4行那 03/22 17:24
※ 編輯: lovefo 來自: 125.230.14.141 (03/22 19:15)