試題、程序及解題報(bào)告學(xué)校模擬題模擬1mnd

1、2004年分區(qū)聯(lián)賽模擬試題D跳遠(yuǎn)在水平面上整齊的放著n個(gè)正三角形，相鄰兩個(gè)三角形的底邊之間無(wú)空隙，如下圖所示。一個(gè)小孩子想站在某個(gè)三角形i的頂端，跳到三角形j的頂端上(ij)。他總是朝著斜向45度的方向起跳，且初始水平速度v不超過(guò)一個(gè)給定值v0。在跳躍過(guò)程中，由于受到重力作用（忽略空氣阻力），小孩子將沿著拋物線行進(jìn)，水平運(yùn)動(dòng)方程為x = x0 + vt，豎直運(yùn)動(dòng)方程為y = y0 + vt 0.5gt2，運(yùn)動(dòng)軌跡是一條上凸的拋物線。取g=10.0，(x0， y0)是起跳點(diǎn)坐標(biāo)。請(qǐng)編程求出他從每個(gè)位置起跳能到達(dá)的最遠(yuǎn)三角形的編號(hào)。注意：跳躍過(guò)程中不許碰到非起點(diǎn)和終點(diǎn)的其他三角形。 跳遠(yuǎn)在水平面上

2、整齊的放著n個(gè)正三角形，相鄰兩個(gè)三角形的底邊之間無(wú)空隙，如左圖所示。一個(gè)小孩子想站在某個(gè)三角形i的頂端，跳到三角形j的頂端上(ij)。他總是朝著斜向45度的方向起跳，且初始水平速度v不超過(guò)一個(gè)給定值v0。在跳躍過(guò)程中，由于受到重力作用（忽略空氣阻力），小孩子將沿著拋物線行進(jìn)，水平運(yùn)動(dòng)方程為x = x0 + vt，豎直運(yùn)動(dòng)方程為y = y0 + vt 0.5gt2，運(yùn)動(dòng)軌跡是一條上凸的拋物線。取g=10.0，(x0， y0)是起跳點(diǎn)坐標(biāo)。請(qǐng)編程求出他從每個(gè)位置起跳能到達(dá)的最遠(yuǎn)三角形的編號(hào)。注意：跳躍過(guò)程中不許碰到非起點(diǎn)和終點(diǎn)的其他三角形。輸入第一行為兩個(gè)正整數(shù)n，v0(3n10， 1v0100)

3、，表示三角形的個(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ā)無(wú)法達(dá)到任何三角形，相應(yīng)的數(shù)為0。狀態(tài)：起跳點(diǎn)i和i點(diǎn)后的點(diǎn)j。每個(gè)狀態(tài)元素的取值范圍：1in-1，i+1jn 約束條件的分析：判斷小孩能否從i點(diǎn)跳到j(luò)點(diǎn)的方法如下：設(shè)起點(diǎn)和終點(diǎn)間的水平距離為l、垂直距離為h。則由物理知識(shí)（已在題目中給出）有：t = l / vh = vt 5t2 = l 5* 。因此，v = sqrt(5*l*l/ (l - h)。當(dāng)然，這個(gè)v不一定符合要求，

4、它需要滿足兩個(gè)條件。 它不能大于極限速度v0，即必須有v v0 跳躍過(guò)程中不得碰到其他三角形。如何判斷頂點(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è)三角形的頂點(diǎn)不在拋物線下方，則跳遠(yuǎn)不能完成。我們?cè)诿杜e過(guò)程中不斷將小孩所能跳到的點(diǎn)j調(diào)整為best。 枚舉結(jié)束后，best即為試題要求的最遠(yuǎn)點(diǎn)。var len ： array1 . 20 of longint； x， y ： array1 . 20 of

5、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 len1 / 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；

