【问题简述】

　　在N个坑中放核物质，求无连续M个坑放入核物质的方法总数。
【算法分析】

　　本题是典型的组合计数问题，且数据量较大，所以应使用组合数学的算法实现。
　　运用升格思想，设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
【程序实现的技巧】

　　递推关系式建立了，编程实现就没什么困难了，但还应注一下问题的规模。本题N的规模可达50，根据不等式F(50)<=250 ≈1015，已超过长整型的范围。但如果使用高精度计算势必会加大编程复杂度。事实上1015并不是非常大，选用合适的数据结构完全可以避免高精度运算。TurboPascal支持一种称为Extended的实型数组，它可支持最多20位的有效数字。完全可以适应本题的要求。如此一来，程序就只有短短的四行了，源程序见附录。
【进一步的优化】

　　首先是空间上，以上算法虽然可行，但不难发现当前状态的值只与前面有限的几项有关系，如果我们将其全部储存必然会造成空间上巨大的浪费。一种常见的做法是在数组中只保存前N项关联的数据，算完一个阶段后再刷新，将所有数据向上一阶段复制，遗弃最前面的那个阶段，继续算下一阶段。这种方法虽然可行，但数据的复制要耗费额外的时间，并且当相关的阶段较多时对原来程序要做的改动较大，既不方便又易出错。下面介绍一个本人自己在编程时摸索出来的方法，实现起来非常简单，同时也省去了复制数据的时间。设当前阶段与前M阶段相关，建立数组F[0..M]，数组存储内容与原来一样，不过访问数组下标I时，使用F[I Mod (N+1)]代替。这样只需作很小的改动，就可获得大量空间，并且Pascal处理Mod的速度是很快的，这种方法几乎没有额外的时间消耗。

　　在时间效率上，本算法也有可优化的地方。题目只要我们求出N规模的解，而我们通过递推关系式，把1-N规模的解都求出来了，这无疑是一个浪费。尤其是当问题规模进一步增大时，往往考虑使用母函数将问题的递推关系转化为关于N的函数直接求解。限于篇幅这里就不介绍了。
　　总之，程序=算法+数据结构，程序的优化是无止境的，我们在平常的编程中要注重这方面的训练，才能从中获益。
【附录】

源程序：Nuclear.pas
{$N+}
Program exp;
Var f:Array [-5..50] Of Extended;
　　n,m,i:Integer;
Begin
　Readln(n,m);
　Fillchar(f,sizeof(f),0);f[-1]:=1;f[0]:=1;
　For i:=1 To n Do f[i]:=2*f[i-1]-f[i-m-1];
　Writeln(f[n]:0:0);
End.