算法合集之《數(shù)學(xué)模型的建立比較和應(yīng)用》

1、數(shù)學(xué)模型的建立、比較和應(yīng)用蘇州中學(xué) 邵錚關(guān)鍵字: 數(shù)學(xué)模型 算法 母函數(shù)【摘要】數(shù)學(xué)模型是解決實(shí)際問題的一種基本工具。將實(shí)際問題抽象成一個(gè)數(shù)學(xué)模型，運(yùn)用數(shù)學(xué)工具進(jìn)行求解，并將結(jié)果應(yīng)用于具有相同特征的一類問題中，是解決問題的一種基本的途徑。本文首先介紹了數(shù)學(xué)模型的一些性質(zhì)，然后建立了三種不同的數(shù)學(xué)模型來求解一個(gè)問題，將三種數(shù)學(xué)模型相互比較，得出數(shù)學(xué)模型抽象性與高效性之間的關(guān)系，再將數(shù)學(xué)模型推廣應(yīng)用于另兩個(gè)問題的求解，得出數(shù)學(xué)模型抽象性與可推廣性之間的關(guān)系，最后總結(jié)全文，揭示出有關(guān)數(shù)學(xué)模型的一些普遍規(guī)律一、引論實(shí)際問題往往是紛繁而復(fù)雜的，而其中的規(guī)律也是隱藏著的，要想直接用計(jì)算機(jī)來求解實(shí)際問題往往

2、有一定的困難。計(jì)算機(jī)擅長(zhǎng)的是解決數(shù)學(xué)問題。因此，我們有必要將實(shí)際問題抽象成數(shù)學(xué)模型，然后再用計(jì)算機(jī)來對(duì)數(shù)學(xué)模型進(jìn)行求解。與實(shí)際問題相比，數(shù)學(xué)模型有以下幾個(gè)性質(zhì)：抽象性：數(shù)學(xué)模型是實(shí)際問題的一種抽象，它去除了實(shí)際問題中與問題的求解無關(guān)的部分，簡(jiǎn)明地體現(xiàn)了問題的本質(zhì)。這一點(diǎn)是下面兩個(gè)性質(zhì)的基礎(chǔ)。高效性：數(shù)學(xué)模型中各個(gè)量之間的關(guān)系更為清晰，容易從中找到規(guī)律，從而提高求解的效率。由于這一點(diǎn)是由數(shù)學(xué)模型的抽象性決定的，因此數(shù)學(xué)模型的抽象化程度對(duì)數(shù)學(xué)模型效率的高低有重要的影響，這一點(diǎn)將在第二部分中詳細(xì)闡述?？赏茝V性：數(shù)學(xué)模型可以推廣到具有相同性質(zhì)的一類問題中。換句話說，解決了一個(gè)數(shù)學(xué)模型就解決了一類實(shí)際問

3、題。這里的“相同性質(zhì)”是指相同的本質(zhì)，表面看似毫不相干的問題可能有著相同的本質(zhì)。由于這一點(diǎn)也是由數(shù)學(xué)模型的抽象性決定的，因此數(shù)學(xué)模型的抽象化程度對(duì)數(shù)學(xué)模型的推廣范圍也有重要的影響，這一點(diǎn)將在第三部分中詳細(xì)闡述。二、數(shù)學(xué)模型的建立和比較由于考慮問題的角度不同，面對(duì)同一個(gè)實(shí)際問題，可能建立起各種各樣的數(shù)學(xué)模型。在各種數(shù)學(xué)模型中，我們要尋找的是效率高的模型。模型的效率同模型的抽象化程度有關(guān)，下面從一個(gè)實(shí)例中來分析它們之間的具體關(guān)系。【多邊形分割問題】將一個(gè)凸n邊形用n-3條互不相交的對(duì)角線分割為n-2個(gè)三角形,求分割方案的總數(shù).如:n=5時(shí),有以下幾種分割方案:這道題可用以下幾種方法來求解:<

