Re: [理工] [離散]-遞迴
※ 引述《gn00618777 (123)》之銘言：
: A =2A + n-1 a1=0
: n n/2
: 我是用疊代法去做= =，算的似乎太慢，用特解的列法我不會列 請教教我 謝謝...
中正95第六題對吧,正巧剛剛無聊算了一下
我令n=2^k
則n/2=2^k-1
原式變成→A(k)=2*A(k-1) + 2^k-1
齊次解:A(k) = c*(2^k)
特解:A(k) = d0+d1*k+(d2+d3*k)*2^k
因為d2可以跟齊次解合併,故變成→A(k)=d0+d1*k+d2*k*(2^k)
(上面這句考試我不寫,我直接寫最後↑)
特解之所以這樣令,是因為這題具兩種形式的非齊次解
你知道當非齊次解的部份,若有a^n這種形式要令(d0+d1n)a^n這樣吧
然後每多一次重根就n再多上去這樣
那-1這個部份,你可以看成：-1*1^k
所以特解你可以看成：(d0+d1k)1^k+(d2+d3k)2^k
你有小黃課本的話,他第一種和第二種,這樣就可以想成同一種
只是因為1^k這種在式子裡總是省略
小黃怕我們忘記才會分開(可能吧),但事實上是同一種
代入原式：
d0+d1*k+d2*k*2^k - 2[ d0+d1(k-1)+d2(k-1)2^(k-1) ] = 2^k -1
化簡→-d0-d1*k+2d1+d2*(2^k) = 2^k -1
分作2^k部份、k部份 及 常數部份來解
則d2 = 1,d1=0,d0=1
特解：A(k) = 1+k*(2^k)
整個合併：A(k)=1+c*2^k+k*2^k, n代回,k = log(以2為底)n
→A(n) = 1+c*n+n*log(2底)n
A(1) = 0 = 1+c*1+1*log(2底)1
= 1+c+0 →c=-1
A(n) = 1-n+nlog(2底)n
驗算：A(1) = 1-1+1*0 = 0 正確
A(2) = 2*A(1) +2-1 = 0+1 = 1(原式)
而解出出來的 = 1-2+2*1 = 1 正確
--
為什麼那邊那個人那麼傷心呢? ││││││
因為他是台灣人啊，吃的比我們還毒哩! 2.5ppm ˍ︵ │││ 還好我們
0.5ppm ◥ ◥ 2ppm ╱ ╱▏ ││ 不用吃…
◤ ◥ ◤ ◥ │￣▏ ˍ 0ppm
| | | ╱ ╱ ﹨
◥◢ ￣ （||） ω ╯ ㄦ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.33.45.181
→
03/22 17:46, , 1F
03/22 17:46, 1F
※ 編輯: keepoo 來自: 114.33.45.181 (03/22 17:50)
討論串 (同標題文章)