[理工] [離散] 97政大資科

[cakeboy ()]

http://small.lib.nccu.edu.tw/exam/data/master/cs/cs97.pdf

請問政大資科的證明計算第一題的遞迴

初值我知道s0是1 s1是4

我有找到一個答案是 sn=4 X Sn-1 n>=2

但是這樣s2=16 可是我想長度二的字串

只有aa bb cc dd四種符合的

還是我對這題目了解錯誤呢?

謝謝




--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.171.209
※ 編輯: cakeboy         來自: 61.231.171.209       (11/20 21:14)
推 volleyer:應該是要S(n)=4*S(n-2)喔
→ volleyer:因為迴文的話  第n個決定後第1個也跟著決定  剩中間n-2個
→ volleyer:然後有四種選擇  所以S(n)=4*S(n-2)
→ cakeboy:謝謝,我了解了
推 rockmanray:所以Sn=2^n+(-2)^n 嗎？
→ cakeboy:2^(n+1)+(-2)^(n-1)