4、1>.搜索法:這種方法的思路是將各種分割方案全都列舉出來。顯然，一組n-3條互不相交的對(duì)角線對(duì)應(yīng)于一種分割方案，因此可把問題看作是求不同的對(duì)角線組的數(shù)目。將n邊形的n個(gè)頂點(diǎn)按順時(shí)針方向編號(hào)為1、2、3n，則一條對(duì)角線可表示為一個(gè)數(shù)對(duì)(a1,a2)，a1、a2分別表示對(duì)角線兩端頂點(diǎn)的序號(hào)，a1<a2，a1為對(duì)角線的始端，a2為末端。對(duì)角線在對(duì)角線組中的順序是無關(guān)緊要的，因此，一個(gè)對(duì)角線組是一個(gè)集合，它的元素是對(duì)角線。判斷兩條對(duì)角線是否相交是一個(gè)必須解決的問題。設(shè)兩條對(duì)角線分別為(a1,a2)與(b1,b2)，若把表示對(duì)角線的數(shù)對(duì)看作開區(qū)間，那么兩條對(duì)角線不相交的充要條件是兩個(gè)區(qū)間有包

5、含關(guān)系或他們的交集為空集。于是，我們建立起解決本問題的第一個(gè)數(shù)學(xué)模型：已知：n的值, 一個(gè)集合由(n-3)個(gè)不同的開區(qū)間(i,j)組成, i1.n-2, ji+2.n,(i1)或(jn) 同一個(gè)集合中任兩個(gè)不同的開區(qū)間(i1,j1),(i2,j2)滿足： (i1,j1)(i2,j2)=空集)或(i1,j1)包含(i2,j2)或(i2,j2)包含(i1,j1)求：不同的集合的個(gè)數(shù)搜索時(shí)，先考慮以頂點(diǎn)1為始端的對(duì)角線，可以不連任何對(duì)角線(圖一中A)，也可以連(1,3)(圖一中B)，或連(1,4)(圖一中C)，或同時(shí)連(1,3)(1,4) (圖一中D)。對(duì)于每一種情況，再考慮以頂點(diǎn)2為始端的對(duì)角線，

6、依此類推。當(dāng)?shù)玫絥-3條互不相交的對(duì)角線時(shí)，便找到了一種方案(參見圖一)。 圖一在考慮以頂點(diǎn)i為始端的對(duì)角線時(shí)，有以下幾條規(guī)則必須遵循：1.與原有對(duì)角線相交的對(duì)角線不得選取。2.當(dāng)i>=3時(shí)，若頂點(diǎn)i-1為始端的對(duì)角線一條都未連，則對(duì)角線(i-2,i)必須是已經(jīng)連的。3.對(duì)角線的末端頂點(diǎn)序號(hào)必須大于i。否則，頂點(diǎn)i將成為對(duì)角線的末端，另一個(gè)頂點(diǎn)j(j<i)成為對(duì)角線的始端，這條對(duì)角線已在考慮以頂點(diǎn)j為始端的對(duì)角線時(shí)考慮過了，再考慮將引起重復(fù)。按照以上三條規(guī)則，即可得到如圖一的搜索樹(圖中打的葉結(jié)點(diǎn)為不同的分割方案)。搜索法的數(shù)學(xué)模型較為復(fù)雜，用它可以求出具體方案，但它的抽象化程度不

7、高，導(dǎo)致了求解時(shí)的低效率。為了使用上面的規(guī)則2來提高效率，求解過程還是從多邊形及其對(duì)角線本身來考慮的，數(shù)學(xué)模型的作用僅體現(xiàn)在判斷對(duì)角線是否相交上。用該方法編制的程序在n稍大時(shí)速度就很慢。(n=12時(shí)已需運(yùn)行時(shí)間16.2秒(486DX2/80)，測(cè)試結(jié)果見附表一。)<2>.遞推法:上一種方法的數(shù)學(xué)模型中有很多與問題的要求無關(guān)的內(nèi)容(如對(duì)角線的表示、對(duì)角線組的表示、每種具體方案)。在遞推法建立的數(shù)學(xué)模型中，我們只考慮凸n邊形的分割方案總數(shù)。設(shè)k邊形的分割方案總數(shù)為Ak，于是得到A數(shù)列：A3,A4,A5.考慮n邊形的分割方案總數(shù)An。任取n邊形的一條邊，不妨取邊(n-1,n), 若在某一

