推 victor21835:感謝 果然是好招 05/09 23:53
※ 引述《victor21835 (victor)》之銘言：
: 由於先前po的問題不清楚....(把昨天刪了)
: 所以我打原文po上來
: Suppose a string that contains only 0s, 1s, and 2s is
: called a ternary string, find:
: A recurrence relation for the number of ternary string that do not
: contain two consecutive 0’s or two consecutive 1’s
: 答案的遞迴數列是 a(n)=2*a(n-1)+a(n-2)
: ----------------------------------------
: 我自己的想法
: 若選2開頭 則 沒問題 a(n-1)
: 但選擇 1 or 0開頭 就會卡住
: 應該是三種開頭都討論完 寫成遞迴數列@@
: 如果有哪邊不清楚 可以推文我看到會馬上補
給個參考方法
設x(n),y(n),z(n)表分別為0,1,2開頭的上述數列
所以由定義 x(n)=y(n-1)+z(n-1)
y(n)=x(n-1)+z(n-1)
z(n)=x(n-1)+y(n-1)+z(n-1)
且a(n)=x(n)+y(n)+z(n)= 上三式和 = 2[x(n-1)+y(n-1)+z(n-1)] + z(n-1)
=2a(n-1)+a(n-2)
其中 z(n-1)=a(n-2) 很容易推
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.217.27