1、數(shù)學(xué)模型及其在信息學(xué)競賽中的應(yīng)用上海市復(fù)旦附中高三（8）班郭一【關(guān)鍵字】數(shù)學(xué)模型，可靠性，可解性【引言】數(shù)學(xué)模型是人們解決現(xiàn)實(shí)問題的有力武器。人們把現(xiàn)實(shí)問題經(jīng)過科學(xué)地抽象、提煉得到數(shù)學(xué)模型，再用數(shù)學(xué)方法去解決。數(shù)學(xué)模型可分為離散和連續(xù)兩種。連續(xù)數(shù)學(xué)模型需要大量的高等數(shù)學(xué)知識(shí)，中學(xué)生很少接觸。在信息學(xué)競賽經(jīng)常出現(xiàn)的則是離散數(shù)學(xué)模型。本文主要介紹的就是離散數(shù)學(xué)模型的一般概念及建立方法【正文】 所謂數(shù)學(xué)模型，就是現(xiàn)實(shí)世界中某一類特殊的運(yùn)動(dòng)變化過程、關(guān)系或結(jié)構(gòu)的一種模擬性的數(shù)學(xué)結(jié)構(gòu)，其實(shí)也就是對(duì)現(xiàn)實(shí)模型進(jìn)行科學(xué)抽象后得到的模型。在信息學(xué)競賽中，試題給出的問題通常是一個(gè)現(xiàn)實(shí)問題，這也就需要選手在審清題意

2、后首先把問題的關(guān)鍵因素總結(jié)、提煉出來，形成一個(gè)抽象的數(shù)學(xué)模型，這樣有利于問題的分析與解決。 一般來說，我們?cè)诮庖坏烙嘘P(guān)現(xiàn)實(shí)問題的試題時(shí)，需要分以下幾個(gè)步驟： 審清題意，了解題目的來龍去脈，弄清哪些量是已知的（輸入），需要求什么（輸出），數(shù)據(jù)規(guī)模如何等等。這是解決問題的前提。 建立模型，使之能夠簡潔高效地表達(dá)出題目給出的現(xiàn)實(shí)模型。 解決模型，得出算法。建模之后就是要解決模型。這步順利與否很大部分上取決于所建模型的可解性如何。 編程實(shí)現(xiàn)。 其中，、兩步是關(guān)鍵。模型建立與解決得好與壞對(duì)能否成功解決該題起著決定性的作用。（一） 對(duì)于同一個(gè)現(xiàn)實(shí)問題，可能可以建立不同的數(shù)學(xué)模型 這種現(xiàn)象十分普遍，也就是平

3、時(shí)所說的一題多解。既然如此，這里有必要討論一下數(shù)學(xué)模型的選擇問題，其實(shí)也就是評(píng)判一個(gè)模型好壞標(biāo)準(zhǔn)的問題。一個(gè)好的數(shù)學(xué)模型不僅要能夠準(zhǔn)確地反映出現(xiàn)實(shí)模型（可靠性），所建立的模型還必須能夠被有效地解決（可解性）。這里“有效”指的是解決它的算法所需的空間與時(shí)間都在可以承受的范圍之內(nèi)。通常在解一些要求最優(yōu)解或要求準(zhǔn)確計(jì)數(shù)的一類具有唯一正確解的試題時(shí)，我們一般在保證可靠性的前提下，盡量提高模型的可解性。若幾個(gè)模型都具有可靠性，則當(dāng)然可解性越強(qiáng)的模型越好。 例： 最佳旅行路線問題 IOI93 【問題描述】你在加拿大航空公司組織的一次競賽中獲獎(jiǎng)，獎(jiǎng)品是一張免費(fèi)機(jī)票，可在加拿大旅行，從最西的一個(gè)城市出發(fā)，單方

4、向從西向東經(jīng)若干城市到達(dá)最東的一個(gè)城市（必須到達(dá)最東的城市）；然后再單方向從東向西飛回起點(diǎn)（可途徑若干城市）。除起點(diǎn)城市外，任何城市只能訪問次，起點(diǎn)城市被訪問次：出發(fā)一次；返回一次。除指定的航線外，不允許乘其他航線也不允許使用其他交通工具。求解的問題是：給定城市表列及兩城市之間的直通航線表列，請(qǐng)找出一條旅行路線，在滿足上述限制條件下，使訪問的城市數(shù)盡可能多。 這是一個(gè)現(xiàn)實(shí)問題，我們首先可以做如下的抽象：把每個(gè)城市抽象成一個(gè)頂點(diǎn)。不妨設(shè)由西到東的城市對(duì)應(yīng)編號(hào)分別是1至n。若兩個(gè)城市之間有直通航線，則在相應(yīng)的兩點(diǎn)之間連一條邊。這樣，所有城市與直通航線就被抽象成了一個(gè)無向圖。 【盲目搜索】這是最原始

