(完整word版)排序例題

1、1、明明的隨機數(shù)( Noip2006) 【問題描述】明明想在學校中請一些同學一起做一項問卷調(diào)查， 為了實驗的客觀性， 他先用計 算機生成了 N 個 1 到 1000 之間的隨機整數(shù)(NK100),對于其中重復的數(shù)字， 只保留一個， 把其余相同的數(shù)去掉， 不同的數(shù)對應著不同的學生的學號。 然后再 把這些數(shù)從小到大排序，按照排好的順序去找同學做調(diào)查。請你協(xié)助明明完成 “去重”與“排序”的工作?！据斎胛募枯斎胛募?random.in 有 2 行，第 1 行為 1 個正整數(shù)，表示所生成的隨機數(shù)的個數(shù)： N 第 2 行有 N 個用空格隔開的正整數(shù)，為所產(chǎn)生的隨機數(shù)?！据敵鑫募枯敵鑫募?random.

2、out 也是 2 行，第 1 行為 1 個正整數(shù) M 表示不相同的隨機數(shù) 的個數(shù)。第 2 行為 M 個用空格隔開的正整數(shù)，為從小到大排好序的不相同的隨機 數(shù)?！据斎霕永?020 40 32 67 40 20 89 300 400 15【輸出樣例】815 20 32 40 67 89 300 400【參考程序】/By LYLtimvar n,s:byte;i,min,max,x:word;b:array1.1000of boolean;beginassign(input,random.in);reset(input);assign(output,random.out);rewrite(outp

3、ut);readln(n);fillchar(b,sizeof(b),false);min:=1000;max:=0;s:=0;for i:=1 to n dobeginread(x);bx:=true;if xmax then max:=x;end;close(input);for i:=min to max do if bi then inc(s);writeln(s);for i:=min to max do if bi then write(i, );close(output);end.2、車廂重組( carry.pas )【問題描述】在一個舊式的火車站旁邊有一座橋， 其橋面可以繞河中

4、心的橋墩水平旋轉。 一個 車站的職工發(fā)現(xiàn)橋的長度最多能容納兩節(jié)車廂， 如果將橋旋轉 180 度，則可以把 相鄰兩節(jié)車廂的位置交換， 用這種方法可以重新排列車廂的順序。 于是他就負責 用這座橋將進站的車廂按車廂號從小到大排列。 他退休后， 火車站決定將這一工 作自動化， 其中一項重要的工作是編一個程序， 輸入初始的車廂順序， 計算最少 用多少步就能將車廂排序?！据斎胛募枯斎胛募袃尚袛?shù)據(jù)，第一行是車廂總數(shù)N (不大于 10000),第二行是 N 個不同的數(shù)表示初始的車廂順序。【輸出文件】一個數(shù)據(jù)，是最少的旋轉次數(shù)?！据斎霕永?carry .in44 3 2 1【輸出樣例】 carry .ou

5、t6【參考程序】/By LYLtimvar n,i,j,t:word;a:array1.10000of word;change:boolean;s:longword;beginassign(input,carry.in);reset(input); assign(output,carry.out);rewrite(output);readln(n);for i:=1 to n do read(ai);close(input);s:=0;i:=1;repeatchange:=false;for j:=1 to n-i doif ajaj+1 then begin t:=aj;aj:=aj+1;a

6、j+1:=t;change:=true; inc(s);end;until not change;end.3、眾數(shù) (masses.pas)【問題描述】由文件給出 N個 1到 30000間無序數(shù)正整數(shù)， 其中 個正整數(shù)可能會出現(xiàn)多次， 出現(xiàn)次數(shù)最多的整數(shù)稱為眾數(shù)。 現(xiàn)的次數(shù)?！据斎敫袷健枯斎胛募谝恍惺钦麛?shù)的個數(shù) N,第二行開始為【輸出格式】輸出文件有若干行，每行兩個數(shù)，第 1 個是眾數(shù)，次數(shù)?！据斎霕永?masses.in122 4 2 3 2 5 3 7 2 3 4 3 【輸出樣例】 masses.out2434【參考程序】/By LYLtimvar n,i,x,min,max,max

7、x:word;a:array1.30000of word;beginassign(input,masses.in);reset(input);assign(output,masses.out);rewrite(output); fillchar(a,sizeof(a),0);min:=30000;max:=0;maxx:=0;readln(n);for i:=1 to n dobegin read(x); if xmax then max:=x; inc(ax);if axmaxx then maxx:=ax; end;for i:=min to max do if ai=maxx then

