組合算法的選擇與應(yīng)用

1、 組合算法的選擇與應(yīng)用【關(guān)鍵字】組合算法 評(píng)價(jià)依據(jù) 復(fù)雜性 選擇 應(yīng)用【摘要】本文提出了在組合算法設(shè)計(jì)和組合算法選擇方面所應(yīng)當(dāng)遵循的三個(gè)原則，即通用性、可計(jì)算性和較少的信息冗余量，并初步分析了它們之間的相互關(guān)系。這三個(gè)原則是整個(gè)組合算法設(shè)計(jì)的主導(dǎo)思想，也是數(shù)學(xué)建模和算法優(yōu)化的方向。通過對(duì)三個(gè)問題的分析，提示了組合算法的設(shè)計(jì)方法，改進(jìn)方向和優(yōu)化技術(shù)，是對(duì)一系列組合數(shù)學(xué)原理的實(shí)際應(yīng)用，也是對(duì)組合算法設(shè)計(jì)的初步研究?！菊摹恳弧⒁?論組合數(shù)學(xué)是一個(gè)古老的數(shù)學(xué)分支，也是當(dāng)代數(shù)學(xué)中非常重要的數(shù)學(xué)分支。它發(fā)源于有趣的數(shù)學(xué)游戲，許多古典的組合數(shù)學(xué)問題，無(wú)論在理論數(shù)學(xué)或應(yīng)用數(shù)學(xué)上都有很重要的研究?jī)r(jià)值。今天，一

2、方面，極為成熟的組合計(jì)數(shù)理論為物理學(xué)、化學(xué)、生物學(xué)的發(fā)展奠定了堅(jiān)實(shí)的基礎(chǔ)，另一方面，由于計(jì)算機(jī)軟硬件的限制，組合計(jì)數(shù)理論的計(jì)算機(jī)實(shí)踐又必然涉及到基于多項(xiàng)式時(shí)間內(nèi)的算法優(yōu)化問題。本文正是基于以上情況，對(duì)一系列組合問題的算法設(shè)計(jì)做了一些初步探索。二、組合算法的評(píng)價(jià)依據(jù)任何事物都有好壞之分，算法也不例外。眾所周知，時(shí)間復(fù)雜度與空間復(fù)雜度是算法評(píng)價(jià)的主要依據(jù)。那么，除了這兩點(diǎn)外，組合算法的設(shè)計(jì)還應(yīng)遵循怎樣的原則呢？1通用性通用性即可移植性。一個(gè)算法，是只適合于一個(gè)特殊問題，還是可以適用于一類問題，這是組合算法評(píng)價(jià)的一個(gè)主要依據(jù)，有些組合數(shù)學(xué)問題，許多信息學(xué)競(jìng)賽或數(shù)學(xué)建模競(jìng)賽選手一看到題目后往往使用模擬

3、法或構(gòu)造產(chǎn)生式系統(tǒng) 見參考文獻(xiàn)6第一章，然后用深度優(yōu)先搜索（DFS），或廣度優(yōu)先搜索（BFS）求解，用這些方法設(shè)計(jì)的程序往往受到時(shí)間或空間的限制，而且由于在綜合數(shù)據(jù)庫(kù)中信息存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)不同，其算法實(shí)現(xiàn)時(shí)的規(guī)模 在本論文中，我們將規(guī)模定義為在一定時(shí)間內(nèi)程序可以運(yùn)行完畢的情況下輸入數(shù)據(jù)的最大量。也不同，這必然影響到算法的通用性問題。解決問題的辦法是對(duì)原問題進(jìn)行數(shù)學(xué)抽象，取其精華，去其糟粕。只有對(duì)原問題的數(shù)學(xué)模型仔細(xì)分析，抓住本質(zhì)，才能建立高效的組合算法，只有這種經(jīng)過數(shù)學(xué)抽象的算法，才能具有較好的通用性，能夠應(yīng)付較大的規(guī)模。另外，在大規(guī)模組合算法的設(shè)計(jì)過程中，強(qiáng)調(diào)通用性的好處是顯而易見的，它便于算