5、的想法。我們一開始假想有兩架飛機(jī)都從最西邊的城市飛向最東邊的城市，并且在搜索的過程中保證兩條路線中的城市除起點(diǎn)與終點(diǎn)外都不相同。記下所有找到的路線中所經(jīng)城市最多的方案，把其中的一條作為向東旅行的路線，一條作為向西旅行的路線，合并起來即得最佳旅行路線。 因?yàn)樗阉鞯臅r(shí)間復(fù)雜度是指數(shù)級(jí)的，所以這樣做的話，時(shí)間效率不夠理想。究其主要原因就是所有模型的抽象程度不夠，沒有把試題中的限制充分融入數(shù)學(xué)模型中，盲目性太大?！揪W(wǎng)絡(luò)流模型】為了把更多的試題中的限制融入模型中，我們?cè)谠械哪Ｐ偷幕A(chǔ)上建立了如下的最大費(fèi)用最大流的模型：1） 為了保證每個(gè)城市最多只能被訪問一次，我們把每個(gè)城市i拆成兩個(gè)頂點(diǎn)i和i，并在兩

6、個(gè)頂點(diǎn)之間連接一條i至i的有向弧，單位費(fèi)用設(shè)為0。2） 將原圖中的無向邊改為有向?。喝舫鞘衖到城市j有直通航線（ij，或i=j=n時(shí)，我們考慮i的前趨頂點(diǎn)，不妨設(shè)為k。此時(shí)，到達(dá)頂點(diǎn)k與j的兩條路線的所需乘航線之和也一定最大，否則與fi,j最大矛盾。若ij時(shí)，結(jié)論同理可得。由此，我們有如下的動(dòng)態(tài)規(guī)則方程：f i, i 無意義 (1in）實(shí)際最多可能的訪問城市數(shù)為f n,n-2。時(shí)間復(fù)雜度降為O（N2）。 對(duì)于最佳旅行路線這一個(gè)問題，我們建立了三種不同的數(shù)學(xué)模型。這三種模型都具有可靠性（可以得出最優(yōu)解），但可解性不同。一般來說，建立的模型越簡潔，抽象程度越高，算法實(shí)現(xiàn)時(shí)不必要的操作也越少，運(yùn)行效

7、率也就越高。 值得注意的是，最近的一些競賽中有時(shí)會(huì)出現(xiàn)根據(jù)解的近似程度給分的題目。對(duì)于這類題目，我們更多考慮的則是所建模型的可解性。當(dāng)然，可靠性的降低也是有限度的，這個(gè)限度就是方案的可行性及誤差允許范圍。此外，許多數(shù)學(xué)模型有近似解法，這些都是通過適當(dāng)犧牲模型自身可靠性來提高模型的可解性。 （二）一個(gè)模型可能同時(shí)適用于多個(gè)現(xiàn)實(shí)問題。 這也就是我們要研究數(shù)學(xué)模型的主要原因之一。我們解決一個(gè)數(shù)學(xué)模型就相當(dāng)于解決了一類問題。比如說，最短路徑問題，可謂在現(xiàn)實(shí)生活中無處不在，上文中提到的網(wǎng)絡(luò)流的模型也有著很高的實(shí)用價(jià)值。這些數(shù)學(xué)模型的解決使得許多實(shí)際問題迎刃而解。然而，數(shù)學(xué)模型的解決只是解決一個(gè)現(xiàn)實(shí)問題的

8、一半，另一半就是如何將現(xiàn)實(shí)問題轉(zhuǎn)化為一個(gè)已經(jīng)解決的數(shù)學(xué)模型，即如何建模。建模在現(xiàn)實(shí)與抽象之間起著橋梁的作用。尤其在競賽中，后者有時(shí)顯得更為重要。（三） 如何建立數(shù)學(xué)模型？ 要能夠建立數(shù)學(xué)模型，首先必須熟悉一些經(jīng)典的數(shù)學(xué)模型及其算法。這是建模的基礎(chǔ)，沒有這個(gè)基礎(chǔ)則根本談不上建立什么數(shù)學(xué)模型。競賽中許多問題最終都可以轉(zhuǎn)化為經(jīng)典的數(shù)學(xué)模型，因此必須掌握這些常見的模型。 其次建立數(shù)學(xué)模型需要選手有把實(shí)際問題相互聯(lián)系，類比的能力。上文已經(jīng)指出許多實(shí)際模型都有著相同或相似的數(shù)學(xué)模型。既然這樣，它們之間必然存在著一些相同或相似。相互聯(lián)系、類比是發(fā)掘這些信息的有效手段。這里先給出一個(gè)大家都很熟悉的模型： 【凸

9、n邊形分割】一個(gè)凸n邊形，可以通過不相交的(n-3)根對(duì)角線，把n邊形拆分成(n-2)個(gè)三角形。求方案數(shù)hn。當(dāng)n=5時(shí)，方案數(shù)h5=5。 【配對(duì)括號(hào)序列】求由n個(gè)左括號(hào)(，n個(gè)右括號(hào))，能組成多少種不同的配對(duì)括號(hào)序列，記作Qn。一個(gè)序列的配對(duì)與否定義如下： 1（）是配對(duì)的。2若A是配對(duì)的，則(A)也是配對(duì)的。3若A、B都是配對(duì)的，則AB也是配對(duì)的。這兩題的模型都是大家十分熟悉的Catalan數(shù)Cn=1/(n+1)*C(2n,n)。通過數(shù)學(xué)計(jì)算可知，hn=Cn-2，Qn=Cn（證明略）。 【結(jié)和律】有n個(gè)數(shù)a1,a2,a3,an依據(jù)加法結(jié)合律，不改變其順序，只用括號(hào)表示成對(duì)的和，問有幾種求和方

10、案Pn？ 因?yàn)轭}目只要求求配對(duì)方案數(shù)，與a1,a2,a3,an的值無關(guān)。我們不妨令S=a1+a2+a3+an，并把a(bǔ)i（0=i Si-p (pin)Si Si-q (qin) 我們?cè)俳ㄒ粋€(gè)有向圖，共有n1個(gè)頂點(diǎn)，分別是S0至Sn，若SiSj，那么就從Si往Sj引一條邊。如圖（n=6,p=5,q=3）。這樣對(duì)于S0,S1,Sn來說，他們必須是拓?fù)溆行虻模⊿00），反過來，任何一組S0Sn都惟一地對(duì)應(yīng)一個(gè)整數(shù)數(shù)列?，F(xiàn)在，我們已經(jīng)把這道題目輪換為一個(gè)圖論的拓?fù)渑判虻膯栴}，而這個(gè)問題又是我們非常熟悉的。程序見附錄。回到NOI99的那道題，將此題與CEOI94的那題相互聯(lián)系，我們發(fā)覺這兩題都涉及到連續(xù)這