8、種分割方案中，邊(n-1,n)屬于三角形(i,n-1,n),那么就將分割方案歸入第i類，如圖二所示。圖二設(shè)第i類方案總數(shù)為Bi，則 計(jì)算Bi可用如下方法：對(duì)于第i類的方案，原n邊形已被分割為一個(gè)i+1邊形與一個(gè)(n-i)邊形，下面的工作分為兩步，第一步是將i+1邊形分割為三角形，有Ai+1種方案，第二步是將(n-i)邊形分割為三角形，有An-i種方案。為了表達(dá)的方便，令A(yù)2=1，于是有 將代入得： 于是，問題的數(shù)學(xué)模型即為：已知：n的值及數(shù)列A2,A3,A4, 該數(shù)列滿足： A2=1 , j>2求：An利用這個(gè)模型，我們即可很方便地依次求出A3,A4.An。遞推法的數(shù)學(xué)模型比搜索法的簡(jiǎn)明

9、，抽象化程度更高，效率也高得多。用遞推法編制的程序已能應(yīng)付中等數(shù)據(jù)，在n<100時(shí)不超過一秒。但當(dāng)n很大時(shí)仍然很慢，n=250時(shí)需18.7秒(486DX2/80)，測(cè)試結(jié)果見附表一。<3>.母函數(shù)法：上一種方法的數(shù)學(xué)模型中已去除了很多與問題的要求無關(guān)的內(nèi)容，但同時(shí)，問題只要求An,而上述方法卻將A3An都求出了。能否不求A3An-1而直接由n求出An呢？下面用母函數(shù)這種數(shù)學(xué)模型來解決這個(gè)問題。將A2,A3,A4作為冪級(jí)數(shù)的系數(shù)，令 如果能解出Y(x),那么也就求出了An.為了求Y(x),我們來看一下Y(x)2的值:而,因此有: -*x得:將代入，解出：各項(xiàng)系數(shù)均為負(fù)數(shù)，而Ai

10、>0,故： , 其中,于是，所以，于是得出了由n直接求出An的數(shù)學(xué)模型：已知：n的值， 求：An求解時(shí)用公式可直接計(jì)算An。在三個(gè)數(shù)學(xué)模型中，這一個(gè)表達(dá)最為簡(jiǎn)潔，抽象化程度最高。用它來求解的效率也最高。n=1000時(shí)不超過1秒,n=5000時(shí)也僅需14.7秒(486DX2/80)，測(cè)試結(jié)果見附表一與附表二。搜索法作為一種最基本的方法，建立在一個(gè)較為復(fù)雜的數(shù)學(xué)模型之上，它的特點(diǎn)是可以求出每一種分割方法，但用這種方法來求方案總數(shù)顯然針對(duì)性不強(qiáng)，因此效率很低。遞推法是建立在數(shù)列這個(gè)數(shù)學(xué)模型之上的，由于去除了很多不必要的因素，效率大為提高，對(duì)于n<=300時(shí)有較好的效果。利用母函數(shù)這種數(shù)學(xué)

11、模型求解，是對(duì)遞推法的一種數(shù)學(xué)優(yōu)化，得出了更為簡(jiǎn)潔的結(jié)論，當(dāng)n>300時(shí)充分顯示出其優(yōu)勢(shì)。從以上的分析中可以得出這樣的結(jié)論：數(shù)學(xué)模型的抽象化程度越高，它的效率越高。這個(gè)結(jié)論很容易理解，因?yàn)槌橄蠡潭仍礁?，?shù)學(xué)模型中與問題無關(guān)的成分就越少，于是效率也就越高。相反的，若抽象化程度不夠高，則數(shù)學(xué)模型中含有較多的與問題無關(guān)的成分，那么，效率也就要低一些。三、數(shù)學(xué)模型的推廣和應(yīng)用數(shù)學(xué)模型具有可推廣性。數(shù)學(xué)模型是建立在問題本質(zhì)的基礎(chǔ)上的，而不是建立在問題的表面現(xiàn)象上的。因此，雖然兩個(gè)問題表面毫無關(guān)系，只要它們有相同的本質(zhì)，就可以用相同的數(shù)學(xué)模型求解。然而，要看到兩個(gè)問題有相同的本質(zhì)并不是一件容易的事