4、法的優(yōu)化和升級(jí)。在實(shí)際應(yīng)用中的某些條件改變時(shí)，可以重寫較少的代碼。從軟件工程學(xué)的角度來說，通用性是必需的。2可計(jì)算性這里指的可計(jì)算性，是指能夠在多項(xiàng)式時(shí)間內(nèi)得出結(jié)果。一般來說，對(duì)于遞歸函數(shù)來說，由于計(jì)算機(jī)系統(tǒng)中的空間一定，因此對(duì)問題的規(guī)模有較嚴(yán)格的限制（例如在Turbo Pascal 7.0系統(tǒng)中，棧的最大空間只有65520字節(jié)）因此說，對(duì)于大多數(shù)的遞歸函數(shù)具有較差的可計(jì)算性。通過組合方法，求遞歸函數(shù)的非遞歸形式是解決這類問題有主要方法，但并不是所有的遞歸函數(shù)都可轉(zhuǎn)化為非遞歸形式，雙遞歸函數(shù)（如Ackermann函數(shù) Ackermann函數(shù)可用遞推關(guān)系如下定義A（m，0）=A（m-1，0） m

5、=1，2，A（m，n）=A（m-1，A（m，n-1） m=1，2， n=1，2， 初始條件為 A（0，n）=n+1，n=0，1，）便不能轉(zhuǎn)化為非遞歸形式，這類函數(shù)具有較小的可計(jì)算性。當(dāng)然，對(duì)于某些遞歸函數(shù)，通過尋找函數(shù)本身的組合意義進(jìn)而將其轉(zhuǎn)化為非遞歸函數(shù)也是一種方法。這種方法的應(yīng)用讀者將在后文中見到。3、信息冗余量在組合數(shù)學(xué)的建模過程中，大量的信息冗余是制約組合算法效率的一個(gè)重要因素，例如在遞歸程序運(yùn)行的過程中，實(shí)際上產(chǎn)生了一棵解答樹 見參考文獻(xiàn)6第二章（產(chǎn)生式系統(tǒng)的搜索策略），同一棵子樹的結(jié)點(diǎn)間的信息不相互關(guān)聯(lián)，這樣便產(chǎn)生了大量的信息冗余，解決的方法之一便是引入記憶機(jī)制，將已得出的信息記錄

6、下來。這種機(jī)制實(shí)際上起到了剪枝的作用，但它嚴(yán)格受到空間的限制，實(shí)際上是時(shí)空矛盾在算法設(shè)計(jì)中的體現(xiàn)。這便是我們?cè)诮M合算法設(shè)計(jì)中倡導(dǎo)函數(shù)非遞歸化的原因。它可以達(dá)到零信息冗余。當(dāng)然，組合算法的通用性、可計(jì)算性與信息冗余程度在一定程度上是對(duì)立的。例如雙遞歸函數(shù)作為一種數(shù)學(xué)模型，能夠反映一類問題，具有通用性，但卻具有較差的可計(jì)算性和較大的信息冗余量，而有些問題雖具有較好的可計(jì)算性和較低的信息冗余量，卻具有較差的通用性?？傊?，算法的時(shí)間復(fù)雜度，空間復(fù)雜度，通用性，可計(jì)算性和信息冗余量應(yīng)是衡量組合算法的幾個(gè)主要標(biāo)準(zhǔn)。三、組合算法的選擇實(shí)例組合算法的評(píng)價(jià)依據(jù)同時(shí)也是建立數(shù)學(xué)模型和優(yōu)化算法的指導(dǎo)思想。那么應(yīng)該如

7、何設(shè)計(jì)高效，通用的組合算法呢？下面我們通過幾個(gè)實(shí)際的組合問題來初步研究。例1核反應(yīng)堆中有和兩種粒子，每秒鐘內(nèi)一個(gè)粒子可以反應(yīng)產(chǎn)生3個(gè)粒子，而一個(gè)粒子可以反應(yīng)產(chǎn)生1個(gè)粒子和2個(gè)粒子。若在t=0時(shí)刻的反應(yīng)堆中只有一個(gè)粒子，求在t時(shí)刻的反應(yīng)堆中粒子和粒子數(shù)。這是一個(gè)物理學(xué)中的簡(jiǎn)單問題。我們通過對(duì)兩種算法的比較來說明組合算法的通用性。模型I：本題中共涉及兩個(gè)變量，設(shè)在i時(shí)刻粒子數(shù)為ni，粒子數(shù)為mi，則有：n0=1,m0=0,ni=mi1，mi=3ni1+2mi1 本題便轉(zhuǎn)化為求數(shù)列N和M的第t項(xiàng)，我們可用遞推的方法求得nt和mt，此模型的空間需求較小，時(shí)間復(fù)雜度為O（n），但隨著n的增大，所需時(shí)間越

