網(wǎng)上找的一些10月浙江3模擬策略

1、模擬法模擬的形式隨機(jī)模擬：題目給定或者隱含某一概率。設(shè)計(jì)者利用隨機(jī)函數(shù)和取整函數(shù)設(shè)定某一范圍的隨機(jī)值，將符合概率的隨機(jī)值作為參數(shù)。然后根據(jù)這一模擬的數(shù)學(xué)模型展開算法設(shè)計(jì)。由于解題過程借助了計(jì)算機(jī)的偽隨機(jī)數(shù)發(fā)生數(shù)，其隨機(jī)的意義要比實(shí)際問題中真實(shí)的隨機(jī)變量稍差一些，因此模擬效果有不確定的因素；過程模擬：題目不給出概率，要求編程者按照題意設(shè)計(jì)數(shù)學(xué)模型的各種參數(shù)，觀察變更這些參數(shù)所引起過程狀態(tài)的變化，由此展開算法設(shè)計(jì)。模擬效果完全取決于過程模擬的真實(shí)性和算法的正確性，不含任何不確定因素。由于過程模擬的結(jié)果無二義性，因此競(jìng)賽大都采用過程模擬。 模擬法的類型直敘式模擬篩選法模擬構(gòu)造法模擬直敘式模擬 直敘式

2、模擬即按照試題要求展開模擬過程。編程者要忠實(shí)于原題，認(rèn)真審題，千萬不要疏漏任何條件，精心設(shè)計(jì)方便模擬的數(shù)據(jù)結(jié)構(gòu)。“直敘式模擬”的難度取決于模擬對(duì)象所包含的動(dòng)態(tài)變化的屬性有多少，動(dòng)態(tài)屬性愈多，則難度愈大。 花生采摘【問題描述】魯賓遜先生有一只寵物猴，名叫多多。這天，他們兩個(gè)正沿著鄉(xiāng)間小路散步，突然發(fā)現(xiàn)路邊的告示牌上貼著一張小小的紙條：“歡迎免費(fèi)品嘗我種的花生！熊字”。魯賓遜先生和多多都很開心，因?yàn)榛ㄉ撬麄兊淖類?。在告示牌背后，路邊真的有一塊花生田，花生植株整齊地排列成矩形網(wǎng)格（如圖1）。有經(jīng)驗(yàn)的多多一眼就能看出，每棵花生植株下的花生有多少。為了訓(xùn)練多多的算術(shù)，魯賓遜先生說：“你先找出花生最多

3、的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時(shí)間內(nèi)回到路邊?！蔽覀兗俣ǘ喽嘣诿總€(gè)單位時(shí)間內(nèi)，可以做下列四件事情中的一件：1)從路邊跳到最靠近路邊（即第一行）的某棵花生植株；2)從一棵植株跳到前后左右與之相鄰的另一棵植株；3)采摘一棵植株下的花生；4)從最靠近路邊（即第一行）的某棵花生植株跳回路邊。現(xiàn)在給定一塊花生田的大小和花生的分布，請(qǐng)問在限定時(shí)間內(nèi)，多多最多可以采到多少個(gè)花生？注意可能只有部分植株下面長(zhǎng)有花生，假設(shè)這些植株下的花生個(gè)數(shù)各不相同。例如在圖2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5,

4、 4)的植株下長(zhǎng)有花生，個(gè)數(shù)分別為13, 7, 15, 9。沿著圖示的路線，多多在21個(gè)單位時(shí)間內(nèi)，最多可以采到37個(gè)花生。【輸入文件】輸入文件peanuts.in的第一行包括三個(gè)整數(shù)，M, N和K，用空格隔開；表示花生田的大小為M * N（1M, N20），多多采花生的限定時(shí)間為K（0K1000）個(gè)單位時(shí)間。接下來的M行，每行包括N個(gè)非負(fù)整數(shù)，也用空格隔開；第i + 1行的第j個(gè)整數(shù)Pij（0Pij 500）表示花生田里植株(i, j)下花生的數(shù)目，0表示該植株下沒有花生?！据敵鑫募枯敵鑫募eanuts.out包括一行，這一行只包含一個(gè)整數(shù)，即在限定時(shí)間內(nèi)，多多最多可以采到花生的個(gè)數(shù)。每

5、次在二維數(shù)組中找到當(dāng)前最大值的位置 若最大值為零，則由當(dāng)前位置直接返回路邊； 否則判斷走至最大值位置后再返回路邊的時(shí)間是否來得及：如果來得及，則移動(dòng)到最大值位置，把該位置的花生數(shù)置為零，累加已用時(shí)間；如果來不及，就由當(dāng)前位置直接返回路邊。 設(shè)var t,m,n,k,max,i,j,max1i,max1j,maxi,maxj,total:integer; 多多目前的行程為t；花生田的規(guī)模為m*n；多多采花生的限定時(shí)間為k ；最近采集花生的位置為（max1i,max1j），準(zhǔn)備采集花生的位置為（maxi，maxj），顯然兩個(gè)采集點(diǎn)的距離為 ；多多在限定時(shí)間內(nèi)可采集到的最多花生數(shù)為total p:a

6、rray1.20,1.20of integer; 花生田。其中pi，j為花生田里植株(i, j)下花生的數(shù)目由于多多在相鄰元素間移動(dòng)一步的時(shí)間為一個(gè)單位，因此除去多多從路邊往返數(shù)組第一行的2個(gè)單位時(shí)間，則多多在數(shù)組內(nèi)采集花生的時(shí)間不允許超過k-2（k=k-2）個(gè)時(shí)間單位。我們首先計(jì)算花生數(shù)最多的位置（max1i，max1j）和該位置的花生數(shù)max，將多多的行程t初始化為max1i。顯然，如果花生田里有花生(max0)且采集了花生最多的植株后可返回路邊（t+max1i-1k），則采集（max1i，max1j）位置的花生（pmax1i,max1j0；totaltotal+max）。然后計(jì)算下一個(gè)花

