Re: [理工] [離散] 三元序列
※ 引述《k71412 (Mark)》之銘言：
: ※ 引述《wsx02 ()》之銘言：
: : 作者: wsx02 () 看板: Math
: : 標題: [離散] 三元序列
: : 時間: Fri Feb 1 19:17:58 2013
: : 請問一題今天台大的考題
: : 三元n序列 有0,1,2三種字元
: : 不包含連續1和連續2的遞迴式
: : 為什麼是a(n) = 2a(n-1) + a(n-2)
: : //還是 a(n) = a(n-1) + 2a(n-2) ... 我忘記這兩個是哪一個了@@
: : 請問應該要怎麼導出來呢?
: : 謝謝
: 第一個字元為0
: 則後面n-1個不含連續1且不含連續2之字串數為a(n-1)
: 第一個字元為1
: 考慮第二個字元為0或2
: 若為0則後面n-2個個數為a(n-2)
: 若為2，考慮第三個字元為0或為1
: 以此類推
: 最後得a(n-2)+a(n-3)+...+a(1)
: 同理
: 第一個字元為2也是這樣討論
: 所以可以得到a(n)=a(n-1)+2[a(n-2)+a(n-3)+...+a(1)] ---X
: a(n-1)=a(n-2)+2[a(n-3)+a(n-4)+...+a(1)] ---Y
: X-Y => a(n)-a(n-1)=a(n-1)-a(n-2)+2a(n-2)
: a(n)=2a(n-1)+a(n-2)
: 我自己是這樣寫的
: 給原PO參考一下
我的想法是這樣欸不知道對不對
考慮第二個字元是1,第一個可以是2或0,後面接a(n-2)
第二個字元是2,第一個可以是1或0,後面接a(n-2)
第二個字元是0,第一個可以是0或1或2,後面接a(n-2)
所以總共情況是7*a(n-2)
又a(n-1)即為開頭為0或1或2後面接a(n-2),所以a(n-1)=3*a(n-2)
所以7*a(n-2)=2*a(n-1)+a(n-2)
主要是a(n-1)=3*a(n-2)這邊好像有盲點不知道可不可以這樣用 0.0
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.121.32
※ 編輯: tobestronger 來自: 140.113.121.32 (02/02 22:34)
推
02/02 22:42, , 1F
02/02 22:42, 1F
推
02/02 22:49, , 2F
02/02 22:49, 2F
→
02/02 23:26, , 3F
02/02 23:26, 3F
→
02/02 23:26, , 4F
02/02 23:26, 4F
討論串 (同標題文章)