8、來越大，即：T n此模型的算法如下：算法1-1Prog Arithmtic1_1;BeginRead(t); n0:=1; /初始化操作 m0:=0; for i:=1 to t do /進(jìn)行t次遞推 begin ni:=mi-1; mi:=3*ni-1+2*mi-1; end; write(nt); /輸出結(jié)果 write(mt);End. Arithmtic1_1模型II：設(shè)在t時(shí)刻的粒子數(shù)為f（t），粒子數(shù)為g(t)，依題可知： g(t)=3f(t -1)+2g(t -1) （1）f(t)=g(t -1) （2）g(0)=0,f(0)=1下面求解這個(gè)遞歸函數(shù)的非遞歸形式由（2）得f(t

9、-1)=g(t-2) （3）將（3）代入（1）得g(t)=3g(t -2)+2g(t-1) （t2） （4）g(0)=0,g(1)=3（4）式的特征根方程為：x22x3=0其特征根為x1=3,x2= -1所以該式的遞推關(guān)系的通解為g(t)=C1·3t+C2·( -1)t代入初值g(0)=0,g(1)=3得C1+C2=03C1C2=3解此方程組得所以該遞推關(guān)系的解為g(t)=即 算法12Prog Arithmetic1_2;Begin read(t); n:=trunc(exp(t*ln(3); m:=trunc(exp(t+1)*ln(3); if odd(t) then

10、begin /判斷( -1)t n:=n-3; m:=m+3; end else begin n:=n+3; m:=m-3; end; n:=trunc(n/4); / 4|n m:=trunc(m/4); / 4|m Write(n); Write(m);End. Arithmetic1_2在模型II中，我們運(yùn)用組合數(shù)學(xué)的方法建立了遞歸函數(shù)并轉(zhuǎn)化為非遞歸函數(shù)。它的優(yōu)點(diǎn)是算法的復(fù)雜性與問題的規(guī)模無(wú)關(guān)。針對(duì)某一具體數(shù)據(jù)，問題的規(guī)模對(duì)時(shí)間的影響微乎其微。通過以上兩個(gè)模型我們可以看出，模型II抓住了問題的本質(zhì)，尤其成功地運(yùn)用了組合數(shù)學(xué)中關(guān)于常系數(shù)線性齊次遞推關(guān)系求解的有關(guān)知識(shí)，因而使算法本身既具有通

11、用性和可計(jì)算性，同時(shí)達(dá)到了零信息冗余。例2在平面直角坐標(biāo)系中，有n個(gè)圓心坐標(biāo)為整點(diǎn)的單位圓，求它們所覆蓋區(qū)域的總面積。這是一道計(jì)算幾何學(xué)的問題，關(guān)于圖形并的問題，較為常用的方法是離散化，但是如果借助于組合數(shù)學(xué)的有關(guān)理論，是否可以設(shè)計(jì)出更好的算法呢？我們先來看幾個(gè)簡(jiǎn)單的例子。（1）兩個(gè)圓的交（交集不為）設(shè)圓i的圓心坐標(biāo)為（xi,yi），我們定義一個(gè)異型函數(shù)（dissmilaruty function）如下：在討論兩個(gè)圓的交的問題時(shí)，設(shè)兩圓為圓1與圓2，它們的交有兩種情況設(shè)陰影部分面積為S，則S= =設(shè)陰影部分面積為S，則S= = =由于兩個(gè)圓的非空交集問題是圓最簡(jiǎn)單的交問題。所以我們規(guī)定的交為型

12、交，的交為型交，這個(gè)規(guī)定將在下文的討論中用到。2、三個(gè)圓的交（交集不為）：經(jīng)過分析易證，若三個(gè)圓的交集不為空，則三個(gè)圓中任意兩圓的交集一定不為空，反之亦成立。且在任意兩圓相交所組成的三個(gè)交中，一定有2個(gè)型交，1個(gè)型交。如圖所示，陰影部分面積為S，則有：S=3、四個(gè)圓的交（交集不為）經(jīng)分析可證，若四個(gè)圓的交集不為。則四個(gè)圓的圓心一定圍成一個(gè)邊長(zhǎng)為1的正方形，這四個(gè)圓心按照順時(shí)針（或逆時(shí)針方向）一定形成4個(gè)型交，四個(gè)圓的交集如圖中陰影部分所示，設(shè)其陰影部分面積為S，則：S= = =可以證明5個(gè)或5個(gè)以上互不重合的單位圓的交集必為。分析至此，我們可以知道，任意多個(gè)單位圓的交集都可以通過2、3、4個(gè)圓

13、的交而獲得，那么任意多個(gè)單位圓的并集呢？由交集到并集，這使我們想起了容斥原理，于是得出：模型有了，但是平面上的位置關(guān)系如何來表示呢？我們用帶權(quán)有向圖來有表示單位圓間的關(guān)系，邊上的權(quán)函數(shù)定義如下： 0 AiAj=C（i,j）= 1 Ai與Aj為型交 2 Ai與Aj的型交于是所有單位圓之間的信息便可由一個(gè)三角矩陣表示出來。兩個(gè)圓、三個(gè)圓、四個(gè)圓相交的情況可由下圖表示：1i11 i i imjj 1 2 2 11j j k 1k(1) (2) (3) (4)（1）圖表示兩圓為型交的圓；（2）圖表示兩圓為型為圓；（3）圖表示3個(gè)圓相交的圖，在3邊中有 邊權(quán)為2，其余兩邊權(quán)為1；（4）圖為四個(gè)圓相交時(shí)的

14、圖。題目標(biāo)分析至此，我們便可輕松地設(shè)計(jì)出算法。算法2Func dissmilaruty_function(k1,k2:integer):integer; Beginl:=abs(xk1-xk2)+abs(yk1-yk2); /計(jì)算異型函數(shù)的值 if l>2 then return(0) else return(l); End; dissmilaruty_function Proc Arithetic2; Begin count1:=0; /count1為型交的個(gè)數(shù) count2:=0; /count2為型交的個(gè)數(shù) area:=n*pi; /當(dāng)所有圓都不相交時(shí)的面積值 for i:=1 t

15、o n-1 do for j:=i+1 to n do begin listi,j:=dissmilaruty_function(i,j); if listi,j=1 then count1:=count1+1; /兩圓為型交else if listi,j=2 then count2:=count2+1; /兩圓為型交 end;/判斷兩個(gè)圓的相交情況 area:=area-count1*s1-count2*s2; count1:=0; for i:=1 to n-2 do for j:=i+1 to n-1 do for k:=j+1 to n do begin check:=true; p:

16、=listi,j+listj,k+listi,k; if (listi,j=0) or (listj,k=0) or (listi,k=0) then check:=false; if (p=4) and check then /三邊的權(quán)值都不為0且權(quán)值之和為4 begin count1:=count1+1; /三個(gè)圓的交不為空的個(gè)數(shù) if listi,j=2 then infoi,k:=2 else if listj,k=2 then infoj,k:=2 else if listi,k=2 then infoi,k:=2; end;/info供判斷四個(gè)圓的交的情況時(shí)使用 end;/判斷三個(gè)

17、圓的交的情況 area:=area+s3*count1; count1:=0; for i:=1 to n-2 do for j:=i+1 to n-1 do for k:=j+1 to n do if (j<>k) and (infoi,j=2) and (listj,k=1) and (listi,k=1) then count1:=count1+1; /四個(gè)圓的交的個(gè)數(shù) area:=area-s4*count1; End; Arithetic2這種算法建立在對(duì)問題進(jìn)行深入分析，數(shù)學(xué)抽象的基礎(chǔ)之上的，因而無(wú)論在時(shí)間上還是在空間上都是較優(yōu)的。更為重要的是，這種算法比離散化算法更精

18、確，更具一般性，能夠解決諸如圖形并等一系列問題。且算法的實(shí)質(zhì)是一種計(jì)數(shù)問題，具有較強(qiáng)的可計(jì)算性。例3一場(chǎng)激烈的足球賽開始前，售票工作正在緊張的進(jìn)行中，每張球票為50元?，F(xiàn)有2n個(gè)人排隊(duì)等待購(gòu)票，其中有n 個(gè)人手持50元的鈔票，另外n個(gè)人手持100元的鈔票，假設(shè)開始售票時(shí)售票處沒有零錢。問這2n個(gè)人有多少種排隊(duì)方式，使售票處不至出現(xiàn)找不開錢的局面？這是一道典型的組合計(jì)數(shù)問題。從表面上看很難找出規(guī)律，下面我們基于本題建立幾個(gè)模型，最終揭示問題的本質(zhì)。I搜索模型我們用深度優(yōu)先搜索（DFS）算法來直觀地模擬所有情況。算法中指定一變量k記錄售票處有50元鈔票的張數(shù)，初始時(shí)令k=0，若某人手持100元鈔票

19、且k=0時(shí)則回溯，否則繼續(xù)遞歸。若第2n個(gè)人購(gòu)?fù)昶奔催f歸進(jìn)行到第2n層時(shí)計(jì)數(shù)器累加1。遞歸結(jié)束后，計(jì)數(shù)器中的值便為排隊(duì)總數(shù)。算法3-1Proc DFS(i:integer); /I為遞歸層數(shù) Begin for j:=0 to 1 do /j=0表示某人手持50元的鈔票 ，j=1表示某人手持100元鈔票 begin if (j=0) then begin k:=k+1; /k表示計(jì)數(shù)器 m:=m+1; /m表示有多少人手持50元鈔票購(gòu)票 if (m=n) then total:=total+1 /若已有n個(gè)人手持50元鈔票購(gòu)票，那么其余手持100元鈔票購(gòu)票的人一定能找開錢。 else dfs(

20、i+1); k:=k-1; m:=m-1; end else begin /表示手持100元鈔票時(shí) if k>0 then begin k:=k-1; dfs(i+1); k:=k+1; end; end; endfor; End; dfs由于本算法的實(shí)質(zhì)是模擬，因此算法實(shí)現(xiàn)起來時(shí)間復(fù)雜度較高，為指數(shù)級(jí)，這種算法嚴(yán)格限制了問題的規(guī)模，因而不是一個(gè)好的算法。II棧模型通過對(duì)問題的分析我們可以得出這樣的結(jié)論：在任何時(shí)刻，若第n個(gè)人手持100元的鈔票買票，則在此之前，定有m個(gè)人手持50元的鈔票買票，使得mn，我們通過分析還將得出：售票處收到的50元的鈔票最終將全部找出，售票處收到的100元的鈔

21、票最終將全部留下，且一旦收到一張面值為100元的鈔票，則一定找出一張面值為50元的鈔票。由此我們想到了用棧來表示這一過程：若某人手持一張50元的錢幣購(gòu)票，相當(dāng)于一個(gè)元素進(jìn)棧；若某人手持一張100元的錢幣購(gòu)票，相當(dāng)于一個(gè)元素出棧。則問題轉(zhuǎn)化為：若1n共n個(gè)元素依次進(jìn)棧，問共有多少種出棧順序。n個(gè) 元素的全排列共有n!個(gè)，那么這n!種方案是否都是可能的出棧順序呢？答案是否定的，我們可以證明，若a1,a2,an是可能的依次出棧順序，則一定不存在這樣的情況：使得i<j<k且aj<ak<ai，證明如下：若i<j<k，說明ai 最先出棧，aj次之，ak最后出棧，下面分兩

22、種情況討論：（i）如果ai>aj，那么當(dāng)aj 出棧時(shí)，如果ak已在棧中，則ak比aj先入棧，由輸入a序列知：ak<aj,所以有ak<aj<ai;當(dāng)出棧時(shí)，如果ak尚未入棧，則由輸入序列知aj<ai<ak（ii）如果ai<aj，那么當(dāng)aj出棧時(shí)，如果ak已入棧，則由輸入序列知ak<aj,而ai與ak的關(guān)系取決于ai與ak哪個(gè)先入棧。但無(wú)論怎樣，ai與ak均小于aj，當(dāng)aj出棧時(shí)，如果ak尚未入棧，則由輸入序列知ai<aj<ak因此，輸出序列中不可能出現(xiàn)當(dāng)i<j<k時(shí)，aj<ak<ai通過以上分析，我們得出棧模型的

23、算法，算法先產(chǎn)生1n共n個(gè)數(shù)的全排列，對(duì)于每種排列，若符合前面所講的出棧規(guī)則，那么這n個(gè)排列便是一個(gè)可能的出棧序列，計(jì)數(shù)器加1，當(dāng)n個(gè)元素的全排列列舉結(jié)束時(shí)，計(jì)數(shù)器的值便是問題的解。在此思想的指導(dǎo)下，為了與模型I的算法進(jìn)行比較，我們?cè)谶@里采用遞歸技術(shù)來產(chǎn)生n個(gè)元素的全排列，若在每產(chǎn)生一個(gè)排列后進(jìn)行該排列是否為可能輸出棧序列的判定，則算法的時(shí)間復(fù)雜度為O（nn），與模型I的算法比較起來，我們發(fā)現(xiàn)模型II中遞歸的深度降低，棧的使用空間減小，但在構(gòu)造解答樹的過程中，每層擴(kuò)展的結(jié)點(diǎn)數(shù)則大量增加，而有些結(jié)點(diǎn)的增加是無(wú)意義的，所以我們?cè)趯?shí)際的算法設(shè)計(jì)中可以一邊生成排列一邊進(jìn)行可能輸出序列的判定性檢驗(yàn)，若不