8、writeln(i, ,ai);close(input);close(output);end.4、第 k 小整數(shù) (knunber.pas) 【問題描述】現(xiàn)有 n 個正整數(shù)，nW10000,要求出這 n 個正整數(shù)中的第 k 個最小整數(shù) (相同大小的整數(shù)只計算一次)，k 1000，正整數(shù)均小于 30000?！据斎敫袷健康谝恍袨?n 和 k，第二行開始為 n 個正整數(shù)的值，整數(shù)間用空格隔開?！据敵龈袷健康?k 個最小整數(shù)的值；若無解，則輸出“ NO RESUL”T ?！据斎霕永?knunber.in10 3writeln(s);close(output);K NK10000,同一求出它的眾數(shù)及它

9、出N 個正整數(shù)。第 2 個是眾數(shù)出現(xiàn)的1 3 3 7 2 5 1 2 4 6【輸出樣例】 knunber.out3【參考程序】/By LYLtimvar n,k,i,x,min,max,s:word;b:array1.30000of boolean;beginassign(input,knumber.in);reset(input);assign(output,knumber.out);rewrite(output); fillchar(b,sizeof(b),false);min:=30000;max:=0;s:=0; readln(n,k);for i:=1 to n dobeginrea

10、d(x); bx:=true; if xmax thenmax:=x;end; close(input); for i:=min to max do begin if bi then inc(s); if s=kthen begin writeln(i); close(output); halt; end;end;writeln(NO RESULT); close(output);end.5、軍事機密 (Secret.pas)【問題描述】軍方截獲的信息由 n(n=30000)個數(shù)字組成，因為是敵國的高端秘密，所以一 時不能破獲。 最原始的想法就是對這 n 個數(shù)進行小到大排序， 每個數(shù)都對應一個

11、 序號，然后對第 i 個是什么數(shù)感興趣，現(xiàn)在要求編程完成?！据斎敫袷健康谝恍?n,接著是 n 個截獲的數(shù)字，接著一行是數(shù)字 k,接著是 k 行要輸 出數(shù)的序號?！据敵龈袷健縦 行序號對應的數(shù)字?！据斎霕永?Secret.in5121 1 126 123 73243【輸出樣例】 Secret.out7123121【參考程序】/By LYLtimvar n,i,k:word;a:array1.30000of longword;procedure qsort(l,r:longword);var pl,pr,m,t:longword;beginpl:=l;pr:=r;m:=a(l+r)shr 1;r

12、epeatwhile aplm do dec(pr);if plpr;if pll then qsort(l,pr);end;qsortbeginmainassign(input,secret.in);reset(input);assign(output,secret.out);rewrite(output);readln(n);for i:=1 to n do read(ai);qsort(1,n);readl n(k);for i:=1 to k do begin readln(n); writeln(an); end;close(i nput);close(output);end.6、獎

13、學金(Noip2007)【問題描述】某小學最近得到了一筆贊助，打算拿出其中一部分為學習成績優(yōu)秀的前 5 名學生 發(fā)獎學金。期末，每個學生都有 3 門課的成績：語文、數(shù)學、英語。先按總分從 高到低排序，如果兩個同學總分相同，再按語文成績從高到低排序，如果兩個同 學總分和語文成績都相同，那么規(guī)定學號小的同學排在前面，這樣，每個學生的排序是唯一確定的。任務：先根據(jù)輸入的 3 門課的成績計算總分，然后按上述規(guī)則排序，最后按排名 順序輸出前 5 名學生的學號和總分。注意，在前 5 名同學中，每個人的獎學金都 不相同，因此，你必須嚴格按上述規(guī)則排序。例如，在某個正確答案中，如果前 兩行的輸出數(shù)據(jù)(每行輸出

14、兩個數(shù)：學號、總分)是：7 2795 279這兩行數(shù)據(jù)的含義是：總分最高的兩個同學的學號依次是7 號、5 號。這兩名同學的總分都是 279 (總分等于輸入的語文、數(shù)學、英語三科成績之和)，但學號 為 7 的學生語文成績更高一些。如果你的前兩名的輸出數(shù)據(jù)是：5 2797 279則按輸出錯誤處理，不能得分?！据斎敫袷健枯斎胛募?scholar.in 包含 n+1 行：第 1 行為一個正整數(shù) n，表示該校參加評選的學生人數(shù)。第 2 到 n+1 行,每行有 3 個用空格隔開的數(shù)字，每個數(shù)字都在 0 到 100 之間。第 j 行的3 個數(shù)字依次表示學號為 j-1 的學生的語文、數(shù)學、英語的成績。每個學

