※ 引述《maque (Que)》之铭言：
: 题目 http://ppt.cc/kNJC
: 小黄课本上有写解答
: 但无法理解部分观念
: 解答:http://ppt.cc/5ixl
: 若开始为0,则有an-1个方法
: 开始部分为什么不讨论为1
他是先讨论含5个连续1的情况
因为含5个连续0与含5个连续1的情况是相同的
所以只要讨论其中一种情况最后再乘以2倍即可
: 接下来讨论若开始为10则有an-2个
: 这部分为什么不讨论00、01、11的情况?
如果你现在想讨论的是含5个连续1的情况，则讨论的顺序会是：
0xxx...、10xxx...、110xxx...、1110xxx...、11110xxx...、11111xxx...
以下图解说明：
假设an表示含5个连续1个方法数
┌─┐┌─────────────────┐
│0 ││ an-1 │=> 剩(n-1)个数要含5个连续1
└─┘└─────────────────┘
┌─┐┌─┐┌──────────────┐
│1 ││0 ││ an-2 │=> 剩(n-2)个数要含5个连续1
└─┘└─┘└──────────────┘
┌─┐┌─┐┌─┐┌───────────┐
│1 ││1 ││0 ││ an-3 │=> 剩(n-3)个数要含5个连续1
└─┘└─┘└─┘└───────────┘
┌─┐┌─┐┌─┐┌─┐┌────────┐
│1 ││1 ││1 ││0 ││ an-4 │=> 剩(n-4)个数要含5个连续1
└─┘└─┘└─┘└─┘└────────┘
┌─┐┌─┐┌─┐┌─┐┌─┐┌─────┐
│1 ││1 ││1 ││1 ││0 ││ an-5 │=> 剩(n-5)个数要含5个连续1
└─┘└─┘└─┘└─┘└─┘└─────┘
┌─┐┌─┐┌─┐┌─┐┌─┐┌─────┐
│1 ││1 ││1 ││1 ││1 ││ 2^(n-5) │=> 已出现5个连续1，后面任意即可
└─┘└─┘└─┘└─┘└─┘└─────┘
含5个连续0也是同样的讨论方式
最后只要再扣掉1111100000与0000011111即可
另外，开头为00或01与开头为0的方法数是一样的
所以只能算一次，否则会重复算
你不能根据你现在讨论的开头是几个bit去讨论所有的情况
而是根据递回的条件作为你讨论的依据
比方说你会先讨论第一个bit
如果第一个bit是0，代表剩下的(n-1)个数中要含5个连续1
如果第一个bit是1，你不能说剩下的(n-1)个数中一样要含5个连续1
因为如果第二个bit是0的话，代表你的第一个1被中断了
只能从剩下的(n-2)个数中找到含5个连续1的方法数
所以这个情况就会变成是上面(an-2)的case
但如果第二个bit是1的话，代表你现在有两个连续1
但你不能说剩下的(n-2)个数中要含5个连续1
因为如果第三个bit是0的话，代表你的前面两个1被中断了
只能从剩下的(n-3)个数中找到含5个连续1的方法数
所以这个情况就会变成是上面(an-3)的case
以此类推往下讨论就会变成上面的讨论方式
所以你必须依照你所定的递回条件和你目前的讨论状况作为讨论的依据
: 前面有类似题目，例如二元序不含连续个0
: 会分成开头为1，则有an-1个
: 若第一位为0，则有an-2个
: 则an=(an-1)+(an-2)
此题只要仿照上面的讨论方式即可
假设an表示不含连续0的方法数
┌─┐┌─────────────────┐
│1 ││ an-1 │=> 剩(n-1)个数不含连续0
└─┘└─────────────────┘
┌─┐┌─┐┌──────────────┐
│0 ││1 ││ an-2 │=> 剩(n-2)个数不含连续0
└─┘└─┘└──────────────┘
: 麻烦解惑了! 谢谢!