24、滿足條件，則及時(shí)剪枝，因而在n較大時(shí)該算法的時(shí)間復(fù)雜度應(yīng)小于O（nn）算法3-2Func check(s:integer):boolean; /判斷1s共s個(gè)元素的出棧序列是否為可能的棧輸出序列begin for a:=1 to s-2 do for b:=a+1 to s-1 do if (datab<datas) and (datas<dataa) then return(false); reture(true);end; checkProc stack(i:integer); /產(chǎn)生n個(gè)元素的全排列begin for j:=1 to n do if not(j in flag

25、) then begin datai:=j; if check(i) then begin flag:=flag+j; if i=n then total:=total+1 /計(jì)數(shù)器加1 else stack(i+1); flag:=flag-j; end; endfor;end; stack但我們應(yīng)該明確地看到，模型I與模型II在算法實(shí)現(xiàn)時(shí)解答樹中的結(jié)點(diǎn)數(shù)目都是很多的，結(jié)點(diǎn)是棧所儲(chǔ)存的信息，大量結(jié)點(diǎn)的出現(xiàn)必然影響算法可運(yùn)行數(shù)據(jù)的規(guī)模，在模型III中，我們著重思考如何對(duì)問題進(jìn)行數(shù)學(xué)抽象。III遞歸算法：令f(m,n)表示有m個(gè)人手持50元的鈔票，n個(gè)人手持100元的鈔票時(shí)共有的方案總數(shù)。我們分