7、生數(shù)最多的位置（maxi，maxj），將兩個(gè)采集點(diǎn)的距離計(jì)入t(tt+ )，并將（maxi，maxj）設(shè)為下一個(gè)采集目標(biāo)（max1imaxi;max1jmaxj）。重復(fù)上述計(jì)算過程，直至花生田里無花生(max=0)或者采集（max1i，max1j）位置的花生后無法返回路邊（t+max1i-1k）為止。由此得出算法：readln(m,n,k);讀花生田的規(guī)模和多多采花生的限定時(shí)間k:=k-2; 計(jì)算多多在數(shù)組內(nèi)采集花生的最多時(shí)間max:=0;讀花生田的信息。計(jì)算花生數(shù)最多的位置（max1i，max1j）和該位置的花生數(shù)maxfor i:=1 to m do for j:=1 to n do be

8、gin read(pi,j); if pi,jmax then begin max:=pi,j;max1i:=i;max1j:=j；end;then end;fort:=max1i;total:=0; 多多的行程和采集的花生數(shù)初始化while (t+max1i-10) do若在限定時(shí)間內(nèi)回到路邊且找到花生最多的植株，則采摘它的花生，并累計(jì)采摘的花生總數(shù) begin pmax1i,max1j:=0;total:=total+max; max:=0;計(jì)算當(dāng)前花生數(shù)最多的位置（maxi，maxj）和該位置的花生數(shù)max for i:=1 to m dofor j:=1 to n doif pi,jm

9、ax then begin max:=pi,j;maxi:=i;maxj:=j；end;then t:=t+1+abs(max1i-maxi)+abs(max1j-maxj);累計(jì)行程 max1i:=maxi;max1j:=maxj；從該位置出發(fā)，繼續(xù)采摘花生end;while writeln(total);輸出限定時(shí)間內(nèi)多多采到花生數(shù)的最大值 時(shí)間復(fù)雜度為O (k*n2) 貪心算法 先將花生植株按花生數(shù)遞減的順序排列成一維數(shù)組，數(shù)組元素記錄下植株的花生數(shù)和位置。按照數(shù)組順序，找出距離之和不超過k-2、且最接近k-2的前若干個(gè)元素，將這些元素記錄的花生數(shù)累加起來，便構(gòu)成了問題的解。算法的時(shí)間復(fù)

10、雜度為O (n*log n +k)。昂貴的聘禮 年輕的探險(xiǎn)家來到了一個(gè)印第安部落里。在那里他和酋長(zhǎng)的女兒相愛了，于是便向酋長(zhǎng)去求親。酋長(zhǎng)要他用10000個(gè)金幣作為聘禮才答應(yīng)把女兒嫁給他。探險(xiǎn)家拿不出這么多金幣，便請(qǐng)求酋長(zhǎng)降低要求。酋長(zhǎng)說：“嗯，如果你能夠替我弄到大祭司的皮襖，我可以只要8000金幣。如果你能夠弄來他的水晶球，那么只要5000金幣就行了。”探險(xiǎn)家就跑到大祭司那里，向他要求皮襖或水晶球，大祭司要他用金幣來換，或者替他弄來其他的東西，他可以降低價(jià)格。探險(xiǎn)家于是又跑到其他地方，其他人也提出了類似的要求，或者直接用金幣換，或者找到其他東西就可以降低價(jià)格。不過探險(xiǎn)家沒必要用多樣?xùn)|西去換一樣

11、東西，因?yàn)椴粫?huì)得到更低的價(jià)格。探險(xiǎn)家現(xiàn)在很需要你的幫忙，讓他用最少的金幣娶到自己的心上人。另外他要告訴你的是，在這個(gè)部落里，等級(jí)觀念十分森嚴(yán)。地位差距超過一定限制的兩個(gè)人之間不會(huì)進(jìn)行任何形式的直接接觸，包括交易。他是一個(gè)外來人，所以可以不受這些限制。但是如果他和某個(gè)地位較低的人進(jìn)行了交易，地位較高的的人不會(huì)再和他交易，他們認(rèn)為這樣等于是間接接觸，反過來也一樣。因此你需要在考慮所有的情況以后給他提供一個(gè)最好的方案。 為了方便起見，我們把所有的物品從1開始進(jìn)行編號(hào)，酋長(zhǎng)的允諾也看作一個(gè)物品，并且編號(hào)總是1。每個(gè)物品都有對(duì)應(yīng)的價(jià)格P，主人的地位等級(jí)L，以及一系列的替代品Ti和該替代品所對(duì)應(yīng)的“優(yōu)惠”

12、Vi。如果兩人地位等級(jí)差距超過了M，就不能“間接交易”。你必須根據(jù)這些數(shù)據(jù)來計(jì)算出探險(xiǎn)家最少需要多少金幣才能娶到酋長(zhǎng)的女兒。輸入文件 M，N（1=N=100），依次表示地位等級(jí)差距限制和物品的總數(shù)。 按照編號(hào)從小到大依次給出了N個(gè)物品的描述。每個(gè)物品的描述開頭是三個(gè)非負(fù)整數(shù)P、L、X（XN），依次表示該物品的價(jià)格、主人的地位等級(jí)和替代品總數(shù)。接下來X行每行包括兩個(gè)整數(shù)T和V，分別表示替代品的編號(hào)和“優(yōu)惠價(jià)格”。輸出文件 最少需要的金幣數(shù)。數(shù)據(jù)結(jié)構(gòu)const maxn=100;物品數(shù)上限type ny=nz;物品的指針變量 nz=array1.maxn,1.2 of longint;替代品序列，

13、包括每一個(gè)替代品的編號(hào)和“優(yōu)惠價(jià)格” nx=record p,x,l:longint; 物品的價(jià)格、替代品總數(shù)和主人的地位等級(jí) list:ny; 替代品序列 end;var map:array1.maxn of nx;物品序列 can:array1.maxn of boolean;記錄與當(dāng)前客戶的等級(jí)差距在限制范圍內(nèi)的客戶 p,l,x,i,j,m,n，l1:longint;輸入信息readln(m,n);輸入地位等級(jí)差距限制和物品總數(shù)readln(map1.p,map1.l,map1.x);讀入物品1的價(jià)格、主人的地位等級(jí)和替代品總數(shù)new(map1.list);讀入物品1的每個(gè)替代品的編號(hào)和

