Re: [問題] 解遞?關係式?
※ 引述《pinky94 (pinky)》之銘言：
: 請問87清大資訊的這題要怎麼解遞?關係式?麻煩可以列出詳細的計算過程嗎?
: Let f(n)=2f(n/3)+4 for n = 3^k,k>=1 and f(1)=2,evaluate f(729)
先用定義域轉換
n = 3^k, k = log_3 n
f( 3^k ) = 2f( 3^(k-1) ) + 4
再解線性非齊次式
a_k = 2a_(k-1)+4
a_(k-1) = 2a_(k-2)+4
兩式相減
a_k - 3a_(k-1) + 2a_(k-2) = 0
r^2 - 3r + 2 = 0
(r-2)(r-1)=0
通解為
a_k = c1 x k^0 x 2^k + c2 x k^0 x 1^k
代入f(n) 用消去法 求C1,C2
依題意 a_k = c1 x k^0 x 2^k + c2 x k^0 x 1^k
k=0,n= 3^k = 3^0 =1,f(1)=2,a_k= a_0 = c1 x 0^0 x 2^0 + c2 x 0^0 x 1^0 =2
k=1,n= 3^k = 3^1 =3,f(3)=8,a_k= a_1 = c1 x 1^0 x 2^1 + c2 x 1^0 x 1^1 =8
兩式相減，得
c1=6, c2=-4
f(n)= a_k = (6 x 2^k) - 4 = ( 6 x 2^(log_3 n) ) - 4
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.135.40.31
※ 編輯: meya 來自: 220.136.163.137 (03/10 19:07)
討論串 (同標題文章)