s={00,1} ，n長的字串只能由s所組成
請造一遞迴求an
an為長度為n的字串，由s組成的方法數。
想法為下，不知道對不對
字串為2bit時只能是(11)，只有1種，所以a2=1
字串為3bit時只能是(001,100,111)，所以a3=3
字串為4bit時只能是(0000,0011,1100,1001,1111)，所以a4=5
遞迴是這樣 an=an_1 + an_2
a3=3,a4=5,n>=3
還是這樣要 an=an_1 + an_2 + an_3
a2=1,a3=3,a4=5,n>=3
謝謝回答
4 則留言:
考慮最後一個bit
且令An為n個bit由s組成的方法數
若最後一個bit=1
則(An)=(An-1)
若為00
則(An)=(An-2)
2bit時是(11.00)，2種，所以a2=2
3bit時只能是(001,100,111)，所以a3=3
(An)=(An-1)+(An-2)
a2=2.a3=3
解得An=(Fn+1)，n大於等於2
------------------
你的a2好像寫錯了
應該是00跟11
遞迴兩階就夠了
而且要寫成三階的話
你那樣寫
好像也是錯
我也不確定
你參考參考
原來是2bits時少考慮了
感謝愛情絕緣體
那1bit的需要考慮嗎？....
因為S={00,1}
一bit的只有一種...
a1= 1
a2= 2
列出來的也是An = An-1 + An-2
這樣答案就會差在n大於等於1了....
恩 應該要把1bit考慮進去
張貼留言