12、。這需要我們拋開問題的表面現(xiàn)象，仔細(xì)地比較分析，在問題之間建立對(duì)應(yīng)關(guān)系。數(shù)學(xué)模型的可推廣性與數(shù)學(xué)模型的抽象化程度有著密切的關(guān)系。為解決同一個(gè)問題而建立起的不同的數(shù)學(xué)模型可能具有不同的可推廣性。下面將由母函數(shù)建立起的數(shù)學(xué)模型應(yīng)用于另一些問題的求解。【樹的計(jì)數(shù)問題】求具有n個(gè)結(jié)點(diǎn)的二叉樹的數(shù)目。設(shè)具有k個(gè)結(jié)點(diǎn)的的二叉樹的數(shù)目為Dk，則* 當(dāng)k=0時(shí)，是一棵空樹，只有一種。* 當(dāng)k>0時(shí)，二叉樹可分為根結(jié)點(diǎn)、具有i個(gè)結(jié)點(diǎn)的左子樹與具有k-1-i個(gè)結(jié)點(diǎn)的右子樹。于是具有k個(gè)結(jié)點(diǎn)的二叉樹的數(shù)目等于具有i個(gè)結(jié)點(diǎn)的二叉樹的數(shù)目與具有k-1-i個(gè)結(jié)點(diǎn)的二叉樹的數(shù)目的乘積。將以上的分析寫成公式，就是：比較

13、上文中A數(shù)列與這里的D數(shù)列可知 ,于是將上文中的數(shù)學(xué)模型(式)稍加變換，即得： 至此，我們已將這個(gè)問題用上面的數(shù)學(xué)模型解決了。這個(gè)問題與多邊形分割問題具有相同的本質(zhì)，即它們計(jì)數(shù)的規(guī)律是一致的，因此，它們可用相同的數(shù)學(xué)模型求解。為了將這種數(shù)學(xué)模型進(jìn)一步推廣，我們?cè)賹⑸弦粋€(gè)問題分析一下：將每棵二叉樹的n個(gè)結(jié)點(diǎn)一一編號(hào)，使每棵二叉樹的前序序列都是1,2,3,n。由于前序序列與中序序列可唯一確定一棵二叉樹，所以每棵二叉樹的中序序列與其它的二叉樹都是不同的。(一旦相同，那么這兩棵二叉樹就是同一棵二叉樹了。)另外，對(duì)于一棵前序序列確定的二叉樹，它的中序序列可以由前序序列進(jìn)棧與出棧生成。于是該數(shù)學(xué)模型又可直

14、接用于下面問題的求解?！净疖囘M(jìn)出棧問題】一列火車n節(jié)車廂，依次編號(hào)為1,2,3,n。每節(jié)車廂有兩種運(yùn)動(dòng)方式，進(jìn)棧與出棧，問n節(jié)車廂出棧的可能排列方式有多少種。將這個(gè)問題與上一個(gè)問題比較一下：列車原始的排列狀態(tài)(1,2,3,n)正是二叉樹的前序序列；列車車廂的進(jìn)棧與出棧對(duì)應(yīng)于二叉樹結(jié)點(diǎn)的進(jìn)棧與出棧；列車出棧后的排列狀態(tài)正是二叉樹的中序序列。將兩道題對(duì)應(yīng)起來看，不難發(fā)現(xiàn)，列車出棧后的可能排列方式的數(shù)目就是二叉樹的中序序列的數(shù)目，也就是二叉樹的數(shù)目。設(shè)n節(jié)車廂的排列方式有En種，則 于是，我們又用相同的數(shù)學(xué)模型解決了這個(gè)問題。將數(shù)學(xué)模型推廣到樹的計(jì)數(shù)問題時(shí)，我們只是比較了相似的遞推公式，可以說是一種

