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

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

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

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

4、法的優(yōu)化和升級。在實際應(yīng)用中的某些條件改變時，可以重寫較少的代碼。從軟件工程學的角度來說，通用性是必需的。2可計算性這里指的可計算性，是指能夠在多項式時間內(nèi)得出結(jié)果。一般來說，對于遞歸函數(shù)來說，由于計算機系統(tǒng)中的空間一定，因此對問題的規(guī)模有較嚴格的限制（例如在Turbo Pascal 7.0系統(tǒng)中，棧的最大空間只有65520字節(jié)）因此說，對于大多數(shù)的遞歸函數(shù)具有較差的可計算性。通過組合方法，求遞歸函數(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ù)具有較小的可計算性。當然，對于某些遞歸函數(shù)，通過尋找函數(shù)本身的組合意義進而將其轉(zhuǎn)化為非遞歸函數(shù)也是一種方法。這種方法的應(yīng)用讀者將在后文中見到。3、信息冗余量在組合數(shù)學的建模過程中，大量的信息冗余是制約組合算法效率的一個重要因素，例如在遞歸程序運行的過程中，實際上產(chǎn)生了一棵解答樹 見參考文獻6第二章（產(chǎn)生式系統(tǒng)的搜索策略），同一棵子樹的結(jié)點間的信息不相互關(guān)聯(lián)，這樣便產(chǎn)生了大量的信息冗余，解決的方法之一便是引入記憶機制，將已得出的信息記錄

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

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

