數(shù)學(xué)建模在OI中的應(yīng)用

《數(shù)學(xué)建模在OI中的應(yīng)用》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)學(xué)建模在信息學(xué)競賽中的應(yīng)用江蘇省常州高級中學(xué)曹文一、概述實(shí)際問題往往是紛繁而復(fù)雜的，而其中的規(guī)律也是隱藏著的，要想直接用計(jì)算機(jī)來求解實(shí)際問題往往有一定的困難。計(jì)算機(jī)擅長的是解決數(shù)學(xué)問題。因此，我們有必要將實(shí)際問題抽象成數(shù)學(xué)模型，然后再用計(jì)算機(jī)來對數(shù)學(xué)模型進(jìn)行求解。數(shù)學(xué)模型(MathematicalModel)：對于現(xiàn)實(shí)中的原型，為了某個特定目的，作出一些必要的簡化和假設(shè)，運(yùn)用適當(dāng)?shù)臄?shù)學(xué)工具得到一個數(shù)學(xué)結(jié)構(gòu)。也可以說，數(shù)學(xué)建模是利用數(shù)學(xué)語言（符號、式子與圖象）模擬現(xiàn)實(shí)的模型。把現(xiàn)實(shí)模型抽象、簡化為某種數(shù)學(xué)結(jié)構(gòu)是數(shù)學(xué)模型的基本特征。它或者能解釋特定現(xiàn)象的現(xiàn)實(shí)狀態(tài)，或者能預(yù)測到對

2、象的未來狀況，或者能提供處理對象的最優(yōu)決策或控制。與實(shí)際問題相比，數(shù)學(xué)模型有以下幾個性質(zhì)：1.抽象性：數(shù)學(xué)模型是實(shí)際問題的一種抽象，它去除了實(shí)際問題中與問題的求解無關(guān)的部分，簡明地體現(xiàn)了問題的本質(zhì)。這一點(diǎn)是下面兩個性質(zhì)的基礎(chǔ)。2.高效性：數(shù)學(xué)模型中各個量之間的關(guān)系更為清晰，容易從中找到規(guī)律，從而提高求解的效率。由于這一點(diǎn)是由數(shù)學(xué)模型的抽象性決定的，因此數(shù)學(xué)模型的抽象化程度對數(shù)學(xué)模型效率的高低有重要的影響。3.可推廣性：數(shù)學(xué)模型可以推廣到具有相同性質(zhì)的一類問題中。換句話說，解決了一個數(shù)學(xué)模型就解決了一類實(shí)際問題。這里的“相同性質(zhì)”是指相同的本質(zhì)，表面看似毫不相干的問題可能有著相

3、同的本質(zhì)。由于這一點(diǎn)也是由數(shù)學(xué)模型的抽象性決定的，因此數(shù)學(xué)模型的抽象化程度對數(shù)學(xué)模型的推廣范圍也有重要的影響。二、建立數(shù)學(xué)模型的方法和步驟1.模型準(zhǔn)備首先要了解問題的實(shí)際背景，明確建模目的，搜集必需的各種信息，盡量弄清對象的特征。在信息學(xué)競賽中這一步意味著：審清題意，了解題目的來龍去脈，弄清哪些量是已知的（輸入），需要求什么（輸出），數(shù)據(jù)規(guī)模如何等等，這是解決問題的前提。2.建立模型根據(jù)所作的假設(shè)分析對象的因果關(guān)系，利用對象的內(nèi)在規(guī)律和適當(dāng)?shù)臄?shù)學(xué)工具，構(gòu)造各個量間的等式關(guān)系或其它數(shù)學(xué)結(jié)構(gòu)，使之能夠簡潔高效地表達(dá)出題目給出的現(xiàn)實(shí)模型。不過我們應(yīng)當(dāng)牢記，建立數(shù)學(xué)模型是為了讓更多的

4、人明了并能加以應(yīng)用，因此工具愈簡單愈有價(jià)值。3.模型求解15建模之后就是要解決模型。這步順利與否很大部分上取決于所建模型的可解性如何。可以采用解方程、畫圖形、證明定理、邏輯運(yùn)算、數(shù)值運(yùn)算等各種傳統(tǒng)的和近代的數(shù)學(xué)方法，特別是計(jì)算機(jī)技術(shù)。一道實(shí)際問題的解決往往需要紛繁的計(jì)算，因此編程能力和熟悉數(shù)學(xué)知識便舉足輕重。4.編程實(shí)現(xiàn)其中，２、３兩步是關(guān)鍵。模型建立與解決得好與壞對能否成功解決該題起著決定性的作用。三、具體應(yīng)用1.對于同一個現(xiàn)實(shí)問題，可能可以建立不同的數(shù)學(xué)模型這種現(xiàn)象十分普遍，也就是平時所說的一題多解。既然如此，這里有必要討論一下數(shù)學(xué)模型的選擇問題，其實(shí)也就是評判一個模型好

5、壞標(biāo)準(zhǔn)的問題。一個好的數(shù)學(xué)模型不僅要能夠準(zhǔn)確地反映出現(xiàn)實(shí)模型（可靠性），所建立的模型還必須能夠被有效地解決（可解性）。這里“有效”指的是解決它的算法所需的空間與時間都在可以承受的范圍之內(nèi)。通常在解一些要求最優(yōu)解或要求準(zhǔn)確計(jì)數(shù)的一類具有唯一正確解的試題時，我們一般在保證可靠性的前提下，盡量提高模型的可解性。若幾個模型都具有可靠性，則當(dāng)然可解性越強(qiáng)的模型越好。例如第六屆分區(qū)聯(lián)賽高中組第四題【方格取數(shù)】就可以建立多種數(shù)學(xué)模型，各個模型的在可靠性與可解性方面各有千秋，請看下面的分析。【問題描述】設(shè)有N＊N的方格圖（N≤8），我們將其中的某些方格中填入正整數(shù)，而其他的方格中則放入數(shù)字0

6、。如下圖所示（見樣例）：向右A1234567810000000020013006003000070004000140000向下502100040060015000007014000000800000000B某人從圖的左上角的A點(diǎn)出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的B點(diǎn)。在走過的路上，他可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字0）。此人從A點(diǎn)到B點(diǎn)共走兩次，試找出2條這樣的路徑，使得取得的數(shù)之和為最大。【輸入】輸入的第一行為一個整數(shù)N（表示N＊N的方格圖），接下來的每行有三個整數(shù)，前兩個表示位置，第三個數(shù)為該位置上所放的數(shù)。一行單獨(dú)的0表示輸入結(jié)束。【輸出】只

7、需輸出一個整數(shù)，表示2條路徑上取得的最大的和。【樣例】82313152663574414522156463157214000結(jié)果67【問題分析】本題是從1997年國際信息學(xué)奧林匹克的障礙物探測器一題簡化而來，如果人只能從A點(diǎn)到B點(diǎn)走一次，則可以用動態(tài)規(guī)劃算法求出從A點(diǎn)到B點(diǎn)的最優(yōu)路徑。具體的算法描述如下：從A點(diǎn)開始，向右和向下遞推，依次求出從A點(diǎn)出發(fā)到達(dá)當(dāng)前位置（i，j）所能取得的最大的數(shù)之和，存放在sum數(shù)組中，原始數(shù)據(jù)經(jīng)過轉(zhuǎn)換后用二維數(shù)組data存儲，為方便處理，對數(shù)組sum和data加進(jìn)零行與零列