Re: [離散] 遞迴問題請教
從另一個方向下手的話..
假設 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
推
08/11 17:14, , 1F
08/11 17:14, 1F
討論串 (同標題文章)