Re: [理工] [離散]-遞迴
※ 引述《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)
→
03/22 15:08, , 1F
03/22 15:08, 1F
推
03/22 15:09, , 2F
03/22 15:09, 2F
→
03/22 15:09, , 3F
03/22 15:09, 3F
→
03/22 15:12, , 4F
03/22 15:12, 4F
推
03/22 15:36, , 5F
03/22 15:36, 5F
推
03/22 17:24, , 6F
03/22 17:24, 6F
※ 編輯: lovefo 來自: 125.230.14.141 (03/22 19:15)
討論串 (同標題文章)