阿修罗 2008-06-11 03:47:00
点我顶贴
收藏
删除
设N个坑不会发生爆炸的组合数为F(n)。
假设已知F(n)以前的放置方案，在n-1个坑的左边再加一个坑得n个坑。
则第n个坑的放置方案有以下情况：（为便于叙述，我们把放入核物质称为1，未放入称为0，则n个坑的状态表示为二进制数）
1、当该坑右边已有连续m-1个核物质时（即形如111…1110*），则该坑只能不放核物质，否则将发生爆炸。
因为前m个状态已确定，此种情况总数为F(n-1-m)
2、对于剩下的情况，新加入的第n个坑可以为1，也可为0。
此种情况总数为2*[F(n-1)-F(n-1-m)]。
通过加法原理，易得F(n)的递推关系式：
f(n)=2*f(n-1)-f(n-1-m)
f(-5)=f(-4)=f(-3)=f(-2)=0, f(-1)=f(0)=1
------------------------------------------------
我搞不懂他为什么 f(-1)=f(0)=1
这个f(-1)=1 ..好像很精妙......