從另一個方向下手的話.. 假設 c_n 是長度n, 結尾為1,2,3之一的數的個數 d_n 是長度n, 結尾為0的數的個數 得 a_n = c_n + d_n, c_1 = 3, d_1 = 1 c_n = 3c_{n-1} + 2d_{n-1} //c可以再接1,2,3 d只能接1,2 d_n = c_{n-1} + d_{n-1} //結尾接0 然後...想辦法化簡\囧/ d_n = c_{n-1} + d_{n-1} = a_{n-1} c_n = 3(c_{n-1} + d_{n-1}) - d_{n-1} = 3a_{n-1} - a_{n-2} 最後終於 a_n = c_n + d_n = 4a_{n-1} - a_{n-2} - 以上繞了一圈 對不起 從比較數學的想法的話... a_n 是長度 n 且 0 後面不接 3 的數的個數 所以 a_n = 4a_{n-1} - a_{n-2} 不管前一個結尾是什麼 但是0後面的不能接3 總之0,1,2,3全部亂接 所以就是扣掉長度n-2的接0 如果有學程式的話,可以多看一些Dynamic Programming的問題幫助思考 不過寫程式很多情況下是直接分 case 討論...有時候不容易化成簡單的遞迴式 ※ 引述《metalalive (想玩音樂)》之銘言： : Let a_n be the number of n-digit quaternary {0,1,2,3} sequances : in which there is never a 3 immediately to the right of a 0 : find a recurrence relation for a_n : 這題是說 0後面不可以接3 : ex. : 033 <--- invalid : 013 <--- valid : 這樣對嗎? : 如果是 : 不知道這題要怎麼思考它的情況 @@ : 感激不盡 : 對遞迴的觀念真的非常弱 : 常常題目條件一變換就解不出來了 : 不知有無有效的練習方式? : 謝謝 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.217.34.87