11、個(gè)概念。我們也同樣可以建一個(gè)圖，頂點(diǎn)分別表示S0Sn，這里Sn表示所求串第i位以前（包括第i位）1的出現(xiàn)次數(shù)。略有不同的是，這次不但Si與Sj之間有大小關(guān)系，還需要表示出到底大多少。我們把這個(gè)量作為Si與Sj之間的邊上的權(quán)。具體地說，若SjSi+k，則我們就從Si向Sj引一條權(quán)為k的單向邊。至此，題目中的兩個(gè)條件都已經(jīng)在圖中體現(xiàn)出來了。還有一點(diǎn)需要注意的是，本題與上題不同，它要求每個(gè)字符非 0 即 1 ，所以我們也需要把這點(diǎn)體現(xiàn)在圖中，即再加2n個(gè)不等式：Si+1Si，Si+1Si+1。接下來的問題就是求其它各點(diǎn)到S0的最長路。其實(shí)，本題與上題都可以轉(zhuǎn)化為同一個(gè)模型，即圖論最長路問題，因?yàn)槲覀?/p>

12、可以把上題圖中邊的權(quán)就看作是1。初看上去，以上兩題都似乎與圖論無甚關(guān)系。題目中并沒有出現(xiàn)圖論中常見的“城市”，“終端”等頂點(diǎn)，也沒有“鐵路”，“線路”等邊，還沒有“長度”，“傳輸時(shí)間”等權(quán)，但都確確實(shí)實(shí)用圖論模型漂亮地解決了，不由地讓人發(fā)出感嘆真沒想到呀！其實(shí)，想到與沒想到雖就一念之差，卻不是偶然的：這里面既有經(jīng)驗(yàn)的因素，也與你所掌握數(shù)學(xué)模型的多少有關(guān)，更重要的則是你的創(chuàng)造力。在上兩題中把Si作為頂點(diǎn)，大小關(guān)系作為邊，以及權(quán)的確定都不可以不說是一種創(chuàng)造。而正是它們?cè)谏蟽深}的解決中起了關(guān)鍵性的作用。 縱觀人類的進(jìn)步史， 創(chuàng)造力有著舉足輕重的作用。計(jì)算機(jī)發(fā)展至今，無論是性能的提高，軟件的發(fā)展，還是

