Fw: [離散] 三元序列

[suhorng ( )]

※ [本文轉錄自 Math 看板 #1H2wlPMt ]

作者: suhorng ( ) 看板: Math
標題: Re: [離散] 三元序列
時間: Fri Feb  1 19:49:42 2013

dp記結尾

令 a[n][0] 表示長度 n 結尾 0 的個數
   a[n][1]                 1
   a[n][2]                 2

a[1][0] = a[1][1] = a[1][2] = 1

可得

a[n][0] = a[n-1][0] + a[n-1][1] + a[n-1][2]  // 0 隨便接
a[n][1] = a[n-1][0] + a[n-1][2]              // 不可接 1
a[n][2] = a[n-1][0] + a[n-1][1]              // 不可接 2

變數變換一下
令 c[n] := a[n][0] + a[n][1] + a[n][2], 所以

c[n] = a[n][0] + a[n][1] + a[n][2]

     = 3a[n-1][0] + 2a[n-1][1] + 2a[n-1][2]

     = 2c[n-1] + a[n-1][0]

     = 2c[n-1] + c[n-2]

※ 引述《wsx02 ()》之銘言：
: 請問一題今天台大的考題
: 三元n序列 有0,1,2三種字元
: 不包含連續1和連續2的遞迴式
: 為什麼是a(n) = 2a(n-1) + a(n-2)
: //還是  a(n) = a(n-1) + 2a(n-2) ... 我忘記這兩個是哪一個了@@
: 請問應該要怎麼導出來呢?
: 謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.166.47.38
推 zxm20243    :推，好招
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: suhorng (118.166.51.142), 時間: 02/02/2013 22:46:36
推 johnfly2003:漂亮
推 tw00288312:還蠻屌
→ suhorng:雖然不少 DP 的題目可以這樣寫掉(半機械化的過程...)
→ suhorng:不過最後變數變換換回來常常不這麼順利...