14、“優(yōu)惠價(jià)格”for i:=1 to map1.x do readln(map1.listi,1,map1.listi,2);for i:=2 to n do讀入物品2物品n的信息 with mapi do begin readln(p,l,x);new(list); for j:=1 to x do readln(listj,1,listj,2); end;計(jì)算最少需要的金幣數(shù)遞推每一個(gè)客戶h(1hn)11尋找每一個(gè)與客戶h的等級(jí)差距在限制范圍內(nèi)的客戶i搜索客戶i的每一個(gè)可與客戶h交易的替代品j,若替代后花錢更少，則記下 pricei=minpricej+物品j的優(yōu)惠價(jià)，物品i的單價(jià)12若當(dāng)前

15、方案最佳（price1=0) and (mapi.l-maph.l=m) then cani:=true; for i:=1 to n do pricei:=mapi.p;初始時(shí)直接購(gòu)買repeat ok:=true; for i:=1 to n do枚舉每一個(gè)與客戶h的等級(jí)差距在限制范圍內(nèi)的客戶 if cani then for j:=1 to mapi.x do begin枚舉物品i的每一個(gè)替代品，記下其編號(hào)和“優(yōu)惠價(jià)格” now:=mapi.listj,1; more:=mapi.listj,2; if （cannow）and(pricenow+morepricei) 若第j個(gè)替代品可與

16、客戶h交易且間接交易后花錢更少，則采取該交易方案 then begin ok:=false;pricei:=pricenow+more;end; end;foruntil ok;if price1min then min:=price1;若目前方案的花錢最少，則記下end;for writeln(min);輸出最少需要的金幣數(shù)end;DAM語言 有個(gè)機(jī)器執(zhí)行一種DASM語言。該機(jī)器有一個(gè)棧，初始時(shí)棧里只有一個(gè)元素x，隨著DAM語言程序的執(zhí)行，棧里的元素會(huì)發(fā)生變化。DAM語言有四種指令：D指令：把棧頂元素復(fù)制一次加到棧頂A指令：把棧頂元素取出，加到新的棧頂元素中。M指令：把棧頂元素取出，乘到新的

17、棧頂元素中。如果執(zhí)行A或M指令的時(shí)候棧內(nèi)只有一個(gè)元素，則機(jī)器會(huì)發(fā)出錯(cuò)誤信息。如果程序無誤，那么執(zhí)行完畢以后，棧頂元素應(yīng)該是x的多項(xiàng)式，例如，程序DADDMA的執(zhí)行情況為（棧內(nèi)元素按照從底到頂?shù)捻樞驈淖笾劣遗帕?，用逗?hào)隔開）：x x， x 2x 2x， 2x 2x， 2x， 2x 2x， 4x2 4x2+2x給出一段DAM程序，求出執(zhí)行完畢后棧頂元素。輸入輸入僅一行，包含一個(gè)不空的字符串s，長(zhǎng)度不超過12，代表一段DAM程序。輸入程序保證合法且不會(huì)導(dǎo)致錯(cuò)誤。輸出僅輸出一行，即棧頂多項(xiàng)式。須按照習(xí)慣寫法降冪輸出，即：等于1的系數(shù)不要打印，系數(shù)為0的項(xiàng)不打印，第一項(xiàng)不打印正號(hào)。一次方不打印1。 模擬

18、需要注意的問題：多項(xiàng)式的表示方式。有的選手或許會(huì)覺得：本題沒有說明次數(shù)的上限，因此最好用鏈表做。其實(shí)完全沒有必要。由于指令不超過12條，而D指令和A，M指令總數(shù)應(yīng)該相等，因此最多有6條M指令，因此次數(shù)上限為26=64。我們可以用數(shù)組來表示多項(xiàng)式，又方便又不會(huì)導(dǎo)致時(shí)間和空間上的問題。 本題也沒有說明系數(shù)的最大值。稍微細(xì)心的選手發(fā)現(xiàn)：它最大可能為232，超過長(zhǎng)整數(shù)的范圍，因此需要采用extended類型，當(dāng)然，也不存在非得用高精度的必要。 $n+var degree ： array1 . 20 of integer； 存儲(chǔ)系數(shù)個(gè)數(shù)的棧 co ： array1 . 20， 0 . 64 of ext

19、ended；存儲(chǔ)多項(xiàng)式的棧 tmp ： array0 . 64 of extended；系數(shù)序列 I， j， d， a， b， top ： integer； 棧頂指針為top s ： string； Dam程序 first ： boolean；begin top 1； 棧頂指針初始化 fillchar(co， sizeof(co)， 0)； 存儲(chǔ)多項(xiàng)式的棧清零 degree1 1；初始時(shí)棧里只有一個(gè)元素x co1， 1 1； read(s)；輸入Dam程序 for I 1 to length(s) do依次執(zhí)行Dam程序中的每一條命令case sI ofD： begin 把棧頂元素復(fù)制一次加到

20、棧頂 inc(top)；degreetop degreetop 1； for j 0 to degreetop do cotop， j cotop 1， j； end； DA： begin 把棧頂元素取出，加到新的棧頂元素中 dec(top)； if degreetop degreetop + 1 then degreetop degreetop + 1； for j 0 to degreetop do cotop， j cotop， j + cotop + 1， j； end； AM：begin 把棧頂元素取出，乘到新的棧頂元素中 dec(top)；fillchar(tmp，sizeof(t

21、mp)，0)；ddegreetop+degreetop +1； for a0 to degreetop do for b 0 to degreetop + 1 do tmpa + btmpa+b+cotop， a*cotop+1， b degreetop d； for j 0 to d do cotop， j tmpj； end； Mend；case first true；按照降冪的順序輸出棧頂多項(xiàng)式 for I degreetop downto 1 do if cotop， I 0 then begin if first then first false else write(+)； if

