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

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

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

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

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

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

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

7、生數(shù)最多的位置（maxi，maxj），將兩個采集點的距離計入t(tt+ )，并將（maxi，maxj）設(shè)為下一個采集目標(biāo)（max1imaxi;max1jmaxj）。重復(fù)上述計算過程，直至花生田里無花生(max=0)或者采集（max1i，max1j）位置的花生后無法返回路邊（t+max1i-1k）為止。由此得出算法：readln(m,n,k);讀花生田的規(guī)模和多多采花生的限定時間k:=k-2; 計算多多在數(shù)組內(nèi)采集花生的最多時間max:=0;讀花生田的信息。計算花生數(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若在限定時間內(nèi)回到路邊且找到花生最多的植株，則采摘它的花生，并累計采摘的花生總數(shù) begin pmax1i,max1j:=0;total:=total+max; max:=0;計算當(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);累計行程 max1i:=maxi;max1j:=maxj；從該位置出發(fā)，繼續(xù)采摘花生end;while writeln(total);輸出限定時間內(nèi)多多采到花生數(shù)的最大值 時間復(fù)雜度為O (k*n2) 貪心算法 先將花生植株按花生數(shù)遞減的順序排列成一維數(shù)組，數(shù)組元素記錄下植株的花生數(shù)和位置。按照數(shù)組順序，找出距離之和不超過k-2、且最接近k-2的前若干個元素，將這些元素記錄的花生數(shù)累加起來，便構(gòu)成了問題的解。算法的時間復(fù)

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

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

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

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

14、“優(yōu)惠價格”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;計算最少需要的金幣數(shù)遞推每一個客戶h(1hn)11尋找每一個與客戶h的等級差距在限制范圍內(nèi)的客戶i搜索客戶i的每一個可與客戶h交易的替代品j,若替代后花錢更少，則記下 pricei=minpricej+物品j的優(yōu)惠價，物品i的單價12若當(dāng)前

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

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語言 有個機器執(zhí)行一種DASM語言。該機器有一個棧，初始時棧里只有一個元素x，隨著DAM語言程序的執(zhí)行，棧里的元素會發(fā)生變化。DAM語言有四種指令：D指令：把棧頂元素復(fù)制一次加到棧頂A指令：把棧頂元素取出，加到新的棧頂元素中。M指令：把棧頂元素取出，乘到新的

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

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

19、ended；存儲多項式的棧 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)； 存儲多項式的棧清零 degree1 1；初始時棧里只有一個元素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；按照降冪的順序輸出棧頂多項式 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跳遠在水平面上整齊的放著n個正三角形，相鄰兩個三角形的底邊之間無空隙，如左圖所示。一個小孩子想站在某個三角形i的頂端，跳到三角形j的頂端上(ij)。他總是朝著斜向45度的方向起跳，且初始水平速度v不超過一個給定值v0。在跳躍過程中，由于受到重力作用（忽略空氣阻力），小孩子將沿著拋物線行進，水平運動方程為x = x0 + vt，豎直運動方程為y = y0 + vt 0.5gt

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

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

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

26、1 / 2；計算每一個三角形頂端頂點的坐標(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依次計算每一個三角形所能到達的最遠點 begin best 0；從三角形i出發(fā)能到達的最右的三角形編號初始化 for j i + 1 to n do依次枚舉右方的每一個三角形 begin l xj - xi；計算三角形i與三角形j的兩個頂端頂點的水平距離和垂直距離 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；計算到達三角形k的時間 if (v * t - 5 * t * t) - (yk - yi) 1e-6 then begin如果該時刻的豎直坐標(biāo)增量大于起點到頂點k的豎直坐標(biāo)增量，則拋物線在上方 ok false； break； end；then end；forif ok then best j 若跳遠成功，則三角形j為目前三角形i所能到達的最遠點，否則跳遠不能完成 else br

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

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

30、(x) begin f(x)akxk+ak-1kk-1+a1x+a0； end；f function amoncar (a， b， d， n)：real；計算 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)，則累計其點數(shù) end；for amoncarm/n*(b-a)*d；返回曲邊梯形面積 end；amoncar 在主程序中，輸入隨機點的個數(shù)n和a，b，d，然后通過調(diào)用函數(shù)amoncar (a，b，d，n

31、)計算和輸出定積分的值。注意，n愈大，定積分的值愈精確，但速度愈慢。 self-number對任意一個正整數(shù)n，定義d(n)為n加上其每一位上的數(shù)字，比如d(75) = 75 + 7 + 5 = 87。并且稱n是d(n)的一個generator。一個正整數(shù)，如果沒有任何generator，就說這個數(shù)是一個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 在一張一維的布爾表中，從小到大將每個數(shù)n的d(n)都標(biāo)記為不可能是self-number，那么未被標(biāo)記的一定就是self-number了。 布爾表的容量：因為d(n) n并不會很大：最大也不過9*lgn=81。計算d(n)的時間復(fù)雜度原時間復(fù)雜度為O(NlgN)：因為每次計算d(n)時侯分離其每一位的時間復(fù)雜度是O(lgN)。本題中N高達107，因此這個O(lgN)的因子不可以忽略。優(yōu)化首先預(yù)處理，開一個sumi數(shù)組，記錄i的每一位之和，但是這里i的范圍不用太大，只要在O(sqrt(n)=104就可以了。這樣計算d(n)的時侯，就可以將n的各位和分成低4位和高3位來計算，而每

33、次計算不過是調(diào)用sumi，這樣計算d(n)的時間復(fù)雜度就降到了O(1)。綜上，本題的時間復(fù)雜度就是O(sqrt(n)lgN + N + Mlog2M)，其中Mlog2M是在輸出的時侯需要對si進行排序。設(shè)篩data，其中datai 將數(shù)i的d(i)標(biāo)記為不可能是self-number。篩長為1000。self-number序列為request，其中request i. request 為si，request i. number為si的輸入順序，request i. answer為順序為si的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計算sub0sub10000，其中subi為整數(shù)i的各位數(shù)的和； fillchar(data , sizeof(data) , 0);初始時篩滿，即所有數(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);累計self-number的個數(shù) while (p Limit do dec(tmp , Limit);將di限制在1000范圍內(nèi) datatmp := true; datanow := false; 在data篩中保留第now個元素，去掉第di個元素 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;按照輸入要求記下各個self-number數(shù)輸出1.n中self-number的個數(shù) total輸出outarr1 outarrk；構(gòu)造法模擬 構(gòu)造法模擬需要完整精確地構(gòu)造出反映問題本質(zhì)的數(shù)學(xué)模型，根據(jù)該模型設(shè)計狀態(tài)變化的參數(shù)，計算模擬結(jié)果。由于數(shù)學(xué)模型建立了客觀事物間準(zhǔ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é)試驗安排

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

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

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

40、在最后試驗 const TaskLim=1000；最多原料數(shù)var task:array1.2，1.TaskLimof byte；每種原料做放射、加熱試驗的時間 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)；讀每種原料的放射試驗時間和加熱試驗時間end； init procedure Order； 安排試驗順序var i，j，k， min，b

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

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

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

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

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

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

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

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

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

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

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