前些天在論壇上看到一個看似簡單，其實挺有意思的問題：
【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上驗證通過。