26、情況來討論這個(gè)問題。(1)n=0n=0意味著排隊(duì)購(gòu)票的所有人手中拿的都是50元的錢幣，那么這m個(gè)人的排隊(duì)總數(shù)為1，即f(m,0 )=1（2）m<n若排隊(duì)購(gòu)票的(m+n)個(gè)人中有m個(gè)人手持50元的鈔票，n個(gè)人手持100元的鈔票，當(dāng)m<n時(shí)，即使把m張50元的鈔票都找出去，仍會(huì)出現(xiàn)找不開錢的局面，所以這時(shí)排隊(duì)總數(shù)為0,即f(m,n)=0（3）其它情況我們思考（m+n）個(gè)人排隊(duì)購(gòu)票的情景，第(m+n)個(gè)人站在第（m+n-1）個(gè)人的后面，則第（m+n）個(gè)人的排隊(duì)方式可由下列兩種情況獲得：第（m+n）個(gè)人手持100元的鈔票，則在他之前的（m+n-1）個(gè)人中有m個(gè)人手持50元的鈔票，有（n-1

27、）個(gè)人手持100元的鈔票，此種情況共有f(m,n-1)第（m+n）個(gè)人手持50元的鈔票，則在他之前的（m+n-1）個(gè)人中有（m-1）個(gè)人手持50元的鈔票，有n個(gè)人手持100元的鈔票，此種情況共有f(m-1,n)由加法原理得f(m,n)=f(m-1,n)+f(m,n-1)于是我們得到f(m,n)的計(jì)算公式： 0 m<nf(m,n)= 1 n=0 （*）f(m,n-1)+f(m-1,n)于是我們可以根據(jù)（*）式編寫遞歸算法算法3-3Func f(a,b:integer):longint;begin if a<b then f:=0 else if b=0 then f:=1 else