15、簡(jiǎn)單的推廣。而推廣到火車進(jìn)出棧問題時(shí)，則是從樹的計(jì)數(shù)問題出發(fā)，將兩個(gè)問題對(duì)應(yīng)起來看，進(jìn)行了很多邏輯分析，相比之下要復(fù)雜一些。事實(shí)上，很多數(shù)學(xué)模型的推廣應(yīng)用都需要進(jìn)行仔細(xì)的分析。從一個(gè)問題多邊形分割問題出發(fā)建立起的數(shù)學(xué)模型，公式中已完全略去了分割的具體內(nèi)容，只留下了問題的本質(zhì)：計(jì)數(shù)。由于公式表達(dá)了計(jì)數(shù)方法的實(shí)質(zhì)內(nèi)涵（;）,于是就給了它進(jìn)一步廣泛應(yīng)用于一類問題求解（外延）的可能。再考慮一下多邊形分割問題中搜索法的數(shù)學(xué)模型。在這兩個(gè)問題中，搜索法的數(shù)學(xué)模型顯然是不適用的。它包含著多邊形的每一種具體的分割方案，沒有很好的體現(xiàn)問題計(jì)數(shù)的本質(zhì)，因此影響了這種數(shù)學(xué)模型的可推廣性。在這兩個(gè)問題中，沒有相應(yīng)的概

16、念對(duì)應(yīng)于多邊形的分割方案，于是，搜索法的數(shù)學(xué)模型便對(duì)這兩個(gè)問題無能為力了。而數(shù)列與母函數(shù)兩種方法的數(shù)學(xué)模型仍能應(yīng)用于這兩個(gè)問題。這正是由于后兩種方法的數(shù)學(xué)模型更加抽象，所以更有利于它們的推廣。四、總結(jié)以上三個(gè)實(shí)例充分說明了數(shù)學(xué)模型的高效性、可推廣性以及它們與抽象性之間的關(guān)系。數(shù)學(xué)模型具有高效性。從實(shí)際問題中建立起來的數(shù)學(xué)模型可以去除無關(guān)的內(nèi)容，關(guān)系清晰，有利于效率的提高。數(shù)學(xué)模型具有可推廣性。從實(shí)際問題中建立求解的數(shù)學(xué)模型，一個(gè)數(shù)學(xué)模型建立后，往往能將其應(yīng)用于一類實(shí)際問題中。乍一看分割多邊形與火車進(jìn)出棧沒有什么聯(lián)系，但通過對(duì)模型的理解可以發(fā)現(xiàn)兩個(gè)問題有著密切的內(nèi)在聯(lián)系：它們是可以用相同的數(shù)學(xué)模

17、型來求解的。數(shù)學(xué)模型的高效性與其抽象性是緊密聯(lián)系的。數(shù)學(xué)模型越是抽象，它的效率也就越高。數(shù)學(xué)模型的可推廣性與其抽象性也是緊密聯(lián)系的。數(shù)學(xué)模型越是抽象，它也就越容易被廣泛應(yīng)用?！靖郊扛奖硪?按以上三種數(shù)學(xué)模型設(shè)計(jì)的程序的運(yùn)行時(shí)間的比較n運(yùn)行時(shí)間(秒)(486/80)結(jié)果搜索法遞推法母函數(shù)法50.00.00.0580.10.00.0132100.60.00.01430113.20.00.048621216.80.00.016796200.00.0477638700300.10.0263747951750360400.10.0176733862787006701400500.10.01313278

18、98242169365477991900700.30.0862189239989602857261856406637011085001000.80.0577433580696013577821877006080428563340207316247566110001503.10.0395931314705700199288849001887875768045136379261179347490255197092054195896420693878002008.30.132497017144692472040610304198911001293287035403710045969725655314

19、58474030562929950769133018913041197185787156730200025018.70.12942109465114274900932013291224718543203864499126811120331716878369694940021100392829583154627202225799961741962546561436757757673959435471617200030037.10.128336159511286454919521412986993508946492467649011644182088598624691519032559650708

