noip普及組賽前沖刺資料

1、數(shù)組 一、數(shù)字數(shù)組ex1_1_1.pas級數(shù)求和(NOIP2002)【題目描述】已知：Sn=1+1/2+1/3+1/n。顯然對于任意一個數(shù)K，當(dāng)n.足夠大的時候，Sn大于K。 現(xiàn)給出一個整數(shù)K(1K15),要求計算出一個最小的n,使得Sn>K 【輸入】一行,一個整數(shù)K【輸出】一行,一個整數(shù)n【輸入樣例】1【輸出樣例】2ex1_1_2.pas陶陶摘蘋果(NOIP2005)【題目描述】陶陶家的院子里有一棵蘋果樹，每到秋天樹上就會結(jié)出10個蘋果。蘋果成熟的時候，陶陶就會跑去摘蘋果。陶陶有個30厘米高的板凳，當(dāng)她不能直接用手摘到蘋果的時候，就會踩到板凳上再試試。 現(xiàn)在已知10個蘋果到地面的高度，

2、以及陶陶把手伸直的時候能夠達到的最大高度，請幫陶陶算一下她能夠摘到的蘋果的數(shù)目。假設(shè)她碰到蘋果，蘋果就會掉下來?！据斎搿績尚袛?shù)據(jù)。第一行包含10個100到200之間（包括100和200）的整數(shù)（以厘米為單位）分別表示10個蘋果到地面的高度，兩個相鄰的整數(shù)之間用一個空格隔開。第二行只包括一個100到120之間（包含100和120）的整數(shù)（以厘米為單位），表示陶陶把手伸直的時候能夠達到的最大高度?！据敵觥恳恍?，這一行只包含一個整數(shù)，表示陶陶能夠摘到的蘋果的數(shù)目?！据斎霕永?00 200 150 140 129 134 167 198 200 111110【輸出樣例】5ex1_1_3.pas數(shù)字統(tǒng)

3、計(NOIP2010)【題目描述】請統(tǒng)計某個給定范圍L, R的所有整數(shù)中，數(shù)字2 出現(xiàn)的次數(shù)。比如給定范圍2, 22，數(shù)字2 在數(shù)2 中出現(xiàn)了1 次，在數(shù)12 中出現(xiàn)1 次，在數(shù)20 中出現(xiàn)1 次，在數(shù)21 中出現(xiàn)1 次，在數(shù)22 中出現(xiàn)2 次，所以數(shù)字2 在該范圍內(nèi)一共出現(xiàn)了6次?！据斎搿抗? 行，為兩個正整數(shù)L 和R，之間用一個空格隔開?！据敵觥抗? 行，表示數(shù)字2 出現(xiàn)的次數(shù)。【輸入樣例】2 22【輸出樣例】6【輸入輸出樣例2】2 100【輸出】20【數(shù)據(jù)范圍】1 L R 10000。ex1_1_4.pas狐貍追兔子【題目描述】圍繞著山頂有m個洞(m<=100)，一只狐貍和一只兔子

4、住在各自的洞里。狐貍總想吃掉兔子。一天，兔子對狐貍說：“你想吃我有一個條件，先把洞從1m編上號，你從m號洞出發(fā)，先到一號洞找我；第二次隔1個洞找我，第三次隔2個洞找我，以后依次類推，次數(shù)不限。若能找到我，你就可以飽餐一頓。不過在沒有找我以前不能停下來?！焙倽M口答應(yīng)就開始找了，它從早到晚進了n次洞（1<=n<=1000），累得昏了過去也沒有找到兔子。請問，兔子躲在幾號洞里？【輸入】一行，洞的個數(shù)m，狐貍進洞的次數(shù)n【輸出】一行，兔子躲的洞的號數(shù)，由小到大輸出，各數(shù)中間用空格隔開【輸入樣例】10 2【輸出樣例】2 4 5 6 7 8 9 10ex1_1_5.pas不高興的津津(NOI

5、P2004)【題目描述】津津上初中了。媽媽認為津津應(yīng)該更加用功學(xué)習(xí)，所以津津除了上學(xué)之外，還要參加媽媽為她報名的各科復(fù)習(xí)班。另外每周媽媽還會送她去學(xué)習(xí)朗誦、舞蹈和鋼琴。但是津津如果一天上課超過八個小時就會不高興，而且上得越久就會越不高興。假設(shè)津津不會因為其它事不高興，并且她的不高興不會持續(xù)到第二天。請你幫忙檢查一下津津下周的日程安排，看看下周她會不會不高興；如果會的話，哪天最不高興?！据斎搿堪ㄆ咝袛?shù)據(jù)，分別表示周一到周日的日程安排。每行包括兩個小于10的非負整數(shù)，用空格隔開，分別表示津津在學(xué)校上課的時間和媽媽安排她上課的時間?！据敵觥恳恍?，這一行只包含一個數(shù)字。如果不會不高興則輸出0，如果會