22、abs(cotop， I 1.0) 1e-6 then write(cotop， I ： 0 ： 0)； write(x)； if I 1 then write(， I)； end；then writeln；end.main跳遠(yuǎn)在水平面上整齊的放著n個(gè)正三角形，相鄰兩個(gè)三角形的底邊之間無空隙，如左圖所示。一個(gè)小孩子想站在某個(gè)三角形i的頂端，跳到三角形j的頂端上(ij)。他總是朝著斜向45度的方向起跳，且初始水平速度v不超過一個(gè)給定值v0。在跳躍過程中，由于受到重力作用（忽略空氣阻力），小孩子將沿著拋物線行進(jìn)，水平運(yùn)動(dòng)方程為x = x0 + vt，豎直運(yùn)動(dòng)方程為y = y0 + vt 0.5gt

23、2，運(yùn)動(dòng)軌跡是一條上凸的拋物線。取g=10.0，(x0， y0)是起跳點(diǎn)坐標(biāo)。請(qǐng)編程求出他從每個(gè)位置起跳能到達(dá)的最遠(yuǎn)三角形的編號(hào)。注意：跳躍過程中不許碰到非起點(diǎn)和終點(diǎn)的其他三角形。輸入第一行為兩個(gè)正整數(shù)n，v0(3n10， 1v0100)，表示三角形的個(gè)數(shù)和最大水平初速度。第二行有n個(gè)正整數(shù)li(1li20)，表示從左到右各個(gè)三角形的邊長(zhǎng)。輸出輸出僅一行，包括n-1個(gè)數(shù)，表示從三角形1，2，3n-1的頂點(diǎn)出發(fā)能到達(dá)的最右的三角形編號(hào)。如果從某三角形出發(fā)無法達(dá)到任何三角形，相應(yīng)的數(shù)為0。狀態(tài)：起跳點(diǎn)i和i點(diǎn)后的點(diǎn)j。每個(gè)狀態(tài)元素的取值范圍：1in-1，i+1jn 約束條件的分析：判斷小孩能否從i

24、點(diǎn)跳到j(luò)點(diǎn)的方法如下：設(shè)起點(diǎn)和終點(diǎn)間的水平距離為l、垂直距離為h。則由物理知識(shí)（已在題目中給出）有：t = l / vh = vt 5t2 = l 5*(l/v)2 。因此，v = sqrt(5*l*l/ (l - h)。當(dāng)然，這個(gè)v不一定符合要求，它需要滿足兩個(gè)條件。 它不能大于極限速度v0，即必須有v v0 跳躍過程中不得碰到其他三角形。 如何判斷頂點(diǎn)k是否在拋物線下呢？我們可以算出到達(dá)時(shí)間t0 = dx / v（其中dx為起點(diǎn)到頂點(diǎn)k的水平坐標(biāo)增量），然后算出該時(shí)刻的豎直坐標(biāo)增量vt0 0.5t02。如果此增量大于起點(diǎn)到頂點(diǎn)k的豎直坐標(biāo)增量，則拋物線在上方。只有起點(diǎn)和終點(diǎn)之間任何一個(gè)三角

25、形的頂點(diǎn)不在拋物線下方，則跳遠(yuǎn)不能完成。我們?cè)诿杜e過程中不斷將小孩所能跳到的點(diǎn)j調(diào)整為best。 枚舉結(jié)束后，best即為試題要求的最遠(yuǎn)點(diǎn)。var len ： array1 . 20 of longint； x， y ： array1 . 20 of double；三角形頂端頂點(diǎn)的坐標(biāo)序列 l， h， t， v， v0 ： double； ok ： boolean；跳躍成功標(biāo)志 i， j， k， n， best ： integer；begin read(n， v0)；輸入三角形的個(gè)數(shù)和最大水平初速度 for i 1 to n do read(leni)；入從左到右各個(gè)三角形的邊長(zhǎng) x1 len

26、1 / 2；計(jì)算每一個(gè)三角形頂端頂點(diǎn)的坐標(biāo) y1 len1 * sqrt(3) / 2； for i 2 to n do begin xi xi - 1 + leni - 1 / 2 + leni / 2； yi leni * sqrt(3) / 2； end；forfor i 1 to n - 1 do依次計(jì)算每一個(gè)三角形所能到達(dá)的最遠(yuǎn)點(diǎn) begin best 0；從三角形i出發(fā)能到達(dá)的最右的三角形編號(hào)初始化 for j i + 1 to n do依次枚舉右方的每一個(gè)三角形 begin l xj - xi；計(jì)算三角形i與三角形j的兩個(gè)頂端頂點(diǎn)的水平距離和垂直距離 h yj - yi； if

27、l v0 then break；若大于極限速度v0，則無法從三角形i起跳 ok true； for k i + 1 to j - 1 do判斷跳躍過程中是否碰到其他三角形 begin t (xk - xi) / v；計(jì)算到達(dá)三角形k的時(shí)間 if (v * t - 5 * t * t) - (yk - yi) 1e-6 then begin如果該時(shí)刻的豎直坐標(biāo)增量大于起點(diǎn)到頂點(diǎn)k的豎直坐標(biāo)增量，則拋物線在上方 ok false； break； end；then end；forif ok then best j 若跳遠(yuǎn)成功，則三角形j為目前三角形i所能到達(dá)的最遠(yuǎn)點(diǎn)，否則跳遠(yuǎn)不能完成 else br

28、eak； end；for write(best， )；輸出從三角形i的頂點(diǎn)出發(fā)所能到達(dá)的最右的三角形編號(hào)） end；for writeln；end.main篩選法模擬 模擬過程中可能產(chǎn)生的所有解組成一個(gè)篩。篩選法模擬即先從題意中找出約束條件，然后將篩中的每一個(gè)可能解放到約束條件的過濾器上，一次一次地將不符合條件的解過濾掉，最后沉淀在篩中的即為問題的解?！昂Y選法模擬”的結(jié)構(gòu)和思路簡(jiǎn)明、清晰，但帶有盲目性，因此時(shí)間效率并不一定令人滿意。“篩選法模擬”的關(guān)鍵是找準(zhǔn)約束條件，任何錯(cuò)誤和疏漏都會(huì)導(dǎo)致模擬失敗。 蒙特卡洛法 計(jì)算定積分其中ab，0f(x)d， 輸入：a b d a0a1ak(表示f(x)=

29、ak*xk+a1*x+a0) 產(chǎn)生n(足夠大)個(gè)均勻分布在長(zhǎng)方形a b c d上的隨機(jī)數(shù)點(diǎn)(xi，yi)。其中 xi均勻分布在區(qū)間a，b上的隨機(jī)數(shù)，即xi=a+(b-a)*random(1)； yi均勻分布在區(qū)間0，d上的隨機(jī)數(shù)，即yi=d*random(1)； n個(gè)隨機(jī)數(shù)點(diǎn)組成一個(gè)篩。約束條件的過濾器是某點(diǎn)(xi，yi)是否落在曲邊梯形a e f b外。如果是（yif(xi)），則該點(diǎn)從篩中過濾掉。 最后有m個(gè)隨機(jī)數(shù)點(diǎn)留在篩中（這些隨機(jī)數(shù)點(diǎn)落在曲邊梯形a e f b內(nèi)）。曲邊梯形a e f b的面積應(yīng)該為m和n的比值乘以長(zhǎng)方形a b c d的面積 function f(x)：real；計(jì)算f

