培玉 · 一试
一试训练题
F2填空题经典的计数模型
长度5的0-1串中不允许相邻两个1。共有多少串？
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
按末位分成短一位与短两位的合法串。
解答
记n位计数为F(n)。末位0接任意n-1位串；末位1时前一位必须0，接任意n-2位串。F(0)=1、F(1)=2，依次3、5、8、13。 所求为 。
复核
全零串合法，空串作为递推初值恰一种。
方法总结
按末位分成短一位与短两位的合法串。
为什么评为 F2（会透露解法方向）
按末位分成短一位与短两位的合法串。
已记下，谢谢！