28、f:=f(a-1,b)+f(a,b-1);end; fIV 遞推算法遞歸算法是由終止條件向初始條件推導(dǎo)，而遞推算法是由初始條件向終止條件推導(dǎo)?？梢哉f，它們本質(zhì)上是相同的。那么，把遞歸算法改為遞推算法的意義何在呢？我們運(yùn)用（*）式求解f(4,4)，遞歸程序執(zhí)行時(shí)構(gòu)造的解答樹如下：14f(4，4)0f(3，4) f(4，3)145 9 f(3，3) f(4，2)41505f(2,3) f(3,2) f(3,2) f(4,1)313122f(2,2) f(3,1) f(2,2) f(3,1)2101210f(1,2) f(2,1) f(1,2) f(2,1)通過對(duì)解答樹的仔細(xì)觀察我們會(huì)發(fā)現(xiàn)，在樹中諸

29、如f（3,2）等結(jié)點(diǎn)大量重復(fù)計(jì)算。由此我們看出，遞歸算法雖具有通用性和可計(jì)算性，但產(chǎn)生了大量的數(shù)據(jù)冗余，這些大量的數(shù)據(jù)冗余是限制遞歸算法規(guī)模的主要因素，從而導(dǎo)致模型雖進(jìn)行了數(shù)學(xué)抽象，但算法實(shí)踐起來的效率并不高。那么應(yīng)如何避免大數(shù)據(jù)冗余以至最終達(dá)到零數(shù)據(jù)冗余呢？請(qǐng)看如下的二維表格：m f n12345110000222000335500449141405514284242如果用矩陣的形式，則可表示為1 0 0 0 02 2 0 0 03 5 5 0 04 9 14 14 05 14 28 42 42我們仔細(xì)觀察該矩陣可發(fā)現(xiàn)如下規(guī)律：（1）該短陣為一個(gè)5階下三角短陣（2）ai，j=ai-1, j+

