前些天在論壇上看到一個(gè)看似簡(jiǎn)單，其實(shí)挺有意思的問(wèn)題：
【20個(gè)連續(xù)的號(hào)碼中抽出6個(gè)來(lái)，要求6個(gè)號(hào)碼不能相連，有多少種抽法？】
這問(wèn)題的本意應(yīng)該是兩兩不相連的情況。
首先定義一個(gè)函數(shù)，F(xiàn)(m,p), m是確定抽出幾個(gè)號(hào)碼，p是總共有幾個(gè)號(hào)碼，那么
F(m,p)的值域就是代表在p個(gè)連續(xù)號(hào)碼中，抽出兩兩不相連的m個(gè)號(hào)碼，總共有幾種組合；
接著確定狀態(tài)轉(zhuǎn)移方程，經(jīng)過(guò)觀察，p必須滿足條件p >= m*2-1，否則F就為0，同時(shí)
F(6,20) = F(5,18) + F(5,17) + F(5,16) + ... + F(5,9)；
因此可以得出如下?tīng)顟B(tài)轉(zhuǎn)移方程，
當(dāng) p > m*2-1，F(xiàn)(m,p) = Sigma(F(m-1,q)) + 1；其中q 從(m-1)*2 到 p-2；
當(dāng) p == m*2-1，F(xiàn)(m,p) = 1；
當(dāng) p < m*2-1，F(xiàn)(m,p) = 0；
雖然分析到此，已可以著手具體實(shí)現(xiàn)，但是還是有些問(wèn)題值得進(jìn)一步分析，比如F(m,p)和F(m,p-1)之間存在何種關(guān)系，若使用遞歸，就當(dāng)前這個(gè)問(wèn)題效率估計(jì)會(huì)是問(wèn)題；
因此對(duì)此方程進(jìn)一步分析，
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；
...
可進(jìn)一步推出，
當(dāng) p > m*2-1, F(m,p) = F(m,p-1) + F(m-1,p-2)；
這樣我們就得到了可以進(jìn)行遞推實(shí)現(xiàn)的轉(zhuǎn)態(tài)轉(zhuǎn)移方程；
另外，對(duì)于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;
}
接著再對(duì)目前的整個(gè)實(shí)現(xiàn)做下復(fù)雜度分析，主要處理部分基本上由兩個(gè)循環(huán)構(gòu)成，對(duì)于R數(shù)組的初始化可作為常數(shù)項(xiàng)不計(jì)，那么
大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, 但事實(shí)上必須p >= 2*m - 1，否則F值就接近0或1，因此O(F(m,p)) 近似于const；
所以綜合來(lái)看上面的這個(gè)實(shí)現(xiàn)在時(shí)間上是個(gè)線性復(fù)雜度的實(shí)現(xiàn)；在空間上，使用了兩個(gè)長(zhǎng)度至少為p的數(shù)組，個(gè)人認(rèn)為可以對(duì)此進(jìn)行進(jìn)一步優(yōu)化。
對(duì)于F(6,20) = 5005
整個(gè)實(shí)現(xiàn)在TC++ 3.0上驗(yàn)證通過(guò)。