Re: [離散] recurrence
※ 引述《mqazz1 (無法顯示)》之銘言：
: let Σ = {a,b,c,d}. A palindrome over Σ is a (possibly empty) sequence of
: symbols from Σ such that the sequence is the same as its reverse listing.
: So, for example, aba is a palindrome (of length 3) while aacb is not.
: Now let S(n), n>=0, denote the number of palindromes over Σ of length n
: drive a recurrence relation for S(n) for n>=2
: 請問這要怎麼導呢?
: 謝謝
設 S(n) 為題目中所述 顯然 S(0) = 1、S(1) = 4
接下來，回文有奇數長度與偶數長度的。
若現在是個奇數長度的回文，把最中間的字母砍掉後，剩下的還是回文，
但長度 -= 1；又中間字母無論是 a、b、c、d，砍掉後都形成同一個回文，所以
S(n) = S(n-1)*4，若 n 是奇數
再來偶數長度的回文，把中間兩個字母砍掉任一個會形成奇數長度的回文，所以
S(n) = S(n-1) ，若 n 是偶數
-
只為了解題的話，可以逆推。長度為 m 的字串共有 4^m 個，而若把回文從中切開，
剩下的就是任意字串了。因此有
/ 4^(n/2) ，若 n 是偶數
S(n) = |
\ 4^((n+1)/2)，若 n 是奇數
所以可以得到遞迴式
/ S(n-1)*4，若 n 是奇數
S(n) = |
\ S(n-1) ，若 n 是偶數
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.34.53
推
08/26 20:59, , 1F
08/26 20:59, 1F
→
08/26 22:37, , 2F
08/26 22:37, 2F
→
08/26 22:37, , 3F
08/26 22:37, 3F
討論串 (同標題文章)