20、037365499927532029654393447069621322187712454333678323104526897225807029224162563399190436400附表二:母函數(shù)法在大數(shù)據(jù)下的運(yùn)行時(shí)間與結(jié)果n運(yùn)行時(shí)間(秒,486/80)結(jié)果5000.23392161481258547533436328676042834151806671371051948224646322289022038948496166601639408765893556171082850730432307258421940116521369412511180867674338311172552510

21、939522166767521815497540392540790095187478344663677858462596953622134102520200986176150660638780745851952786342361786271048679068000010000.61282659123120329389992418907864563882089032052318971850610071333658659691765063650897139226963638433013116953018320642351981875889124159470833343280158645658935

22、509878521083681017093125902282959380094332416205262471921409995611627511580863150740180266996754602824885598197887476283926138637334480765160463004590372133777681615368106466120718442527784572428185999328099100855162000191915961265732157462162582417171059495969450867257526779399630744193300422624617

23、85897282518971742893682255505361949539216436303974544929904457402642729850569605966260001940761086095518361490603411114114203867955760000500014.719905339832928463251666735064542780033892729043055532801808728231002712118767340856613205258009823911061689822819966058800117396543598135427586955979277842

24、961401469078660617117152832008304504467148992497204750152333424681387245738408957397390338114207845815084568665148437280856840230967715381553578655967556776543982717552905537280360991836287529653206624959870630812189563333973096972516126687564907702194700263153050115660540146608575975363529153692218

25、249926313524921858319785702196735344867807463504348872703806682765573357532768717863477686122111338669153041998736992669734521138413688462392159022510881310783385941375507549192495429624236359659446666714466733587718312466406881420407038563387766299777666596542552681593789751044519117369900869457690

26、210352595228237709489430574007459436019028016411003882769603558591538735119909737530133155629358089049391809862238075523338926805216933129970680691440105112827804459129710748612740519928346396310561216451805165334432417634618203226858919012500057666732553341830111147081953381212098801044506100316055

27、701817255481733710839405910817391555358217379876468756521829985817456662836784051933862876336442379104782160425463668803378393982395552054129650108630734033416898205271951432275542407693181972145504049297679210194767139351476886047150741289145932752011801726967868777499720314688862911165999548592301

28、937072723328901057052436143506735132885611033291722431843274758902459024223795911169335414024073046732892739564545922432905224799085464497202402997282733137731310719608622106276501882028336819556964548549688683732435397553570938429083111251874432091140686683008816625997915385029705586103119596051190

29、592857213107922653357349746186059611137886983234469885608979844431651549099541746029385575852137806596749721523221127343135867182891487011568951711326856798704310038096674186956424692388366951410846587759001196659372267179038623797279196316562398830984412873244470742052846537606041784053088409888045

30、514186391246641760325928428494459232631616309597601726856079967431552494414587401845403416372467040622320018510892266507167328210681172963043341422470770335588144820328106566130073642731478993587898294358144441027403100084849180337482629142341773312023189985922445391014019546665700263830349608832536

31、195648751981624029939353157525782759785276380074202722356998363216687878275696045979921454028604592868678143415538500876808621326198067856118733223377604856649465535333664011510121428013809253621167461643010574515280289659464539972118062862177079566215629850386783557684491180752622175613789741648825

32、914331354210963270936833659374268491468972427208500546964901388649622735082574922446881704986256189184592919178448768329320131803124374833760877058196194803111496823543186375259372960899823055880506318903220600017289601481824577309204574653990705723667738054032269169861595942214810326174703715814957

33、19930597851695669555189979332882416754183716357001209090944294741473972997610488038219507132437063465054808258284329237819893018092810058281353800000【程序】1.多邊形分割問題 搜索法 (sousuo.pas)$A+,B-,D-,E-,F-,G+,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y-$M 16384,0,655360Program SouSuo;Const Max=30;Type TPara=record l,r:

