作者ooopppeeennn (open)
看板Grad-ProbAsk
標題[問題] 離散數學
時間Sat Apr 11 14:32:35 2009
How many n-digit binary sequences that have no adjacent 0's are
there ?
請教各位高手
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.216.145
1F：推 sasbluesea:Fibonacci 04/11 15:03
2F：推 loveeveryone:n-digit令為Fn 04/11 18:36
3F：→ loveeveryone:分為以下兩種情形 04/11 18:37
4F：→ loveeveryone:最尾巴位元不為0 ----> F n-1 04/11 18:38
5F：→ loveeveryone:尾巴位元為0 ------> F n-2 04/11 18:39
6F：→ loveeveryone:所以 Fn = Fn-1 + Fn-2 04/11 18:40
7F：→ ooopppeeennn:那如果題目把binary改成ternary呢? 04/11 18:55
8F：推 sasbluesea:如果還是只有0不能連續的話應該是F(n)=F(n-1)+2F(n-2) 04/11 22:14