6、則輸出最不高興的是周幾（用1, 2, 3, 4, 5, 6, 7分別表示周一，周二，周三，周四，周五，周六，周日）。如果有兩天或兩天以上不高興的程度相當(dāng)，則輸出時間最靠前的一天?！据斎霕永? 36 27 25 35 40 40 6【輸出樣例】3ex1_1_6.pas多項式輸出(NOIP2009)【題目描述】一元 n 次多項式可用如下的表達式表示：其中，aixi 稱為i次項，ai稱為i次項的系數(shù)。給出一個一元多項式各項的次數(shù)和系數(shù)，請按照如下規(guī)定的格式要求輸出該多項式：1. 多項式中自變量為x，從左到右按照次數(shù)遞減順序給出多項式。2. 多項式中只包含系數(shù)不為0 的項。3. 如果多項式n 次項系

7、數(shù)為正，則多項式開頭不出現(xiàn)“+”號，如果多項式n 次項系數(shù)為負，則多項式以“-”號開頭。4. 對于不是最高次的項，以“+”號或者“-”號連接此項與前一項，分別表示此項系數(shù)為正或者系數(shù)為負。緊跟一個正整數(shù)，表示此項系數(shù)的絕對值（如果一個高于0 次的項，其系數(shù)的絕對值為1，則無需輸出1）。如果x 的指數(shù)大于1，則接下來緊跟的指數(shù)部分的形式為“xb”，其中b 為x 的指數(shù)；如果x 的指數(shù)為1，則接下來緊跟的指數(shù)部分形式為“x”；如果x 的指數(shù)為0，則僅需輸出系數(shù)即可。5. 多項式中，多項式的開頭、結(jié)尾不含多余的空格?！据斎搿抗灿? 行第一行 1 個整數(shù)，n，表示一元多項式的次數(shù)。第二行有 n+1 個

8、整數(shù)，其中第i 個整數(shù)表示第n-i+1 次項的系數(shù)，每兩個整數(shù)之間用空格隔開。【輸出】共1 行，按題目所述格式輸出多項式?！据斎霕永?100 -1 1 -3 0 10【輸出樣例】100x5-x4+x3-3x2+10【輸入輸出樣例2】3-50 0 0 1【輸出】-50x3+1【數(shù)據(jù)范圍】1 n 100，多項式各次項系數(shù)的絕對值均不超過100。二、字符數(shù)組定義:String等價于array0.255 of char，其中第0號但有存放的是實際長度。Ansistring長度不限。常用操作Length(st) 求st的長度Copy(st,m,n) 從st的第m個位置開始復(fù)制n個字符Delete(st

9、,m,n) 刪除st的第m個位置開始的n個字符Val(st,x,code) 將字符串st轉(zhuǎn)化為數(shù)字x，若能成功轉(zhuǎn)化，則code=0；若不能，code返回第一個非法字符的位置。注：當(dāng)st只有一個字符時，code返回的數(shù)值不準，建議少用code判斷位置。 Str(x,st) 將數(shù)字x轉(zhuǎn)化為字符串st將單個字符c轉(zhuǎn)化為數(shù)字x： x:=ord(c)-48;將單個數(shù)字x轉(zhuǎn)化為字符c： c:=chr(x);將字符串倒序存放在a數(shù)組中：A0:=length(st);For i:=1 to a0 do Ai:=ord(sta0-i+1)-48;ex1_2_1.pasISBN號碼(NOIP2008)【題目描述】

10、每一本正式出版的圖書都有一個ISBN號碼與之對應(yīng),ISBN碼包括9位數(shù)字、1位識別碼和3位分隔符，其規(guī)定格式如“x-xxx-xxxxx-x”,其中符號“-”是分隔符（鍵盤上的減號），最后一位是識別碼，例如0-670-82162-4就是一個標準的ISBN碼。ISBN碼的首位數(shù)字表示書籍的出版語音，例如0代表英語；第一個分隔符“-”之后的三位數(shù)字代表出版社，例如670代表維京出版社；第二個分隔符之后的五位數(shù)字代表該書在該出版社的編號；最后一位為識別碼。識別嗎的計算方法如下：首位數(shù)字乘以1加上次位數(shù)字乘以2以此類推，用所得的結(jié)果mod 11，所得的余數(shù)即為識別碼，如果余數(shù)為10，則識別碼為大寫字母X

11、。例如ISBN碼0-670-82162-4中的識別碼4是這樣得到的：對0670082162這9個數(shù)字，從左至右，分別乘以1，2，9，再求和，即0×1+6×2+2×9=158，然后取158 mod 11的結(jié)果4作為識別碼/你的任務(wù)是編寫程序判斷輸入的ISBN號碼中識別碼是否正確，如果正確，則僅輸出“Right”；如果錯誤，則輸出你認為是正確的ISBN號碼.【輸入】只有一行，是一個字符序列，表示一本書的ISBN號碼（保證輸入符合ISBN號碼.的格式要求）?！据敵觥恳恍校偃巛斎氲腎SBN號碼的識別碼正確，那么輸出“Right”，否則，按照規(guī)定的格式，輸出正確的ISBN

12、號碼（包括分隔符“-”）。【輸入樣例】0-670-82162-4【輸出樣例】Right【輸入輸出洋例2】0-670-82162-0【輸出】0-670-82162-4ex1_2_2.pas數(shù)字反轉(zhuǎn)（NOIP2011）【題目描述】給定一個整數(shù)，請將該數(shù)各個位上數(shù)字反轉(zhuǎn)得到一個新數(shù)。新數(shù)也應(yīng)滿足整數(shù)的常見形式，即除非給定的原數(shù)為零，否則反轉(zhuǎn)后得到的新數(shù)的最高位數(shù)字不應(yīng)為零（參見樣例2）?！据斎搿枯斎牍?1 行，一個整數(shù)N?！据敵觥枯敵龉?1 行，一個整數(shù)，表示反轉(zhuǎn)后的新數(shù)?！据斎霕永?23【輸出樣例】321【輸入輸出樣例 2】輸入：-380輸出：-83【數(shù)據(jù)范圍】-1,000,000,000 N