13、網(wǎng)絡(luò)的誕生，處處體現(xiàn)了人類非凡的創(chuàng)造力。創(chuàng)造力是研究信息學(xué)的基本素質(zhì)之一，也是信息學(xué)競賽考察的重點(diǎn)。【參考書目】青少年國際和全國信息學(xué)（計(jì)算機(jī)）奧林匹克競賽指導(dǎo)叢書組合數(shù)學(xué)的算法與程序設(shè)計(jì)吳文虎、王建德編著圖論的算法與程序設(shè)計(jì)吳文虎、王建德編著 清華大學(xué)出版社數(shù)學(xué)模型基礎(chǔ)王樹禾編著 中國科學(xué)技術(shù)大學(xué)出版社【附程序】Black and White，CEOI94:$A+，B-，D-，E-，F(xiàn)-，G+，I-，l-，N-，O-，P-，Q-，R-，S-，T-，V-，X-$M 65520，0，655360program Black_and_White(input, output);const maxn =

14、 1000;var i, n, p, q, count: integer;count: 拓樸排序的序號(hào) s, d: array0.maxn of integer; di為頂點(diǎn)i的入度 next: boolean;拓樸排序結(jié)束標(biāo)記begin write(n,p,q = ); readln(n, p, q);計(jì)算入度 fillchar(d, sizeof(d), 0); for i := 0 to n do begin if i + p = n then inc(di + p); S(i) = 0 then inc(di - q); S(i) S(i-q) end;拓樸排序 count := 0;

15、 repeat next := false; for i := 0 to n do if di = 0 then begin si := count; inc(count); if i + p = 0 then dec(di - q); di := -1; next := true; end; until not next or (count = n + 1);直到所有頂點(diǎn)已被賦上序號(hào)或無0度頂點(diǎn)為止輸出 if count n + 1 then存在環(huán) writeln(NO) else for i := 1 to n do writeln(si - si - 1);end.01串，NOI99：$

16、A+，B-，D-，E-，F(xiàn)-，G+，I-，l-，N-，O-，P-，Q-，R-，S-，T-，V-，X-$M 65520，0，655360program sequence (input，output)；const inputfile=input.txt； 輸入文件名串 outputfile=output.txt； 輸出文件名串 var head:array0.1000，1.6of record 有向圖。headi，k頂點(diǎn)k引出的第k條有向邊，其中 no，v:integer；headi，k.no為該邊的終點(diǎn)序號(hào)；headi，k.v為該邊的權(quán) end； num:array0.1000of shorti

17、nt； numi頂點(diǎn)i引出的邊數(shù) s:array0.1000of integer； si0位i位中1的個(gè)數(shù) n，a0，b0，l0，a1，b1，l1:integer；n串長；l0，a0，b0連續(xù)長度為l0的子串中，0的個(gè)數(shù)的下限和上限為a0、b0；l1，a1，b1連續(xù)長度為l1的子串中，1的個(gè)數(shù)的下限和上限為a1、b1procedure addedge(a，b，c:integer)； 從頂點(diǎn)a 出發(fā)，構(gòu)造一條權(quán)為c的有向邊 begin inc(numa)； 累計(jì)頂點(diǎn)a引出的邊數(shù) heada，numa.no:=b； 設(shè)置該邊的終點(diǎn)和權(quán) heada，numa.v:=c； end； addedgepr

18、ocedure init； 輸入數(shù)據(jù)，構(gòu)造有向圖head var i:integer； begin readln(n，a0，b0，l0，a1，b1，l1)； 輸入數(shù)據(jù) fillchar(head，sizeof(head)，0)； 有向圖初始化 for i:=1 to n do begin 逐個(gè)頂點(diǎn)地構(gòu)造有向圖 if i=l0 then begin 根據(jù)a0l0-(si-)b0構(gòu)造有向邊 addedge(i，i-l0，a0-l0)； addedge(i-l0，i，l0-b0)； end； then if i=l1 then begin 根據(jù)a1si-b1構(gòu)造有向邊 addedge(i-l1，i，

19、a1)； addedge(i，i-l1，-b1)； end； then addedge(i-1，i，0)； 根據(jù)si-1si構(gòu)造有向邊 addedge(i，i-1，-1)； 根據(jù)sisi-1+1構(gòu)造有向邊 end； for end； initprocedure main； 計(jì)算頂點(diǎn)0至其余頂點(diǎn)的最長路徑 var i，j，k:integer； begin fillchar(s，sizeof(s)，0)； s數(shù)組清零 for i:=1 to n do 逐條邊地延長路徑 for j:=0 to n do 枚舉第i條邊的所有可能情況 for k:=1 to numj do if sj+headj，k.vsheadj，k.no 若