Re: [理工] [離散] 三元序列
※ 引述《wsx02 ()》之銘言：
: ※ [本文轉錄自 Math 看板 #1H2wHfv1 ]
: 作者: 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參考一下
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 119.14.120.177
推
02/01 19:43, , 1F
02/01 19:43, 1F
→
02/01 20:08, , 2F
02/01 20:08, 2F
推
02/01 22:55, , 3F
02/01 22:55, 3F
推
02/01 23:13, , 4F
02/01 23:13, 4F
推
02/01 23:25, , 5F
02/01 23:25, 5F
→
02/01 23:26, , 6F
02/01 23:26, 6F
推
02/02 14:23, , 7F
02/02 14:23, 7F
推
02/02 21:33, , 8F
02/02 21:33, 8F
討論串 (同標題文章)