6、 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 l v0 then break；若大于極限速度v0，則無(wú)法從三角形i起跳 ok true； for k i + 1 to j - 1 do判斷跳躍過(guò)程中是否碰到其他三角形 begin t (xk - xi) / v；計(jì)算到達(dá)三角形k的時(shí)間 if (v

7、* 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 break； end；for write(best， )；輸出從三角形i的頂點(diǎn)出發(fā)所能到達(dá)的最右的三角形編號(hào)） end；for writeln；end.main算法initmainprintinit while st dobegin if pos( ,st

8、)=0 then begin datai.s:=st;st:=;end else begin datai.s:=copy(st,1,pos( ,st)-1); st:=copy(st,pos( ,st)+1,length(st)-pos( ,st); inc(i); end;end; k:=i;123456789101112s/729/818/9/8/s1-1-1-1-1-1-1-1-1-1-1-1-1s2-1-1-1-1-1-1-1-1-1-1-1-1s3-1-1-1-1-1-1-1-1-1-1-1-1addup-1-1-1-1-1-1-1-1-1-1-1-1init Main232（只有失

9、誤時(shí)可計(jì)算）if datai.s / then if datai.s2 / thendatai.s1:= ord(datai.s1)-48+ord(datai.s2)-48; s:=0; for i:=1 to k do begin ss:=0; if datai.s1-1 then ss:=ss+datai.s1; if datai.s2-1 then ss:=ss+datai.s2; if datai.s3-1 then ss:=ss+datai.s3; s:=s+ss;datai.addup:=s; end;print for i:=1 to k do begin if not(data

10、i.s1=-1) then begin write(f,datai.addup); if datai+1.s1-1 then write(f, ); end; end;排序工作量 Sort公司是一個(gè)專門為人們提供排序服務(wù)的公司，該公司的宗旨是：“順序是最美麗的”。他們的工作是通過(guò)一系列移動(dòng)，將某些物品按順序擺好。他們的服務(wù)是通過(guò)工作量來(lái)計(jì)算的，即移動(dòng)?xùn)|西的次數(shù)。所以，在工作前必須先考察工作量，以便向用戶提出收費(fèi)數(shù)目。 用戶并不需要知道精確的移動(dòng)次數(shù)，實(shí)質(zhì)上，大多數(shù)人都是憑感覺(jué)來(lái)認(rèn)定這一列物品的混亂程度，根據(jù)Sort公司的經(jīng)驗(yàn)，人們一般是根據(jù)“逆序?qū)Α钡臄?shù)目多少來(lái)稱呼這一序列的混亂程度。假設(shè)我們

11、將序列中第I件物品的參數(shù)定義為AI，那么，排序就是指將A數(shù)組從小到大排序。所謂“逆序?qū)Α笔侵改壳癆1.N中元素各不相同，若IAj，則I,J就為一個(gè)“逆序?qū)Α?。例如，?shù)組的“逆序?qū)Α庇?，共4個(gè)(如圖所示)。輸入輸出樣例輸入： PALIN.IN5Ab3bd輸出：PALIN.OUT2Adb3bdA歸納算法abccbdadbccbdaabcdeabcdedcbaAdb3bdAAb3bd5-2*1-1=26-2*2=25-2*0-1=4Minn-2*最長(zhǎng)公共子序列長(zhǎng)度,n-2*最長(zhǎng)公共子序列長(zhǎng)度-1尋找最長(zhǎng)公共子序列長(zhǎng)度Longestsub(st)=maxlongestsub(st1.j,stn.j+

12、1)1=jnLongestsub(st)=maxlongestsub(st1.j,stn.j+2)-11=jn-1Li,j=尋找最長(zhǎng)公共子序列長(zhǎng)度求st1與st2的最長(zhǎng)公共子序列長(zhǎng)度MaxLi-1,j-1+1,Li,j-1,Li-1,j st1i=st2jMaxLi,j-1,Li-1,j st1ist2jLlength(st1),length(st2)Costi,j表示將原串St從第j位開(kāi)始長(zhǎng)度為i的子串變成回文詞的最小添加字符數(shù)。方法二：Costi,j=stj=sti+j-1stjsti+j-1Costi-2,j+1MinCosti-1,j, Costi-1,j-1當(dāng)i=1或0時(shí)，Cost值

13、為0單向雙軌道 如圖，某火車站有B，C兩個(gè)調(diào)度站，左邊入口A處有n輛火車等待進(jìn)站(從左到右 以a、b、c、d編號(hào))，右邊是出口D，規(guī)定在這一段，火車從A進(jìn)入經(jīng)過(guò)B、C只能從左向右單向 開(kāi)，并且B、C調(diào)度站不限定所能停放的車輛數(shù)。 單向雙軌道 從文件輸入n及n個(gè)小寫字母的一個(gè)排列，該排列表示火車在出口D處形成的從左到右 的火車編號(hào)序列。輸出為一系列操作過(guò)程，每一行形如“h L R”的字母序列，其中h為火車編 號(hào)，L為h車原先所在位置(位置都以A、B、C、D表示)，R為新位置。或者輸出NO表示不 能完成這樣的調(diào)度。 輸入輸出樣例輸入： track.in3cba輸出：track.outc A Bb

14、A Ca A Db C Dc B D輸入輸出樣例從D序列開(kāi)始逐字符處理（從n到1）D序列 cbaA序列 abcB序列 C序列 bc的入棧情況用01串描述數(shù)據(jù)定義const yd1:string5= A B ; yd2:string5= A C ; yd3:string5= A D ; yd4:string5= B C ; yd5:string5= B D ; yd6:string5= C D ;type arr=array1.26 of string6;var sa,sb,sc,sd:string; so,s:arr; n,lena,lenb,lenc:byte; step,b,bs:word

15、; flag:boolean;mainif pos(sdi,sa)0 then main1if pos(sdi,sb)0 then main2if pos(sdi,sc)0 then main3main1t:=1; for j:=k+1 to lena do t:=t*2;while t0 do for j:=1 to lena-k do begin aj:=m mod 2; m:=m div 2;end; for j:=1 to lena-k do 根據(jù)01串入棧 inc(bs);sbs:=sdi+yd3; delete(sa,k,lena+1-k);lena:=k-1; main(i-1);main2for j:=lenb downto k+1 dobeg