34、integer;end; 區(qū)間類型Var method:Longint; 方案總數(shù) Para:array1.Maxof TPara; 區(qū)間組 n:integer; time:Longint;Function M(a,b:integer):integer;高精度整數(shù)類型begin if a<b then m:=b else m:=a;end;Procedure Make; 搜索多邊形的所有分割方案Var i,j:integer; sp,lp1,lp2:integer; Function Connect:boolean; 判斷新加入?yún)^(qū)間組的區(qū)間是否與原有的區(qū)間有沖突 var i,j,k:in

35、teger;b1,b2:boolean; begin j:=parasp.l;k:=parasp.r; Connect:=true; for i:=1 to sp-1 do begin if (j=parai.l)or(j=parai.r) then continue; if (k=parai.l)or(k=parai.r) then continue; if (j>parai.l)and(j<parai.r)xor (k>parai.l)and(k<parai.r) then exit; end; Connect:=false; end; Function PreFa

36、lse:boolean; 檢驗(yàn)是否有其它的沖突 var i:integer;j,k:integer; begin prefalse:=false;j:=parasp.l; if j<=2 then exit; for i:=1 to sp do if (parai.l=j-1)or(parai.r=j-1) then exit; k:=j;j:=k-2; for i:=1 to sp do if (parai.l=j)and(parai.r=k) then exit; PreFalse:=true; end; Function Pop:boolean;forward; Function

37、Push:boolean; 入棧 begin inc(sp); Parasp.l:=lp1;Parasp.r:=lp2; Push:=(lp1=1)and(lp2=n)or(lp1>n)or(lp2>n)or connect; if prefalse then begin Push:=true;pop;exit;end; inc(lp2); if lp2>n then begin inc(lp1);lp2:=lp1+2;end; end; Function Pop:boolean; 出棧 begin if sp=0 then begin dec(sp);pop:=false;

38、exit;end; lp1:=Parasp.l;lp2:=parasp.r;dec(sp); inc(lp2); if lp2>n then begin inc(lp1);lp2:=lp1+2;end; Pop:=(lp1>n)or(lp2>n); end;begin sp:=0; 棧頂指針置0 lp1:=1;lp2:=3; method:=0; while (sp>=0) do begin if Push then while pop do; if sp=n-3 then 獲得了一種方案 begin method:=method+1; while pop do; en

39、d; end; writeln('Total: ',method);end;var i:integer;s:string;BEGIN write('Input N: '); readln(n);輸入多邊形邊數(shù) time:=MemL$40:$6c; if n<3 then writeln('Total: 0') else if n=3 then writeln('Total: 1') else MAKE; 搜索多邊形的所有分割方案 writeln('Time: ',(Meml$40:$6c-time)/18.2

40、:5:1); 輸出所用的時(shí)間END.2.多邊形分割問題 遞推法 (ditui.pas)$A+,B-,D-,E-,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-$M 16384,0,655360Program DiTui;Const Len=100;Max=300;Type Th=array-1.Len+1of integer;高精度整數(shù)類型Var method:array1.Maxof Th; i邊形分割方案總數(shù)為methodi n:integer; 要求的多邊形的邊數(shù) time:Longint;Function M(a,b:integer):integer

41、; 取最大值begin if a<b then m:=b else m:=a;end;Procedure Add(var a:Th;b:Th); a:=a+b;a,b為高精度整數(shù)類型var i,j:integer;begin j:=0; a-1:=m(a-1,b-1); for i:=0 to a-1 do begin inc(j,ai+bi); ai:=j mod 10000; 每位integer存4位十進(jìn)制數(shù) j:=j div 10000; end; if j<>0 then begin inc(a-1);aa-1:=j;end;end;Procedure Mul(a,b

42、:Th;var c:Th); c:=a*b;a,b,c為高精度整數(shù)類型var i,j:integer;k:Longint;begin fillchar(c,sizeof(Th),0); for i:=0 to a-1 do begin k:=0; for j:=0 to b-1 do if i+j<=Len then begin inc(k,longint(ai)*bj+ci+j); ci+j:=k mod 10000; k:=k div 10000; end; inc(ci+b-1+1,k); end; c-1:=a-1+b-1; if cc-1+1<>0 then inc