30、(x) begin f(x)akxk+ak-1kk-1+a1x+a0； end；f function amoncar (a， b， d， n)：real；計(jì)算 begin randomize； m0； for i1 to n do begin xa+(b-a)*random(1)；產(chǎn)生ki yd*random(1)；產(chǎn)生yi if yf(x) then mm+1；若(xi，yI)落入曲邊梯形內(nèi)，則累計(jì)其點(diǎn)數(shù) end；for amoncarm/n*(b-a)*d；返回曲邊梯形面積 end；amoncar 在主程序中，輸入隨機(jī)點(diǎn)的個(gè)數(shù)n和a，b，d，然后通過調(diào)用函數(shù)amoncar (a，b，d，n

31、)計(jì)算和輸出定積分的值。注意，n愈大，定積分的值愈精確，但速度愈慢。 self-number對(duì)任意一個(gè)正整數(shù)n，定義d(n)為n加上其每一位上的數(shù)字，比如d(75) = 75 + 7 + 5 = 87。并且稱n是d(n)的一個(gè)generator。一個(gè)正整數(shù)，如果沒有任何generator，就說這個(gè)數(shù)是一個(gè)self-number。給出一列數(shù)s1，s2，sK，問范圍1, N內(nèi)第s1，s2，sK大的self-number分別是什么。輸入： n k(1 N 107,1 K 5000) s1，s2，sK輸出： 范圍1, N內(nèi)第s1，s2，sK大的self-number用篩數(shù)方法產(chǎn)生1, N中的所有sel

32、f-number 在一張一維的布爾表中，從小到大將每個(gè)數(shù)n的d(n)都標(biāo)記為不可能是self-number，那么未被標(biāo)記的一定就是self-number了。 布爾表的容量：因?yàn)閐(n) n并不會(huì)很大：最大也不過9*lgn=81。計(jì)算d(n)的時(shí)間復(fù)雜度原時(shí)間復(fù)雜度為O(NlgN)：因?yàn)槊看斡?jì)算d(n)時(shí)侯分離其每一位的時(shí)間復(fù)雜度是O(lgN)。本題中N高達(dá)107，因此這個(gè)O(lgN)的因子不可以忽略。優(yōu)化首先預(yù)處理，開一個(gè)sumi數(shù)組，記錄i的每一位之和，但是這里i的范圍不用太大，只要在O(sqrt(n)=104就可以了。這樣計(jì)算d(n)的時(shí)侯，就可以將n的各位和分成低4位和高3位來計(jì)算，而每

33、次計(jì)算不過是調(diào)用sumi，這樣計(jì)算d(n)的時(shí)間復(fù)雜度就降到了O(1)。綜上，本題的時(shí)間復(fù)雜度就是O(sqrt(n)lgN + N + Mlog2M)，其中Mlog2M是在輸出的時(shí)侯需要對(duì)si進(jìn)行排序。設(shè)篩data，其中datai 將數(shù)i的d(i)標(biāo)記為不可能是self-number。篩長(zhǎng)為1000。self-number序列為request，其中request i. request 為si，request i. number為si的輸入順序，request i. answer為順序?yàn)閟i的self-number數(shù)初始化read(N , K); for i := 1 to K do輸入s1，s

34、2，sK ，記下輸入順序 begin read(requesti.request); requesti.number := i; end;qk_sort(1 , K)；按照requesti.request (si)遞增順序排列request計(jì)算sub0sub10000，其中subi為整數(shù)i的各位數(shù)的和； fillchar(data , sizeof(data) , 0);初始時(shí)篩滿，即所有數(shù)可能是self-number數(shù) now := 1; total := 0; p := 1; for i := 1 to N do順序搜索1, N內(nèi)第s1，s2，sK大的self-number begin i

35、f not datanow then若now在篩中 begin inc(total);累計(jì)self-number的個(gè)數(shù) while (p Limit do dec(tmp , Limit);將di限制在1000范圍內(nèi) datatmp := true; datanow := false; 在data篩中保留第now個(gè)元素，去掉第di個(gè)元素 if now = Limit循環(huán)右移data篩的指針now then now := 1 else inc(now); end; 輸出self-numberfor i := 1 to K do outarrrequesti.number := requesti.

36、answer;按照輸入要求記下各個(gè)self-number數(shù)輸出1.n中self-number的個(gè)數(shù) total輸出outarr1 outarrk；構(gòu)造法模擬 構(gòu)造法模擬需要完整精確地構(gòu)造出反映問題本質(zhì)的數(shù)學(xué)模型，根據(jù)該模型設(shè)計(jì)狀態(tài)變化的參數(shù)，計(jì)算模擬結(jié)果。由于數(shù)學(xué)模型建立了客觀事物間準(zhǔn)確的運(yùn)算關(guān)系，因此其效率一般比較高?！皹?gòu)造法模擬”的關(guān)鍵是找到數(shù)學(xué)模型。問題是，能產(chǎn)生正確結(jié)果的數(shù)學(xué)模型并不是唯一的，從不同的思維角度看問題，可以得出不同的數(shù)學(xué)模型，而模擬效率和編程復(fù)雜度往往因數(shù)學(xué)模型而異。即便有數(shù)學(xué)模型，但解該模型的準(zhǔn)確方法是否有現(xiàn)成算法、編程復(fù)雜度如何，這些都是我們要考慮的問題?；瘜W(xué)試驗(yàn)安排