30、ai，j-1（3）ai，i=ai，i-1于是我們便得到了如下算法：算法3-4Prog Arithmetic3_4;Begin read(n); for a:=1 to n do dataa,1:=a; /初始化賦值 for a:=2 to n do for b:=2 to a do dataa,b:=dataa-1,b+dataa,b-1; /遞推 write(datan,n);End. Arithmetic3_4由此，本題的遞推關(guān)系便建立起來，這個(gè)算法的時(shí)間復(fù)雜度為O(n2)，它與模型III的遞歸算法比較起來最大的優(yōu)點(diǎn)在于它充分利用了已經(jīng)得到的信息，從而使算法的時(shí)間復(fù)雜度大大降低，算法本身能

31、夠接受的規(guī)模也大大增加，達(dá)到了零信息冗余，可以說，這是一個(gè)較優(yōu)化的算法。V組合算法我們下面用一種嶄新的模型二叉樹來反映本題，我們依據(jù)以下原則建立一棵具有n 個(gè)結(jié)點(diǎn)的二叉樹。（1）若結(jié)點(diǎn)i是結(jié)點(diǎn)j的兒子結(jié)點(diǎn)，則i>j，若結(jié)點(diǎn)i是結(jié)點(diǎn)k 的左兒子，結(jié)點(diǎn)j是結(jié)點(diǎn)k的右兒子，則i<j。（2）若結(jié)點(diǎn)i是結(jié)點(diǎn)j的兒子且i比j先出棧，則結(jié)點(diǎn)i是結(jié)點(diǎn)j的左兒子；若結(jié)點(diǎn)i比結(jié)點(diǎn)j后出棧，則結(jié)點(diǎn)i是結(jié)點(diǎn)j的右兒子。由（1）可知，這棵具有幾個(gè)結(jié)點(diǎn)的二叉樹的先序遍歷序列一定為1n，由（2）可知，這棵樹最左邊的葉結(jié)點(diǎn)一定最先出棧，最后邊的葉結(jié)點(diǎn)一定最后出棧。所以說，對(duì)于任意一棵具有幾個(gè)結(jié)點(diǎn)的二叉樹，它的前序

32、遍歷順序便為1n，即n個(gè)元素的入棧順序，那么它的中序遍歷順序便是這n個(gè)元素的出棧順序。即2n個(gè)人的排隊(duì)方案總數(shù)即為具有n個(gè)結(jié)點(diǎn)的二叉樹的個(gè)數(shù)，又因?yàn)榫哂衝個(gè)結(jié)點(diǎn)的二叉樹個(gè)數(shù)為 ，即Catalan數(shù)，所以本題的不同排列總數(shù)為算法3-5 由于該算法涉及除法運(yùn)算，為了保證在程序執(zhí)行過程的中間結(jié)果在長(zhǎng)整型之內(nèi)，此算法在求組合數(shù)時(shí)進(jìn)行了優(yōu)化。Prog Arithmetic3_5;Begin read(n); total:=1; a:=n+2; b:=2; while (a<=2*n) do begin total:=total*a; while (total mod b=0) and (b<

33、=n) do begin total:=total div b; b:=b+1; end; a:=a+1; end; while b<n do begin total:=total div b; inc(b); end; write(total);End. Arithmetic3_5本算法的時(shí)間復(fù)雜度為O（n），從建模方式看，組合算法的模型最抽象，也最不易理解，但這個(gè)模型卻能抓住問題的本質(zhì)，因而具有極大的可計(jì)算性，達(dá)到了零信息冗余。 四 總 結(jié)組合算法作為當(dāng)代組合數(shù)學(xué)研究的重要組成部分，在基礎(chǔ)理論研究和社會(huì)實(shí)踐中發(fā)揮著越來越重要的作用，本文著重討論組合算法的評(píng)價(jià)依據(jù)，初步揭示了組合算法的

34、設(shè)計(jì)和優(yōu)化的基本問題?？傊?，只有掌握好組合算法的通用性，可計(jì)算性和信息冗余量的組合算法評(píng)價(jià)原則，才能設(shè)計(jì)出高效的組合算法?！舅惴ū容^實(shí)驗(yàn)】為了更好地反映組合算法設(shè)計(jì)中的三原則對(duì)算法效率的影響，我們對(duì)“球迷購(gòu)票問題”的五個(gè)模型進(jìn)行了實(shí)驗(yàn)，其總結(jié)如下：一、 系統(tǒng)設(shè)置：CPU: Intel 633 CeleronRAM: 128MBOS: Windows Me算法運(yùn)行環(huán)境：Turbo Pascal 7.0二、 規(guī)模確定：由于此實(shí)驗(yàn)的目的是確定模型的優(yōu)劣，所以測(cè)試數(shù)據(jù)所得結(jié)果控制在長(zhǎng)整型以內(nèi)。由計(jì)算得到1n17。為了更好地反映算法的效率，尤其是信息冗余對(duì)算法效率的影響，在進(jìn)行n值選取時(shí)，我們選的是不均

