Re: [理工] 台大電機丙遞迴

[wheniam64 (嘿)]

遞迴這題

我是造一個 {b_n} 數列，其中 b_n = log a_n (以8為底)

這樣就可以轉成：

b_1 = 1, b_2 = 1, b_n = b_{n-1} + 2*b_{n-2}

就變成線性的遞迴惹

接下來解特徵多項式：r^2 - r - 2 = 0

得 r_1 = 2, r_2 = -1

假設 b_n = c*2^n + d*(-1)^n

再代入初值條件解出常數 c = 1/3 和 d = -1/3

而 a_n = 8^{b_n}


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 36.228.111.141
→ ql4au04:一個轉換就變很簡單ＸＤ
→ PTT007:我也是這樣解的，但我log是以2為底
→ carefree1205:我記得以2為底的話轉換後初值比較漂亮
→ wheniam64:請問有考的同學，最後一題chormatic number怎麼寫啊?
→ ql4au04:我利用complete graph 的概念去解 不過我覺得拿不到太多分
→ wheniam64:我也是耶! 但總覺得很難寫出嚴謹的論證
→ LOVEEE5566:這題子嘉筆記有類似的XD
推 divus:chormatic number 在grimaldi section 11.6  exercise 14
→ divus:今天去書店翻課本看到的 XD
→ divus:greedy的方法  max deg=k  任找一點用k+1顏色其中一種去塗
→ divus:然後再找另外一點還沒塗的 因deg<=k 故也可用k+1其中一色
→ divus:不斷重複  直到全部的點塗完