13、1,000,000,000ex1_2_3.pas乒乓球(noip2003)【題目描述】國際乒聯(lián)現(xiàn)在主席沙拉拉自從上任以來就立志于推行一系列改革，以推動乒乓球運動在全球的普及。其中11分制改革引起了很大的爭議，有一部分球員因為無法適應(yīng)新規(guī)則只能選擇退役。華華就是其中一位，他退役之后走上了乒乓球研究工作，意圖弄明白11分制和21分制對選手的不同影響。在開展他的研究之前，他首先需要對他多年比賽的統(tǒng)計數(shù)據(jù)進行一些分析，所以需要你的幫忙。 華華通過以下方式進行分析，首先將比賽每個球的勝負列成一張表，然后分別計算在11分制和21分制下，雙方的比賽結(jié)果（截至記錄末尾）。 比如現(xiàn)在有這么一份記錄，（其中W表示

14、華華獲得一分，L表示華華對手獲得一分）： WWWWWWWWWWWWWWWWWWWWWWLW 在11分制下，此時比賽的結(jié)果是華華第一局11比0獲勝，第二局11比0獲勝，正在進行第三局，當(dāng)前比分1比1。而在21分制下，此時比賽結(jié)果是華華第一局21比0獲勝，正在進行第二局，比分2比1。如果一局比賽剛開始，則此時比分為0比0。 你的程序就是要對于一系列比賽信息的輸入（WL形式），輸出正確的結(jié)果?！据斎搿棵總€輸入包含若干行字符串（每行至多20個字母），字符串有大寫的W、L和E組成。其中E表示比賽信息結(jié)束，程序應(yīng)該忽略E之后的所有內(nèi)容。【輸出】輸出由兩部分組成，每部分有若干行，每一行對應(yīng)一局比賽的比分（按

15、比賽信息輸入順序）。其中第一部分是11分制下的結(jié)果，第二部分是21分制下的結(jié)果，兩部分之間由一個空行分隔?！据斎霕永縒WWWWWWWWWWWWWWWWWWWWWLWE【輸出樣例】11:011:01:121:02:1ex1_2_4.pas統(tǒng)計單詞數(shù)(NOIP2011)【題目描述】一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計出特定單詞在文章中出現(xiàn)的次數(shù)。 現(xiàn)在，請你編程實現(xiàn)這一功能，具體要求是：給定一個單詞，請你輸出它在給定的文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹配單詞時，不區(qū)分大小寫，但要求完全匹配，即給定單詞必須與文章中的某一獨立單詞在不區(qū)

16、分大小寫的情況下完全相同（參見樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例2）。【輸入】2 行：第 1 行為一個字符串，其中只含字母，表示給定單詞；第 2 行為一個字符串，其中只可能包含字母和空格，表示給定的文章?！据敵觥恐挥幸恍校绻谖恼轮姓业浇o定單詞則輸出兩個整數(shù)，兩個整數(shù)之間用一個空格隔開，分別是單詞在文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置（即在文章中第一次出現(xiàn)時，單詞首字母在文章中的位置，位置從0 開始）；如果單詞在文章中沒有出現(xiàn)，則直接輸出一個整數(shù)-1?！据斎霕永縏oto be or not to be is a question【輸出樣例】2 0【輸入輸出樣

17、例 1 說明】輸出結(jié)果表示給定的單詞 To 在文章中出現(xiàn)兩次，第一次出現(xiàn)的位置為0。【提示】【輸入輸出樣例 2】輸入：toDid the Ottoman Empire lose its power at that time輸出：-1【輸入輸出樣例 2 說明】表示給定的單詞 to 在文章中沒有出現(xiàn)，輸出整數(shù)-1?！緮?shù)據(jù)范圍】1 單詞長度 10。1 文章長度 1,000,000。ex1_2_5.pas計算器的改良(NOIP2000)【題目描述】NCL是一家專門從事計算器改良與升級的實驗室，最近該實驗室收到了某公司所委托的一個任務(wù)：需要在該公司某型號的計算器上加上解一元一次方程的功能。實驗室將這個任

18、務(wù)交給了一個剛進入的新手ZL先生。為了很好的完成這個任務(wù),ZL先生首先研究了一些一元一次方程的實例： 4+3x=8 6a-5+1=2-2a -5+12Y=0 ZL先生被主管告之，在計算器上鍵入的一個一元一次方程中，只包含整數(shù)、小寫字母 及十、一、這三個數(shù)學(xué)符號（當(dāng)然，符號“一”既可作減號，也可作負號）。方程中并沒有括號，也沒有除號，方程中的字母表示未知數(shù)。 【輸入】輸入一個一元一次方程,可認為輸入的一元一次方程均為合法的，且有唯一實數(shù)解?！据敵觥繉⒔夥匠痰慕Y(jié)果（精確至小數(shù)點后三位）輸出?！据斎霕永?a-5+1=2-2a【輸出樣例】a=0.750ex1_2_6.pas字符串編輯【題目描述】從鍵