35、勻的。三、 時(shí)間測(cè)定算法：Begint:=meml$40:$6c;主程序；t:=(meml$40:$6c-t)/18.2;out(t) end.四、 實(shí)驗(yàn)結(jié)果 N結(jié)果模型1運(yùn)行時(shí)間模型2運(yùn)行時(shí)間模型3運(yùn)行時(shí)間模型4運(yùn)行時(shí)間模型5運(yùn)行時(shí)間5420.00000.00000.00000.00000.000010167960.00001.15380.00000.00000.00001374290000.1099>600.27470.00000.00001596948451.1538>603.68130.00000.000016353576704.2308>6013.51650.000

36、00.00001712964479015.3846>6049.50550.00000.0000(時(shí)間單位：s)【源程序】1 算法11 的源程序Program Arithmtic1_1;Var n,m:array0.100 of longint; t,i:integer;Begin write('Please input t:'); readln(t); n0:=1; m0:=0; for i:=1 to t do begin ni:=mi-1; mi:=3*ni-1+2*mi-1; end; writeln('N=',nt); writeln('M

37、=',mt);End.2 算法12的源程序Program Arithmetic1_2;var t:integer; n,m:longint;begin write('Please input t:'); readln(t); n:=trunc(exp(t*ln(3); m:=trunc(exp(t+1)*ln(3); if odd(t) then begin n:=n-3; m:=m+3; end else begin n:=n+3; m:=m-3; end; n:=trunc(n/4); m:=trunc(m/4); writeln('N=',n);

38、writeln('m=',m);end.3算法2的源程序Program Arithmetic2;Const InFile='input.txt' OutFile='output.txt' pi=3.1415926535; s1=2/3*pi-1.732/2; s2=pi/2-1; s3=5/12*pi-1.732/2;Var list,info:Array1.100,1.100 of shortint; x,y: Array1.100 of integer; n: Integer; area,s4: real;Procedure init; Va

39、r f:Text; a:integer; Begin assign(f,InFile); reset(f); readln(f,n); for a:=1 to n do read(f,xa,ya); close(f); s4:=4*sin(pi/12)*sin(pi/12)+pi/12-1/4; End;Function dissmilaruty_function(k1,k2:integer):integer; Var l:integer; Begin l:=abs(xk1-xk2)+abs(yk1-yk2); if l>2 then dissmilaruty_function:=0 e

40、lse dissmilaruty_function:=l; End;Procedure done; var i,j,k,p,count1,count2:integer; check: boolean; Begin count1:=0; count2:=0; area:=n*pi; for i:=1 to n-1 do for j:=i+1 to n do begin listi,j:=dissmilaruty_function(i,j); if listi,j=1 then inc(count1) else if listi,j=2 then inc(count2); end; area:=a

41、rea-count1*s1-count2*s2; count1:=0; for i:=1 to n-2 do for j:=i+1 to n-1 do for k:=j+1 to n do begin check:=true; p:=listi,j+listj,k+listi,k; if (listi,j=0) or (listj,k=0) or (listi,k=0) then check:=false; if (p=4) and check then begin inc(count1); if listi,j=2 then infoi,k:=2 else if listj,k=2 then

42、 infoj,k:=2 else if listi,k=2 then infoi,k:=2; end; end; area:=area+s3*count1; count1:=0; for i:=1 to n-2 do for j:=i+1 to n-1 do for k:=j+1 to n do if (j<>k) and (infoi,j=2) and (listj,k=1) and (listi,k=1) then inc(count1); area:=area-s4*count1; End;Procedure out; Var f:text; Begin assign(f,O

43、utFile); rewrite(f); writeln(f,area:0:4); close(f); End;Begin Init; Done; Out;End.4算法31的源程序$A+,B-,D-,E+,F-,G+,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V+,X+$M 65520,0,655360Program Arithmetic3_1;Var n,k,m:integer; total:longint;Procedure DFS(i:integer); Var j:integer; Begin for j:=0 to 1 do begin if (j=0) then begin inc(k); inc(m); if (m=n) then inc(total) else dfs(i+1); dec(k); dec(m); end else begin if k>0 then begin dec(k); dfs(i+1); inc(k); end; end;