作者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