43、(c-1);end;Procedure OutHigh(a:Th); 輸出高精度整數(shù)var s:string4;i,j:integer;begin write('Total: '); j:=a-1;write(aj); for i:=j-1 downto 0 do begin str(ai,s);while s0<#4 do s:='0'+s; write(s); end; writeln;end;Procedure Make; 遞推計(jì)算多邊形分割總數(shù)var i,j:integer;a:Th;begin fillchar(method,sizeof(met

44、hod),0); method2,0:=1; method3,0:=1; fillchar(a,sizeof(a),0); for i:=4 to N do for j:=1 to i-2 do begin mul(methodj+1,methodi-j,a); Add(methodi,a); end; OutHigh(methodn);end;var i:integer;s:string;BEGIN write('Input N: '); readln(n); 輸入多邊形邊數(shù) time:=MemL$40:$6c; if n<3 then writeln('Tot

45、al: 0') else MAKE;遞推計(jì)算多邊形分割總數(shù) writeln('Time: ',(Meml$40:$6c-time)/18.2:5:1); 輸出所用的時(shí)間END.3.多邊形分割問題 母函數(shù)法 見muhanshu.Pas$A+,B-,D-,E-,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-$M 16384,0,655360Program MuHanShu;Const Len=1400;Max=6000;Type Th=array0.Len+1of integer;高精度整數(shù)類型1,按位存儲(chǔ) Ty=array0.Maxof

46、 integer;高精度整數(shù)類型2,按因數(shù)存儲(chǔ)Var fi,fo:text;fin,fon:string; n:integer; time:Longint;Procedure Mul(var a:Th;b:integer); a:=a*b;a為高精度整數(shù)類型1Var i:integer;k:Longint;begin k:=0; for i:=1 to a0 do begin k:=k+ai*longint(b); ai:=k mod 10000; k:=k div 10000; end; if k<>0 then begin inc(a0);aa0:=k;end;end;Func

47、tion MaxPublic(a,b:integer):integer; a,b的最大公因數(shù)var i:integer;begin repeat a:=a mod b; if a=0 then break; b:=b mod a; until b=0; MaxPublic:=a+b;end;Procedure Divide(var k:Ty;h:integer);k:=k div h;k為高精度整數(shù)類型2Var i,j:integer;begin for i:=1 to k0 do if ki mod h =0 then begin ki:=ki div h; if ki=1 then beg

48、in ki:=kk0;dec(k0);end; exit; end; for i:=k0 downto 1 do if MaxPublic(ki,h)>1 then begin j:=MaxPublic(ki,h); h:=h div j;ki:=ki div j; if ki=1 then begin ki:=kk0;dec(k0);end; if h=1 then exit; end;end;Procedure translate(k:Ty;var a:Th);a:=k;a為高精度整數(shù)類型1,k為高精度整數(shù)類型2Var i:integer;begin a1:=1;a0:=1; for

49、 i:=1 to k0 do mul(a,ki);end;Procedure Make;按公式計(jì)算多邊形分割總數(shù)Var i,j:integer;k:Ty;a:Th;s:string4;begin k0:=n-2; for i:=1 to n-2 do ki:=(2*n-3-i); for i:=n-2 downto 2 do divide(k,i); divide(k,n-1); translate(k,a); write('Total: '); j:=a0;write(aj); for i:=j-1 downto 1 do begin str(ai,s);while s0&l

50、t;#4 do s:='0'+s; write(s); end; writeln;end;var i:integer;s:string;BEGIN write('Input N(<=',Max,'): '); readln(n); 輸入多邊形邊數(shù) time:=MemL$40:$6c; if n<3 then writeln('Total: 0') else MAKE; 按公式計(jì)算多邊形分割總數(shù) writeln('Time: ',(Meml$40:$6c-time)/18.2:5:1); 輸出所用的時(shí)間END.4.樹的計(jì)數(shù)問題、火車進(jìn)出棧問題 (tuiguang.pas)$A+,B-,D-,E-,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-$M 16384,0,655360Program TuiGuang;Const Len=1400;Max=50