→ sansia :然後出使條件呢? 08/09 11:17
推 walkwall :不就x1=1 y1=1嗎樓上? 08/09 11:28
→ llewxam :抱歉忘了打@@ 就是樓上說的 08/09 11:52
→ Sfly :這樣太麻煩了 08/09 20:41
※ 引述《sansia (sansia)》之銘言：
: 用遞?關係式表示長度為n，但不包含兩個連續1，的二位元字串的字串總數。
: 請簡短說明如何得出？
: 這個不知道要怎麼迴了
假設
xn: 長度為n，不包含連續1，且結尾0的所有總數
yn: 長度為n，不包含連續1，且結尾1的所有總數
可以寫出兩條遞迴式
xn+1 = xn + yn (1)
代表不管最後一個位數是多少，後面都可以再接0
yn+1 = xn (2)
如果最後一位是1，下一個位數沒辦法再接1
而字串總數就是xn + yn
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.6