37、 阿扁是一位出色的化學(xué)研究員。近日，他正致力于研制一種化學(xué)藥物，用以糾正他糟糕的嗓音。阿扁給他這次研究起的代號(hào)是”acm”（arbains chemical magic，“阿扁的化學(xué)魔術(shù)”)。 經(jīng)過兩個(gè)星期的尋找，阿扁已經(jīng)采集了若干種化學(xué)原料?，F(xiàn)在，他需要對(duì)每種原料進(jìn)行精密的分析，以確定有效成分的含量。每種原料的分析都必須依次經(jīng)過兩個(gè)步驟：首先讓原料接受一定時(shí)間一定量的粒子轟擊（稱放射試驗(yàn)）；然后在156.0973下與濃硫酸共熱（稱加熱試驗(yàn)），兩個(gè)試驗(yàn)都必須在特制的精密昂貴的儀器內(nèi)進(jìn)行。 現(xiàn)在的問題是，由于經(jīng)費(fèi)的問題，阿扁的實(shí)驗(yàn)室里只有一臺(tái)做放射試驗(yàn)的儀器及一臺(tái)做加熱試驗(yàn)的儀器。換句話說，同一

38、時(shí)間內(nèi)最多只能做一個(gè)放射試驗(yàn)和一個(gè)加熱試驗(yàn)。而各種原料需做試驗(yàn)的時(shí)間是不盡相同的（幸而關(guān)于這些時(shí)間的數(shù)據(jù)阿扁已經(jīng)做了做精確的預(yù)算）。現(xiàn)在請(qǐng)你預(yù)計(jì)一下阿扁能結(jié)束試驗(yàn)的最早時(shí)間。輸入 ： 第一行為原料的數(shù)量n（整數(shù)，0=n=1000）。以下n行每行各兩整數(shù)ai，bi，表示第i種原料做放射試驗(yàn)的時(shí)間為ai，做加熱試驗(yàn)的時(shí)間為bi。（0ai，bi100且aibi）輸出 ：只有一行，為結(jié)束試驗(yàn)的最早時(shí)間。 本題“分析試驗(yàn)”的特殊性在于：每份原料必須先進(jìn)行放射試驗(yàn)，再進(jìn)行加熱試驗(yàn)；一次只能有一份原料在某一臺(tái)儀器上做試驗(yàn)。整個(gè)試驗(yàn)的進(jìn)行非常類似于計(jì)算機(jī)的“并行處理”。易知，由于放射實(shí)驗(yàn)所受到的限制少，沒有“

39、空閑”的時(shí)間，所以放射試驗(yàn)的總時(shí)間是確定的（=ai）。問題就在于加熱試驗(yàn)對(duì)放射試驗(yàn)的“等待”。從最簡(jiǎn)單的情況開始 首先，當(dāng)只有一份原料時(shí)，無需安排，先“放射”再“加熱”就可以了。當(dāng)有兩份原料時(shí)，如Sample 1，情況也很簡(jiǎn)單，無非是1-2和2-1的區(qū)別。 放射試驗(yàn)a1a2時(shí)間12345678910加熱試驗(yàn)b1b2放射試驗(yàn)a2a1時(shí)間123456789加熱試驗(yàn)b2b1結(jié)論 考慮兩份原料i、j，當(dāng)按照先i后j的順序做試驗(yàn)時(shí)，總耗時(shí) 進(jìn)一步，我們?cè)O(shè) (先i后j順序中的重合部分)，其含義為在兩臺(tái)儀器上同時(shí)試驗(yàn)的時(shí)間。那么再分析原料數(shù)增多的情況確定原料兩兩之間的較優(yōu)順序 應(yīng)把p排在試驗(yàn)最前面 應(yīng)把p排

40、在最后試驗(yàn) const TaskLim=1000；最多原料數(shù)var task:array1.2，1.TaskLimof byte；每種原料做放射、加熱試驗(yàn)的時(shí)間 odr:array1.TaskLimof integer；最優(yōu)化順序 n，totTime:longint；procedure init；讀入數(shù)據(jù)var i，j，k:integer；begin readln(n)； 讀原料數(shù) for i1 to n do readln(task1，i，task2，i)；讀每種原料的放射試驗(yàn)時(shí)間和加熱試驗(yàn)時(shí)間end； init procedure Order； 安排試驗(yàn)順序var i，j，k， min，b

41、estj，bestk，當(dāng)前安排試驗(yàn)的費(fèi)時(shí)、原料和實(shí)驗(yàn)內(nèi)容 pfront，ptail:integer；頭、尾指針 tick:array1.TaskLimof 0.1；試驗(yàn)工序beginfillchar(tick，sizeof(tick)，0)；試驗(yàn)工序初始化pfront0；ptailn+1；頭尾指針初始化for i1 to n do 依次安排每個(gè)試驗(yàn) begin min30000；在未安排試驗(yàn)的原料中，尋找試驗(yàn)時(shí)間最短的原料bestj,試驗(yàn)內(nèi)容為k for j1 to n do if (tickj=0)then for k1 to 2 do if taskk，jtmi在tottime時(shí)刻開始做原

42、料j的加熱試驗(yàn) then inc(tottime，task2，j) else tottimetmi+task2，j；順序做原料j的放射試驗(yàn)和加熱試驗(yàn) end；forend； CalcTime begin init；輸入數(shù)據(jù) order；計(jì)算試驗(yàn)工序 calctime；計(jì)算總耗時(shí) writeln(tottime)；輸出總耗時(shí)End.main模擬策略舉例 在自然界和日常生活中，許多現(xiàn)象具有不確定的性質(zhì)，有些問題甚至很難建立數(shù)學(xué)模型，或者很難用計(jì)算機(jī)建立遞推、遞歸、枚舉、回溯法等算法。在這種情況下，一般采用模擬策略。所謂模擬策略就是模擬某個(gè)過程，通過改變數(shù)學(xué)模型的各種參數(shù)，進(jìn)而觀察變更這些參數(shù)所引起

