前些天在论坛上看到一个看似简单，其实挺有意思的问题：
【20个连续的号码中抽出6个来，要求6个号码不能相连，有多少种抽法？】
这问题的本意应该是两两不相连的情况。
首先定义一个函数，F(m,p), m是确定抽出几个号码，p是总共有几个号码，那么
F(m,p)的值域就是代表在p个连续号码中，抽出两两不相连的m个号码，总共有几种组合；
接着确定状态转移方程，经过观察，p必须满足条件p >= m*2-1，否则F就为0，同时
F(6,20) = F(5,18) + F(5,17) + F(5,16) + ... + F(5,9)；
因此可以得出如下状态转移方程，
当 p > m*2-1，F(m,p) = Sigma(F(m-1,q)) + 1；其中q 从(m-1)*2 到 p-2；
当 p == m*2-1，F(m,p) = 1；
当 p < m*2-1，F(m,p) = 0；
虽然分析到此，已可以着手具体实现，但是还是有些问题值得进一步分析，比如F(m,p)和F(m,p-1)之间存在何种关系，若使用递归，就当前这个问题效率估计会是问题；
因此对此方程进一步分析，
F(5,18) = Sigma(F(4,q)）+ F(4,7)；q从8到16
F(5,17) = Sigma(F(4,q)）+ F(4,7)；q从8到8；
...
可进一步推出，
当 p > m*2-1, F(m,p) = F(m,p-1) + F(m-1,p-2)；
这样我们就得到了可以进行递推实现的转态转移方程；
另外，对于m == 1的情形，显然F(1,p) = p ；
#include<stdio.h>
#include<conio.h>
#define MAXLEN 10000
static int F[MAXLEN];
static int R[MAXLEN];
int Compute(
const int cM,
const int cP)
{
if (cM <= 0 || cP < (cM*2-1))
return 0;
if (cM == 1)
return cP;
if (cP == cM*2-1)
return 1;
for(int i = 0; i < MAXLEN; ++i) R[i] = i;
for(int m = 2; m <= cM; ++m)
{
int floof = 2*m;
int ceiling = cP-2*(cM-m);
F[2*m-1] = 1;
for(int p = floof; p <= ceiling; ++p)
F[p] = F[p-1] + R[p-2];
for(int j = floof; j <= ceiling; ++j)
R[j] = F[j];
}
return F[cP];
}
main()
{
Compute(6,20);
// Compute(6,19);
// Compute(5,18);
// Compute(5,17);
// Compute(4,16);
// Compute(6,13);
// Compute(6,12);
// Compute(5,11);
// Compute(5,10);
// Compute(4,9);
// Compute(4,8);
// Compute(3,7);
return 0;
}
接着再对目前的整个实现做下复杂度分析，主要处理部分基本上由两个循环构成，对于R数组的初始化可作为常数项不计，那么
大O( F(m,p) ) = O( m*(ceiling-floor) )
= O( m*(p-2*m) )
近似于O( m*p )，
若m << p，显然O(F(m,p)) = p；
若m 近似 p, 但事实上必须p >= 2*m - 1，否则F值就接近0或1，因此O(F(m,p)) 近似于const；
所以综合来看上面的这个实现在时间上是个线性复杂度的实现；在空间上，使用了两个长度至少为p的数组，个人认为可以对此进行进一步优化。
对于F(6,20) = 5005
整个实现在TC++ 3.0上验证通过。