19、盤輸入一個字符串（長度<=255個字符），例如：This is a book. 現(xiàn)對該字符串進行編輯，編輯功能有：D：刪除一個字符，命令的方式為：   D  a  其中a為被刪除的字符（D和a之間用空格隔開，以下均是）   例如：D  s  表示刪除字符 s ，若字符串中有多個 s，則刪除第一次出現(xiàn)的。         如上例中刪除的結(jié)果為： Thi is a book.I：插入一個字符，命令的格式為：   I

20、  a1  a2  其中a1表示插入到指定字符前面，a2表示將要插入的字符。例如：I  s  d  表示在指定字符 s 的前面插入字符 d ，若原串中有多個 s ，則插入在最后一個字符的前面，如上例中：    原  串：This is a book.    插入后：This ids a book. R：替換一個字符，命令格式為：    R  a1  a2  其中a1為被替換的字符，a2為替換的字符

21、，若在原串中有多個a1則應(yīng)全部替換。例如： 原 串： This is a book.輸入命令：R  o  e    替換后的字符串為： This is a beek.在編輯過程中，若出現(xiàn)被改的字符不存在時，則給出提示信息”no exsit!”。【輸入】輸入包含兩行，第一行為待編輯的字符串；第二行為對該字符串進行操作的命令字符串，其中命令均為大寫字符，命令對象大小寫均有可能，命令和命令對象間用一個空格隔開?！据敵觥枯敵鲋挥幸恍?，即編輯后的字符串【輸入樣例】This is a bookI s d【輸出樣例】 This ids a book高精度算法

22、說明：typearr=array0.maxlen of integer;Readln(x);For i:=1 to length(x) do Ai:=ord(xlength(x)-i+1)-48;A0:=length(X);數(shù)x倒序存放在a數(shù)組中：1高精度加法(結(jié)果存放在C數(shù)組中)procedure jia( a,b:arr; var c:arr);var i,len:integer;beginfillchar(c,sizeof(c),0);if a0>b0 then len:=a0 else len:=b0;for i:=1 to len do begin ci:=ai+bi;ci+1

23、:=ci div 10; /進位ci:=ci mod 10;end;if clen+1>0 then inc(len);c0:=len;end;2高精度減法 在存放到a、b數(shù)組時，保證數(shù)a>b，結(jié)果存放在C數(shù)組中。procedure jian( a,b:arr; var c:arr);var i,len:integer;beginfillchar(c,sizeof(c),0);len:=a0;for i:=1 to len do begin if ai<bi then begin ai+1:=ai+1-1; /借位處理 ai:=ai+10; end; ci:=ai-bi;en

24、d;if clen+1>0 then inc(len);c0:=len;end;plus3高精度乘以單個數(shù)x（0<x<100） 要求：結(jié)果仍然存放在a數(shù)組中。Procedure cheng1(x:longint;var a:arr);Var I,j,len:longint;Begin Len:=a0; For i:=1 to len do Ai:=ai*x; /a內(nèi)所有元素乘以x For i:=1 to len do If ai>10 then begin Ai+1:=ai+1+ai div 10; /進位處理 Ai:=ai mod 10;End; While alen