43、過程狀態(tài)的變化，由此展開算法設(shè)計(jì)。 等價(jià)表達(dá)式【問題描述】明明進(jìn)了中學(xué)之后，學(xué)到了代數(shù)表達(dá)式。有一天，他碰到一個(gè)很麻煩的選擇題。這個(gè)題目的題干中首先給出了一個(gè)代數(shù)表達(dá)式，然后列出了若干選項(xiàng)，每個(gè)選項(xiàng)也是一個(gè)代數(shù)表達(dá)式，題目的要求是判斷選項(xiàng)中哪些代數(shù)表達(dá)式是和題干中的表達(dá)式等價(jià)的。 這個(gè)題目手算很麻煩，因?yàn)槊髅鲗?duì)計(jì)算機(jī)編程很感興趣，所以他想是不是可以用計(jì)算機(jī)來解決這個(gè)問題。假設(shè)你是明明，能完成這個(gè)任務(wù)嗎？這個(gè)選擇題中的每個(gè)表達(dá)式都滿足下面的性質(zhì)：1 表達(dá)式只可能包含一個(gè)變量a。2 表達(dá)式中出現(xiàn)的數(shù)都是正整數(shù)，而且都小于10000。3 表達(dá)式中可以包括四種運(yùn)算+（加），-（減），*（乘），（乘冪）

44、，以及小括號(hào)(，)。小括號(hào)的優(yōu)先級(jí)最高，其次是，然后是*，最后是+和-。+和-的優(yōu)先級(jí)是相同的。相同優(yōu)先級(jí)的運(yùn)算從左到右進(jìn)行。（注意：運(yùn)算符+，-，*，以及小括號(hào)(，)都是英文字符）4 冪指數(shù)只可能是1到10之間的正整數(shù)（包括1和10）。5 表達(dá)式內(nèi)部，頭部或者尾部都可能有一些多余的空格。下面是一些合理的表達(dá)式的例子：(a1) 2)3，a*a+a-a，(a+a)，9999+(a-a)*a，1 + (a -1)3，1109【輸入文件】輸入文件equal.in的第一行給出的是題干中的表達(dá)式。第二行是一個(gè)整數(shù)n（2 n 26），表示選項(xiàng)的個(gè)數(shù)。后面n行，每行包括一個(gè)選項(xiàng)中的表達(dá)式。這n個(gè)選項(xiàng)的標(biāo)號(hào)分

45、別是A，B，C，D 輸入中的表達(dá)式的長(zhǎng)度都不超過50個(gè)字符，而且保證選項(xiàng)中總有表達(dá)式和題干中的表達(dá)式是等價(jià)的?！据敵鑫募枯敵鑫募qual.out包括一行，這一行包括一系列選項(xiàng)的標(biāo)號(hào)，表示哪些選項(xiàng)是和題干中的表達(dá)式等價(jià)的。選項(xiàng)的標(biāo)號(hào)按照字母順序排列，而且之間沒有空格。問題的核心是如何判斷表達(dá)式等價(jià) 判斷表達(dá)式等價(jià)的方法一般有兩種：表達(dá)式化簡(jiǎn)后判斷表達(dá)式代值后判斷判斷等價(jià)的方法1：展開多項(xiàng)式后判斷 將所有的表達(dá)式全部轉(zhuǎn)化為最簡(jiǎn)形式，然后再計(jì)算。其一般過程:先將階乘化乘，再展開。計(jì)算同時(shí)合并同類項(xiàng)，并用數(shù)組記錄每一個(gè)表達(dá)式的最簡(jiǎn)形式。然后比較每一個(gè)表達(dá)式的數(shù)組與題干表達(dá)式的數(shù)組是否相同。若相同，

46、則說明該表達(dá)式與題干表達(dá)式是等價(jià)的。優(yōu)點(diǎn):準(zhǔn)確和嚴(yán)密缺點(diǎn):實(shí)現(xiàn)相當(dāng)麻煩，時(shí)間效率不高，尤其是在乘冪多、冪次大的情況下。 判斷等價(jià)的方法2：代值后判斷 將數(shù)值代入并計(jì)算。 誤判的可能:假如碰巧代入的值使兩個(gè)多項(xiàng)式值相等 避免的方法：多次代入不同數(shù)值、代入較大數(shù)值等等。雖然這個(gè)算法并不一定正確，但多次隨機(jī)代值后的出錯(cuò)概率已經(jīng)可以忽略不計(jì)了，而且實(shí)現(xiàn)又比較簡(jiǎn)單。取值的有效方法：取隨機(jī)函數(shù)生成的數(shù)列。這種方法比較有效，無規(guī)律。取偽隨機(jī)數(shù)列。這是一種比較便于人工控制的手段。取實(shí)數(shù)。優(yōu)點(diǎn):由于系數(shù)和次冪和常數(shù)皆為整數(shù)，因此小數(shù)部分便成為判斷的優(yōu)越條件。缺點(diǎn):由于計(jì)算中出現(xiàn)了次方運(yùn)算，所以可能溢出。避免整數(shù)

47、溢出的方法:在求值過程中采用取模運(yùn)算，并且多取幾個(gè)模。我們采取多代整數(shù)、多取模的方法判斷表達(dá)式等價(jià)。于是，如何計(jì)算表達(dá)式的值成了問題的關(guān)鍵表達(dá)式求值的方法1:棧操作 建立兩個(gè)棧，一個(gè)是存儲(chǔ)操作數(shù)的數(shù)棧，一個(gè)是存儲(chǔ)運(yùn)算符的符號(hào)棧。每一個(gè)符號(hào)定義一個(gè)優(yōu)先級(jí),優(yōu)先級(jí)高的運(yùn)算符先算。為了方便起見，我們定義特殊符號(hào)#的級(jí)別最低（賦-1），先將它置符號(hào)棧的棧底。然后依次讀入每個(gè)字符，如果是數(shù)字，則入數(shù)棧。如果是運(yùn)算符，則與符號(hào)棧的棧頂元素比較優(yōu)先級(jí)。如果相等，則出棧，讀下一字符；如果棧外大，則入棧；如果棧內(nèi)大，則符號(hào)棧的棧頂元素出棧，與數(shù)棧最頂2元素運(yùn)算，結(jié)果入數(shù)棧。這個(gè)符號(hào)繼續(xù)處理（再與棧頂比較）。直到