15、生的學號按照輸入順序編號為 1n (恰好是輸入數(shù)據(jù)的行號減 1)。所給的數(shù)據(jù) 都是正確的，不必檢驗。【輸出格式】輸出文件 scholar.out 共有 5 行，每行是兩個用空格隔開的正整數(shù)，依次表示前 5 名學生的學號和總分。【輸入輸出樣例 1】scholar.i nscholar.out66 26590 67 804 26487 66 913 25878 89 912 24488 99 771 23767 89 6478 89 98【輸入輸出樣例 2】scholar.i nscholar.out88 26580 89 892 26488 98 786 26490 67 801 25887 6

16、6 915 25878 89 9188 99 7767 89 6478 89 98【限制】50%的數(shù)據(jù)滿足：各學生的總成績各不相同100%勺數(shù)據(jù)滿足：6=*=300【參考程序】/By LYLtimtypeno de=record i,ch:byte; sum:word; end; arr=array1.300of no de;var n: word;stu:arr;ma,e n:byte;procedure in it;var i:word;beg inassig n(i nput,scholar.i n);reset(i nput);readl n(n);for i:=1 to n dobe

17、gi nstui .i:=i; read(stui.ch);readl n( ma,e n);stui.sum:=stui.ch+ma+e n;end;close(i nput);en d;i nitprocedure merge(l,m,r:word);var pt,pl,pr:word;tmp:arr;beg inpt:=l;pl:=l;pr:=m+1;while(pl=m)a nd(prstupr.sum)or(stupl.sum=stupr.sum)and(stupl.ch=stupr.ch)thenbegin tmppt:=stupl; inc(pt); inc(pl); end e

18、lse begintmppt:=stupr; inc(pt); inc(pr); end;while pl=m do begin tmppt:=stupl; inc(pt); inc(pl); end;while pr=r then exit;m:=(l+r)1;mergesort(l,m);mergesort(m+1,r); merge(l,m,r);end;mergesortprocedure print;var i:byte;begin assign(output,scholar.out);rewrite(output); for i:=1 to 5 do writeln(stui.i,

19、stui.sum); close(output);end;printbeginmaininit;mergesort(1,n);print;end.7、統(tǒng)計數(shù)字 (Noip2007)【問題描述】某次科研調(diào)查時得到了 n 個自然數(shù)，每個數(shù)均不超過 1500000000(1.5*109 ) 已知不相同的數(shù)不超過 10000 個，現(xiàn)在需要統(tǒng)計這些自然數(shù)各自出現(xiàn)的次數(shù)， 按照自然數(shù)從小到大的順序輸出統(tǒng)計結果?！据斎敫袷健枯斎胛募?count.in 包含 n+1 行：第 1 行是整數(shù) n ，表示自然數(shù)的個數(shù)。第 2n+1 行每行一個自然數(shù)?！据敵龈袷健枯敵鑫募?count.out 包含 m 行(m 為 n

20、 個自然數(shù)中不相同數(shù)的個數(shù))，按照自然數(shù)從小到大的順序輸出。 每行輸出兩個整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn) 的次數(shù)，其間用一個空格隔開?！据斎胼敵鰳永縞oun t.i ncoun t.out82 324 245 12100 2451002100【限制】40%的數(shù)據(jù)滿足：1=*=100080%的數(shù)據(jù)滿足：1=n=50000100%的數(shù)據(jù)滿足：11;repeatwhile aplm do dec(pr);if pl=pr;if pll then qsort(l,pr);end;qsortprocedure work;var i,k:longword;beginassign(output,count.

21、out);rewrite(output);an+1:=maxlongint;k:=1;for i:=2 to n+1 doif aiai-1 then begin writeln(ai-1, ,k); k:=1;endelse inc(k);close(output);end;workbeginmaininit;qsort(1,n);work;end.分數(shù)(mark)：【問題描述】 問題描述：高考分數(shù)剛剛公布，共有N個人參加考試，為了有便于填寫志 愿，教育部把所有考生的成績平均分成m檔。保證n是m的倍數(shù)。 考試成績在(k-1)*(n/m)+1名到k*(n/m)名的考生被分配到K檔 (k=1,2,3m)。并列第i名的所有考生都被分配到K擋(k=1,2,3m),并列i