8、來越大，即：T n此模型的算法如下：算法1-1Prog Arithmtic1_1;BeginRead(t); n0:=1; /初始化操作 m0:=0; for i:=1 to t do /進行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ù)為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下面求解這個遞歸函數(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中，我們運用組合數(shù)學的方法建立了遞歸函數(shù)并轉(zhuǎn)化為非遞歸函數(shù)。它的優(yōu)點是算法的復雜性與問題的規(guī)模無關(guān)。針對某一具體數(shù)據(jù)，問題的規(guī)模對時間的影響微乎其微。通過以上兩個模型我們可以看出，模型II抓住了問題的本質(zhì)，尤其成功地運用了組合數(shù)學中關(guān)于常系數(shù)線性齊次遞推關(guān)系求解的有關(guān)知識，因而使算法本身既具有通

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

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

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

14、圖。題目標分析至此，我們便可輕松地設(shè)計出算法。算法2Func dissmilaruty_function(k1,k2:integer):integer; Beginl:=abs(xk1-xk2)+abs(yk1-yk2); /計算異型函數(shù)的值 if l>2 then return(0) else return(l); End; dissmilaruty_function Proc Arithetic2; Begin count1:=0; /count1為型交的個數(shù) count2:=0; /count2為型交的個數(shù) area:=n*pi; /當所有圓都不相交時的面積值 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;/判斷兩個圓的相交情況 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; /三個圓的交不為空的個數(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供判斷四個圓的交的情況時使用 end;/判斷三個

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; /四個圓的交的個數(shù) area:=area-s4*count1; End; Arithetic2這種算法建立在對問題進行深入分析，數(shù)學抽象的基礎(chǔ)之上的，因而無論在時間上還是在空間上都是較優(yōu)的。更為重要的是，這種算法比離散化算法更精

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

19、且k=0時則回溯，否則繼續(xù)遞歸。若第2n個人購完票即遞歸進行到第2n層時計數(shù)器累加1。遞歸結(jié)束后，計數(shù)器中的值便為排隊總數(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表示計數(shù)器 m:=m+1; /m表示有多少人手持50元鈔票購票 if (m=n) then total:=total+1 /若已有n個人手持50元鈔票購票，那么其余手持100元鈔票購票的人一定能找開錢。 else dfs(

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

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

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

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

24、滿足條件，則及時剪枝，因而在n較大時該算法的時間復雜度應(yīng)小于O（nn）算法3-2Func check(s:integer):boolean; /判斷1s共s個元素的出棧序列是否為可能的棧輸出序列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個元素的全排列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 /計數(shù)器加1 else stack(i+1); flag:=flag-j; end; endfor;end; stack但我們應(yīng)該明確地看到，模型I與模型II在算法實現(xiàn)時解答樹中的結(jié)點數(shù)目都是很多的，結(jié)點是棧所儲存的信息，大量結(jié)點的出現(xiàn)必然影響算法可運行數(shù)據(jù)的規(guī)模，在模型III中，我們著重思考如何對問題進行數(shù)學抽象。III遞歸算法：令f(m,n)表示有m個人手持50元的鈔票，n個人手持100元的鈔票時共有的方案總數(shù)。我們分

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

27、）個人手持100元的鈔票，此種情況共有f(m,n-1)第（m+n）個人手持50元的鈔票，則在他之前的（m+n-1）個人中有（m-1）個人手持50元的鈔票，有n個人手持100元的鈔票，此種情況共有f(m-1,n)由加法原理得f(m,n)=f(m-1,n)+f(m,n-1)于是我們得到f(m,n)的計算公式： 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 遞推算法遞歸算法是由終止條件向初始條件推導，而遞推算法是由初始條件向終止條件推導?？梢哉f，它們本質(zhì)上是相同的。那么，把遞歸算法改為遞推算法的意義何在呢？我們運用（*）式求解f(4,4)，遞歸程序執(zhí)行時構(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)通過對解答樹的仔細觀察我們會發(fā)現(xiàn)，在樹中諸

29、如f（3,2）等結(jié)點大量重復計算。由此我們看出，遞歸算法雖具有通用性和可計算性，但產(chǎn)生了大量的數(shù)據(jù)冗余，這些大量的數(shù)據(jù)冗余是限制遞歸算法規(guī)模的主要因素，從而導致模型雖進行了數(shù)學抽象，但算法實踐起來的效率并不高。那么應(yīng)如何避免大數(shù)據(jù)冗余以至最終達到零數(shù)據(jù)冗余呢？請看如下的二維表格：m f n12345110000222000335500449141405514284242如果用矩陣的形式，則可表示為1 0 0 0 02 2 0 0 03 5 5 0 04 9 14 14 05 14 28 42 42我們仔細觀察該矩陣可發(fā)現(xiàn)如下規(guī)律：（1）該短陣為一個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)系便建立起來，這個算法的時間復雜度為O(n2)，它與模型III的遞歸算法比較起來最大的優(yōu)點在于它充分利用了已經(jīng)得到的信息，從而使算法的時間復雜度大大降低，算法本身能

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

32、遍歷順序便為1n，即n個元素的入棧順序，那么它的中序遍歷順序便是這n個元素的出棧順序。即2n個人的排隊方案總數(shù)即為具有n個結(jié)點的二叉樹的個數(shù)，又因為具有n個結(jié)點的二叉樹個數(shù)為 ，即Catalan數(shù)，所以本題的不同排列總數(shù)為算法3-5 由于該算法涉及除法運算，為了保證在程序執(zhí)行過程的中間結(jié)果在長整型之內(nèi)，此算法在求組合數(shù)時進行了優(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本算法的時間復雜度為O（n），從建模方式看，組合算法的模型最抽象，也最不易理解，但這個模型卻能抓住問題的本質(zhì)，因而具有極大的可計算性，達到了零信息冗余。 四 總 結(jié)組合算法作為當代組合數(shù)學研究的重要組成部分，在基礎(chǔ)理論研究和社會實踐中發(fā)揮著越來越重要的作用，本文著重討論組合算法的評價依據(jù)，初步揭示了組合算法的

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

35、勻的。三、 時間測定算法：Begint:=meml$40:$6c;主程序；t:=(meml$40:$6c-t)/18.2;out(t) end.四、 實驗結(jié)果 N結(jié)果模型1運行時間模型2運行時間模型3運行時間模型4運行時間模型5運行時間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(時間單位：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;