48、讀到最后符號(hào)#使棧底#出棧時(shí)，數(shù)棧頂即為表達(dá)式結(jié)果。 表達(dá)式求值的方法2:并查集操作 每次在尚未運(yùn)算的運(yùn)算符找出一個(gè)優(yōu)先級(jí)最高的符號(hào)，進(jìn)行相應(yīng)的運(yùn)算，直至僅剩一個(gè)數(shù)字時(shí)返回。這種方法符合自然思維和運(yùn)算規(guī)則，實(shí)現(xiàn)簡(jiǎn)單明了，不易出錯(cuò)。我們由左而右掃描表達(dá)式串st的每一個(gè)字符，存儲(chǔ)每一個(gè)運(yùn)算的信息。其中第i個(gè)運(yùn)算的運(yùn)算符存儲(chǔ)在ci，優(yōu)先級(jí)存儲(chǔ)在di（di= ），操作數(shù)存儲(chǔ)在ri（若第i個(gè)運(yùn)算的操作數(shù)為變量a，則ri=-1）1、數(shù)據(jù)結(jié)構(gòu) 我們將目前所有參與過運(yùn)算的操作數(shù)放在集合里，其中第p個(gè)操作數(shù)參與運(yùn)算后的結(jié)果記入第fp個(gè)操作數(shù)，即所有具有同一個(gè)f值的操作數(shù)組成一個(gè)集合，它們運(yùn)算后的結(jié)果記入第fp個(gè)

49、操作數(shù)。 如果ci為當(dāng)前的運(yùn)算符，則從fi和fi+1出發(fā)，順著f指針即可找到參與運(yùn)算的兩個(gè)操作數(shù)。const xn=3;代入的a的總數(shù) mn=2;模的總數(shù)var cm,rc,nn,n,i,j:longint;選項(xiàng)數(shù)為nn；運(yùn)算數(shù)為n st:string;表達(dá)式串 c:array 1.30 of char;ci為第i個(gè)運(yùn)算的運(yùn)算符 d:array 1.30 of longint; di為第i個(gè)運(yùn)算的優(yōu)先級(jí) r,u:array 1.30 of int64; ri為第i個(gè)運(yùn)算的操作數(shù)。若ri=-1，則第i個(gè)運(yùn)算的操作數(shù)為變量a a:array 1.xn,1.mn of int64;將第i個(gè)變量值和第

50、j個(gè)模代入題干后的值為ai,j x:array 1.xn of longint;a的第i個(gè)代入值為xi；模的第i個(gè)代入值為yi y:array 1.mn of longint; yes:boolean;當(dāng)前選項(xiàng)與題干等價(jià)的標(biāo)志 mv:int64;當(dāng)前選項(xiàng)的值2、記錄當(dāng)前選項(xiàng)的每一個(gè)運(yùn)算 procedure ff; var top,i,j,v:longint;i為讀字符串的指針；top為括號(hào)嵌套重?cái)?shù)，v為操作數(shù) begin top:=0;n:=1;i:=0;括號(hào)嵌套重?cái)?shù)、運(yùn)算順序數(shù)和字串指針初始化 fillchar(r,sizeof(r),0);操作數(shù)序列初始化 while ilength(st

51、) do begin inc(i);字串指針右移 case sti of分析第i個(gè)字符的類型 (:inc(top);若為左括號(hào)，括號(hào)嵌套重?cái)?shù)+1 ):dec(top); 若為右括號(hào)，括號(hào)嵌套重?cái)?shù)-1 0.9:begin若為數(shù)串，則計(jì)算對(duì)應(yīng)的數(shù)字，記入rn。字串指針指向數(shù)串后的第一個(gè)字符 j:=i;v:=0; while(j=0)and(stj=9)or(stj= )do begin if stj then v:=v*10+ord(stj)-48;inc(j) end; while rn:=v;i:=j-1 end; 0.9 a: rn:=-1; :continue; else begin cn

52、:=sti;記下運(yùn)算符 case sti of記下優(yōu)先級(jí) +,-:dn:=top*3+1; *:dn:=top*3+2; :dn:=top*3+3 end; case inc(n)運(yùn)算順序+1 end else end;caseend;whileend; ff 3、求值過程設(shè)b為運(yùn)算完成的標(biāo)志序列，其中bi=true，標(biāo)志已完成ci運(yùn)算符指定的運(yùn)算。在含有n個(gè)運(yùn)算的表達(dá)式中，含有n-1個(gè)運(yùn)算符。參與當(dāng)前運(yùn)算的兩個(gè)操作數(shù)為rp和rq。我們采用類似并查集的方法計(jì)算表達(dá)式值，即初始時(shí)，N個(gè)操作數(shù)各組成n個(gè)集合。當(dāng)計(jì)算rprp op rq后，集合q并入集合p （fqp），表明第p個(gè)操作數(shù)和第q個(gè)操作數(shù)已經(jīng)完成了運(yùn)算，計(jì)算結(jié)果記入第p個(gè)操作數(shù)。首先將n個(gè)變量操作數(shù)進(jìn)行代值，并對(duì)n個(gè)操作數(shù)進(jìn)行取摸運(yùn)算。然后在未參與運(yùn)算的運(yùn)算符中尋找運(yùn)算級(jí)最高的運(yùn)算符cmax,dmax= 。然后從max和max+1位置開始沿著f指針尋找兩個(gè)待運(yùn)算的操作數(shù)up和uq（fp=p，fq=q），完成由cmax指定的運(yùn)算，結(jié)果記入up，集合q并入集合p。bmaxtrue。依次類推，直至完成n-1個(gè)運(yùn)算為止。 例如變量a=1、模為10時(shí)，計(jì)算表達(dá)式a+(1+2)3的值：r序列-1123f序列1234c序列+d序列143b序列falsefalsefalsefalse找出運(yùn)算符優(yōu)先級(jí)最高的d2（對(duì)應(yīng)括號(hào)內(nèi)的+）和兩個(gè)操