25、+1>0 do begin Len:=len+1; If alen>10 then begin Alen+1:=alen div 10; Alen:=alen mod 10; End; End;End;4高精度乘以高精度要求：結(jié)果存放在c數(shù)組中。procedure cheng2(a,b:arr; var c:arrvar i,j,len:longint;beginfillchar(c,sizeof(c),0);for i:=1 to a0 dofor j:=1 to b0 do begin ci+j-1:=ci+j-1+ai*bj; ci+j:=ci+j+ci+j-1 div 10

26、;ci+j-1:=ci+j-1 mod 10;end;len:=a0+b0;while (len>1) and (clen=0) do len:=len-1;c0:=len;end;ex2_1.pas麥森數(shù)（NOIP2003）【題目描述】形如2P-1的素數(shù)稱為麥森數(shù)，這時P一定也是個素數(shù)。但反過來不一定，即如果P是個素數(shù)，2P-1不一定也是素數(shù)。到1998年底，人們已找到了37個麥森數(shù)。最大的一個是P=3021377，它有909526位。麥森數(shù)有許多重要應(yīng)用，它與完全數(shù)密切相關(guān)。任務(wù)：輸入P（1000P3100000），計算2P-1的位數(shù)和最后500位數(shù)字(用十進制高精度數(shù)表示)【輸入】

27、只包含一個整數(shù)P（1000P3100000）【輸出】第一行：十進制高精度數(shù)2P-1的位數(shù)。第2-11行：十進制高精度數(shù)2P-1的最后500位數(shù)字。（每行輸出50位，共輸出10行，不足500位時高位補0）不必驗證2P-1與P是否為素數(shù)。【輸入樣例】1279【輸出樣例】3860000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ex2_2.pasHanoi雙塔問題(NOIP2007)【題目描述】給定A,B,C三根足夠長的細柱，在A柱上放有2n個中間有空的

28、圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區(qū)分的(下圖為n=3的情形）?，F(xiàn)要將這些圓盤移到C柱上，在移動過程中可放在B柱上暫存。要求: (1)每次只能移動一個圓盤； (2) A、B、C三根細柱上的圓盤都要保持上小下大的順序； 任務(wù):設(shè)An為2n個圓盤完成上述任務(wù)所需的最少移動次數(shù)，對于輸入的n，輸出An。 【輸入】一個正整數(shù)n，表示在A柱上放有2n個圓盤?！据敵觥績H一行，包含一個正整數(shù)，為完成上述任務(wù)所需的最少移動次數(shù)An?！据斎霕永?【輸出樣例】2【輸入輸出樣例2】 2 【輸出】6 【限制】對于50%的數(shù)據(jù)， 1<=n<=25 對于100% 數(shù)據(jù)

29、， 1<=n<=200 【提示】 設(shè)法建立An與An-1的遞推關(guān)系式。數(shù)論算法1求兩數(shù)x,y的最大公約數(shù). 2求兩數(shù)x、y的最小公倍數(shù)function lcm(x,y:longint):longint;var temp:longint;beginif x<y then begin temp:=x;x:=y;y:=temp;end;lcm:=x;while lcm mod y<>0 do inc(lcm,x);end;function gcd(x,y:longint):longint;beginif b=0 then gcd:=xelse gcd:=gcd(y,x

30、mod y);end ;3、素數(shù)的求法A.判斷一個數(shù)n是否為質(zhì)數(shù)：function prime (n: integer): Boolean;var I: integer;beginprime:=true;for I:=2 to trunc(sqrt(n) doif n mod I=0 then beginprime:=false; break;end;end;B.篩選法判斷l(xiāng)ongint范圍內(nèi)的數(shù)有哪些素數(shù)輸入范圍n，求出1n中的所有素數(shù)。procedure sushu(n);var i,j:longint; f:array1.n of boolean;begin fillchar(f,siz

31、eof(f),true); f1:=false; for i:=2 to trunc(sqrt(n) do if fi then for j:=2 to n div i do fi*j:=false;end;ex3_1.pas最大公約數(shù)與最小公倍數(shù)(NOIP2001)【題目描述】二個正整數(shù)x0,y0(2x0100000,2y01000000),求滿足下列條件的P,Q的個數(shù)。 條件： 1.P,Q是正整數(shù)； 2.要求P,Q以x0為最大公約數(shù)，以y0為最小公倍數(shù)。 試求：滿足條件的所有可能的兩個正整數(shù)的個數(shù)。【輸入】輸入x0和y0【輸出】滿足條件的所有可能的兩個正整數(shù)的個數(shù)【輸入樣例】3 60【輸出

32、樣例】4【提示】樣例說明:此時的P Q分別為： 3 60 15 12 12 15 60 3排序算法對a數(shù)組進行從小到大的排序1.快速排序：procedure qsort(l,r:integer);var i,j,mid:integer;begini:=l;j:=r; mid:=a(l+r) div 2; 將當(dāng)前序列在中間位置的數(shù)定義為中間數(shù)repeatwhile ai<mid do inc(i); 在左半部分尋找比中間數(shù)大的數(shù)while aj>mid do dec(j);在右半部分尋找比中間數(shù)小的數(shù)if i<=j then begin 若找到一組與排序目標不一致的數(shù)對則交換它

33、們swap(ai,aj);inc(i);dec(j); 繼續(xù)找end;until i>j;if l<j then qsort(l,j); 若未到兩個數(shù)的邊界，則遞歸搜索左右區(qū)間if i<r then qsort(i,r);end;sort2.選擇排序：procedure sort;var i,j,temp:integer;beginfor i:=1 to n-1 dofor j:=i+1 to n doif ai>aj then begin temp:=ai; ai:=aj;aj:=temp;end;end;3. 冒泡排序procedure bubble_sort;va

34、r i,j,temp:integer;beginfor i:=1 to n-1 dofor j:=1 to n-i doif aj<aj+1 then begin temp:=aj; aj:=aj+1;aj+1:=temp;end; 每次比較相鄰元素的關(guān)系end;4.桶排序 當(dāng)數(shù)據(jù)的范圍在一有限范圍內(nèi)時。例：輸入n個范圍在0.1000之間的整數(shù)，從小到大排序輸出。Var I,n,x:integer; a:array0.1000 of integer;begin readln(n); fillchar(a,sizeof(a),0); for i:=1 to n do begin read(

35、x); ax:=ax+1; end; for i:=1 to 1000 doif ax<>0 then write(I, );end.5. 歸并排序例：a,b均為已按從小到大排好序的兩個數(shù)組，將其合并為有序的一個數(shù)組。procedure guibin(a,b:arr;la,lb:longint);var i,j,k:longint;begin fillchar(c,sizeof(c),0); i:=1;j:=1;k:=0; repeat k:=k+1; if ai<bj then begin ck:=ai;i:=i+1; end else begin ck:=bj; j:=j

36、+1; end; until (i>la)or(j>lb); if i<=la then for j:=i to la do begin k:=k+1; ck:=ai; end; if j<=lb then for i:=j to lb do begin k:=k+1; ck:=bj; end;end;ex4_1.pas校門外的樹(NOIP2005)【題目描述】某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米。我們可以把馬路看成一個數(shù)軸，馬路的一端在數(shù)軸0的位置，另一端在L的位置；數(shù)軸上的每個整數(shù)點，即0，1，2，L，都種有一棵樹。 由于馬路上有一些

37、區(qū)域要用來建地鐵。這些區(qū)域用它們在數(shù)軸上的起始點和終止點表示。已知任一區(qū)域的起始點和終止點的坐標都是整數(shù)，區(qū)域之間可能有重合的部分?，F(xiàn)在要把這些區(qū)域中的樹（包括區(qū)域端點處的兩棵樹）移走。你的任務(wù)是計算將這些樹都移走后，馬路上還有多少棵樹。 【輸入】第一行有兩個整數(shù)L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表馬路的長度，M代表區(qū)域的數(shù)目，L和M之間用一個空格隔開。接下來的M行每行包含兩個不同的整數(shù)，用一個空格隔開，表示一個區(qū)域的起始點和終止點的坐標?！据敵觥恳恍?，這一行只包含一個整數(shù)，表示馬路上剩余的樹的數(shù)目。【輸入樣例】500 315

38、0 300100 200470 471【輸出樣例】298【數(shù)據(jù)規(guī)?！?對于20%的數(shù)據(jù)，區(qū)域之間沒有重合的部分； 對于其它的數(shù)據(jù)，區(qū)域之間有重合的情況。ex4_2.pas明明的隨機數(shù)（NOIP2006）【題目描述】明明想在學(xué)校中請一些同學(xué)一起做一項問卷調(diào)查，為了實驗的客觀性，他先用計算機生成了N個1到1000之間的隨機整數(shù)（N100），對于其中重復(fù)的數(shù)字，只保留一個，把其余相同的數(shù)去掉，不同的數(shù)對應(yīng)著不同的學(xué)生的學(xué)號。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請你協(xié)助明明完成“去重”與“排序”的工作。【輸入】有2行，第1行為1個正整數(shù)，表示所生成的隨機數(shù)的個數(shù)：N 第2行有N個

39、用空格隔開的正整數(shù)，為所產(chǎn)生的隨機數(shù)?！据敵觥?行，第1行為1個正整數(shù)M，表示不相同的隨機數(shù)的個數(shù)。第2行為M個用空格隔開的正整數(shù)，為從小到大排好序的不相同的隨機數(shù)。【輸入樣例】1020 40 32 67 40 20 89 300 400 15【輸出樣例】815 20 32 40 67 89 300 400ex4_3.pas獎學(xué)金(NOIP2007)【題目描述】某小學(xué)最近得到了一筆贊助，打算拿出其中一部分為學(xué)習(xí)成績優(yōu)秀的前5名學(xué)生發(fā)獎學(xué)金。期末，每個學(xué)生都有3門課的成績:語文、數(shù)學(xué)、英語。先按總分從高到低排序，如果兩個同學(xué)總分相同，再按語文成績從高到低排序，如果兩個同學(xué)總分和語文成績都相同，那

40、么規(guī)定學(xué)號小的同學(xué) 排在前面，這樣，每個學(xué)生的排序是唯一確定的。 任務(wù)：先根據(jù)輸入的3門課的成績計算總分，然后按上述規(guī)則排序，最后按排名順序輸出前五名名學(xué)生的學(xué)號和總分。注意，在前5名同學(xué)中，每個人的獎學(xué)金都不相同，因此，你必須嚴格按上述規(guī)則排序。例如，在某個正確答案中，如果前兩行的輸出數(shù)據(jù)(每行輸出兩個數(shù):學(xué)號、總分) 是: 7 279 5 279 這兩行數(shù)據(jù)的含義是:總分最高的兩個同學(xué)的學(xué)號依次是7號、5號。這兩名同學(xué)的總分都是279(總分等于輸入的語文、數(shù)學(xué)、英語三科成績之和)，但學(xué)號為7的學(xué)生語文成績更高一些。如果你的前兩名的輸出數(shù)據(jù)是: 5 279 7 279 則按輸出錯誤處理，不能

41、得分?！据斎搿康?行為一個正整數(shù)n，表示該校參加評選的學(xué)生人數(shù)。 第2到n+1行，每行有3個用空格隔開的數(shù)字，每個數(shù)字都在0到100之間。第j行的3個數(shù)字依次表示學(xué)號為j-1的學(xué)生的語文、數(shù)學(xué)、英語的成績。每個學(xué)生的學(xué)號按照輸入順序編號為ln (恰好是輸入數(shù)據(jù)的行號減1)。 所給的數(shù)據(jù)都是正確的，不必檢驗。 【輸出】共有5行，每行是兩個用空格隔開的正整數(shù)，依次表示前5名學(xué)生的學(xué)號和總分。【輸入樣例1】690 67 8087 66 9178 89 9188 99 7767 89 6478 89 98【輸出樣例1】6 2654 2643 2582 2441 237【輸入樣例2】 8 80 89 8

42、9 88 98 78 90 67 80 87 66 91 78 89 91 88 99 7767 89 64 78 89 98 【輸出樣例2】 8 2652 264 6 264 1 258 5 258 【限制】 50%的數(shù)據(jù)滿足:各學(xué)生的總成績各不相同；100%的數(shù)據(jù)滿足: 6<=n<=300ex4_4.pas分數(shù)線劃定(NOIP2009)【題目描述】世博會志愿者的選拔工作正在A市如火如荼的進行。為了選拔最合適的人才，A市對所有報名的選手進行了筆試，筆試分數(shù)達到面試分數(shù)線的選手方可進入面試。面試分數(shù)線根據(jù)計劃錄取人數(shù)的150%劃定，即如果計劃錄取m名志愿者，則面試分數(shù)線為排名第m*

43、150%（向下取整）名的選手的分數(shù)，而最終進入面試的選手為筆試成績不低于面試分數(shù)線的所有選手。現(xiàn)在就請你編寫程序劃定面試分數(shù)線，并輸出所有進入面試的選手的報名號和筆試成績。【輸入】第一行，兩個整數(shù)n，m（5 n 5000，3 m n），中間用一個空格隔開，其中n 表示報名參加筆試的選手總數(shù)，m 表示計劃錄取的志愿者人數(shù)。輸入數(shù)據(jù)保證m*150%向下取整后小于等于n。第二行到第 n+1 行，每行包括兩個整數(shù)，中間用一個空格隔開，分別是選手的報名號k（1000 k 9999）和該選手的筆試成績s（1 s 100）。數(shù)據(jù)保證選手的報名號各不相同?！据敵觥康谝恍校袃蓚€整數(shù)，用一個空格隔開，第一個整數(shù)

44、表示面試分數(shù)線；第二個整數(shù)為進入面試的選手的實際人數(shù)。 從第二行開始，每行包含兩個整數(shù)，中間用一個空格隔開，分別表示進入面試的選手的報名號和筆試成績，按照筆試成績從高到低輸出，如果成績相同，則按報名號由小到大的順序輸出?！据斎霕永? 31000 903239 882390 957231 841005 951001 88【輸出樣例】88 51005 952390 951000 901001 883239 88【提示】【樣例說明】m*150% = 3*150% = 4.5，向下取整后為4。保證4 個人進入面試的分數(shù)線為88，但因為88有重分，所以所有成績大于等于88 的選手都可以進入面試，故最終

45、有5 個人進入面試。ex4_5.pas接水問題(NOIP2010)【題目描述】學(xué)校里有一個水房，水房里一共裝有m 個龍頭可供同學(xué)們打開水，每個龍頭每秒鐘的供水量相等，均為1?，F(xiàn)在有n 名同學(xué)準備接水，他們的初始接水順序已經(jīng)確定。將這些同學(xué)按接水順序從1到n 編號，i 號同學(xué)的接水量為wi。接水開始時，1 到m 號同學(xué)各占一個水龍頭，并同時打開水龍頭接水。當(dāng)其中某名同學(xué)j 完成其接水量要求wj 后，下一名排隊等候接水的同學(xué)k馬上接替j 同學(xué)的位置開始接水。這個換人的過程是瞬間完成的，且沒有任何水的浪費。即j 同學(xué)第x 秒結(jié)束時完成接水，則k 同學(xué)第x+1 秒立刻開始接水。若當(dāng)前接水人數(shù)n不足m，

46、則只有n個龍頭供水，其它mn個龍頭關(guān)閉?，F(xiàn)在給出n 名同學(xué)的接水量，按照上述接水規(guī)則，問所有同學(xué)都接完水需要多少秒?！据斎搿康? 行2 個整數(shù)n 和m，用一個空格隔開，分別表示接水人數(shù)和龍頭個數(shù)。第2 行n 個整數(shù)w1、w2、wn，每兩個整數(shù)之間用一個空格隔開，wi 表示i 號同學(xué)的接水量。【輸出】只有一行，1 個整數(shù)，表示接水所需的總時間?！据斎霕永? 34 4 1 2 1【輸出樣例】4【輸入輸出樣例說明】第1 秒，3 人接水。第1 秒結(jié)束時，1、2、3 號同學(xué)每人的已接水量為1，3 號同學(xué)接完水，4 號同學(xué)接替3 號同學(xué)開始接水。第2 秒，3 人接水。第2 秒結(jié)束時，1、2 號同學(xué)每人的

47、已接水量為2，4 號同學(xué)的已接水量為1。第3 秒，3 人接水。第3 秒結(jié)束時，1、2 號同學(xué)每人的已接水量為3，4 號同學(xué)的已接水量為2。4 號同學(xué)接完水，5 號同學(xué)接替4 號同學(xué)開始接水。第4 秒，3 人接水。第4 秒結(jié)束時，1、2 號同學(xué)每人的已接水量為4，5 號同學(xué)的已接水量為1。1、2、5 號同學(xué)接完水，即所有人完成接水?？偨铀畷r間為4 秒?！据斎胼敵鰳永?】8 423 71 87 32 70 93 80 76【輸出】163【數(shù)據(jù)范圍】1 n 10000，1 m 100 且m n；1 wi 100。ex4_6.pas瑞士輪(NOIP2011)【題目描述】在雙人對決的競技性比賽，如乒乓球

48、、羽毛球、國際象棋中，最常見的賽制是淘汰賽和循環(huán)賽。前者的特點是比賽場數(shù)少，每場都緊張刺激，但偶然性較高。后者的特點是較為公平，偶然性較低，但比賽過程往往十分冗長。 本題中介紹的瑞士輪賽制，因最早使用于 1895 年在瑞士舉辦的國際象棋比賽而得名。它可以看作是淘汰賽與循環(huán)賽的折衷，既保證了比賽的穩(wěn)定性，又能使賽程不至于過長。 2*N 名編號為12N 的選手共進行R 輪比賽。每輪比賽開始前，以及所有比賽結(jié)束后，都會按照總分從高到低對選手進行一次排名。選手的總分為第一輪開始前的初始分數(shù)加上已參加過的所有比賽的得分和?？偡窒嗤?，約定編號較小的選手排名靠前。 每輪比賽的對陣安排與該輪比賽開始前的排名

49、有關(guān)：第 1 名和第2 名、第3 名和第4名、第2K 1 名和第2K 名、 、第 2N 1 名和第2N 名，各進行一場比賽。每場比賽勝者得1 分，負者得0 分。也就是說除了首輪以外，其它輪比賽的安排均不能事先確定，而是要取決于選手在之前比賽中的表現(xiàn)。 現(xiàn)給定每個選手的初始分數(shù)及其實力值，試計算在 R 輪比賽過后，排名第Q 的選手編號是多少。我們假設(shè)選手的實力值兩兩不同，且每場比賽中實力值較高的總能獲勝?！据斎搿康谝恍惺侨齻€正整數(shù) N、R、Q，每兩個數(shù)之間用一個空格隔開，表示有2*N 名選手、R 輪比賽，以及我們關(guān)心的名次Q。 第二行是 2*N 個非負整數(shù)s1, s2, , s2N，每兩個數(shù)之間

50、用一個空格隔開，其中si 表示編號為i 的選手的初始分數(shù)。 第三行是 2*N 個正整數(shù)w1, w2, , w2N，每兩個數(shù)之間用一個空格隔開，其中wi 表示編號為i 的選手的實力值?！据敵觥恐挥幸恍校粋€整數(shù)，即 R 輪比賽結(jié)束后，排名第Q 的選手的編號?！据斎霕永? 4 27 6 6 710 5 20 15【輸出樣例】1【提示】【輸入輸出樣例說明】【數(shù)據(jù)范圍】對于 30%的數(shù)據(jù)，1 N 100；對于 50%的數(shù)據(jù)，1 N 10,000；對于 100%的數(shù)據(jù)，1 N 100,000，1 R 50，1 Q 2N，0 s1, s2, , s2N 108，1 w1,w2, , w2N 108。

51、查找算法說明：a數(shù)組有一從小到大有序的數(shù)組，查找x在a數(shù)組中應(yīng)插入的位置。1、折半查找function binsearch(l,n:longint):longint;var i,j,mid:integer;begin i:=l; j:=n; repeat mid:=(i+j) div 2;if x=amid then begin binsearch:=mid;exit;end;if x>amid then i:=mid+1else j:=mid-1; until i>j; binsearch:=i;end;進制轉(zhuǎn)換Type Arr:array1.maxlen of integer;

52、說明：除十進制外的其余進制存放在a數(shù)組中。1、十進制數(shù)x轉(zhuǎn)二進制Procedure shi_zhuan_er(x:longint;var a:arr);Var i:longint;Begin Fillchar(a,sizeof(a),0); I:=0; While x>0 do beginI:=i+1;Ai:=x mod 2;X:=x div 2; End; a0:=i; /轉(zhuǎn)化后的數(shù)倒著存放在a數(shù)組中。End;除2取余法2、任意正整數(shù)x轉(zhuǎn)化成n進制Procedure shi_zhuan_n(x,n:longint;var a:arr);Var i:longint;Begin Fillc

53、har(a,sizeof(a),0); I:=0; While x>0 do beginI:=i+1;Ai:=x mod n;X:=x div n; End; a0:=i; /轉(zhuǎn)化后的數(shù)倒著存放在a數(shù)組中。End;除n取余3、n進制轉(zhuǎn)換為十進制正整數(shù)x（x在longint范圍內(nèi)）procedure n_zhuan_shi(n:longint;a:arr;var x:longint);var i,y:longint;begin y:=1; x:=a1; for i:=2 to a0 do begin y:=y*n; x:=x+y*ai; end;end; ex5_1.pas數(shù)制轉(zhuǎn)化【題目描

54、述】  設(shè)有一個字符串A$的結(jié)構(gòu)為：  A$=m<n>p；其中m為數(shù)字串（長度<=20），而n,p均為1或2位的數(shù)字串（其中所表達的內(nèi)容在2-10之間）。從鍵盤上讀入A$后（不用正確性檢查），將A$中的數(shù)字串m(n進制)，以p進制的形式輸出。    例如：A$=48<10>8；其意義為：將10進制數(shù)48，轉(zhuǎn)換成8進制數(shù)輸出。【輸入說明】一行，即一個滿足A$條件的字符串【輸出說明】一行，轉(zhuǎn)化后的數(shù)字【輸入樣例】48<10>8【輸出樣例】60【數(shù)據(jù)范圍】m以及轉(zhuǎn)化過程和轉(zhuǎn)化后的數(shù)據(jù)都在0，2000000000內(nèi)。 0n16 0p9ex5_2.pas數(shù)列（NOIP2006）【題目描述