(完整word版)排序算法題目及其代碼

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

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

3、put);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 )【問(wèn)題描述】在一個(gè)舊式的火車站旁邊有一座橋， 其橋面可以繞

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

5、ut6【參考程序】var 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;aj+1:=t;ch

6、ange:=true; inc(s);end;until not change;writeln(s);end.3、眾數(shù) (masses.pas) 【問(wèn)題描述】由文件給出 N 個(gè) 1 到 30000 間無(wú)序數(shù)正整數(shù)，其中 K NK10000,同一 個(gè)正close(output);整數(shù)可能會(huì)出現(xiàn)多次， 出現(xiàn)次數(shù)最多的整數(shù)稱為眾數(shù)。 求出它的眾數(shù)及它出 現(xiàn)的次數(shù)。【輸入格式】輸入文件第一行是正整數(shù)的個(gè)數(shù) N,第二行開始為 N 個(gè)正整數(shù)。 【輸出格式】輸出文件有若干行，每行兩個(gè)數(shù)，第 1 個(gè)是眾數(shù)，第 2 個(gè)是眾數(shù)出現(xiàn)的 次數(shù)?！据斎霕永?masses.in122 4 2 3 2 5 3 7 2 3

7、 4 3 【輸出樣例】 masses.out2434 【參考程序】var n,i,x,min,max,maxx: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 do begin read(x); if xmax then max:=x;inc(ax); if axmaxx

8、then maxx:=ax; end;for i:=min to max do if ai=maxx then writeln(i, ,ai);close(input);close(output);end.4、第 k 小整數(shù) (knunber.pas) 【問(wèn)題描述】現(xiàn)有 n 個(gè)正整數(shù)，nW10000,要求出這 n 個(gè)正整數(shù)中的第 k 個(gè)最小整數(shù) (相同大小的整數(shù)只計(jì)算一次)，k 1000，正整數(shù)均小于 30000。【輸入格式】第一行為 n 和 k，第二行開始為 n 個(gè)正整數(shù)的值，整數(shù)間用空格隔開?！据敵龈袷健康?k 個(gè)最小整數(shù)的值；若無(wú)解，則輸出“ NO RESUL”T 。【輸入樣例】 knu

9、nber.in10 31 3 3 7 2 5 1 2 4 6【輸出樣例】 knunber.out3【參考程序】var 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 dobeginread(x); bx:=true; i

10、f 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、軍事機(jī)密 (Secret.pas)【問(wèn)題描述】軍方截獲的信息由 n (n=30000)個(gè)數(shù)字組成，因?yàn)槭菙硣?guó)的高端秘密，所以一 時(shí)不能破獲。最原始的想法就是對(duì)這 n 個(gè)數(shù)進(jìn)行小到大排序，每個(gè)數(shù)都對(duì)應(yīng)一個(gè) 序號(hào)，然后對(duì)第 i 個(gè)是什么數(shù)感興

11、趣，現(xiàn)在要求編程完成?！据斎敫袷健康谝恍?n，接著是 n 個(gè)截獲的數(shù)字，接著一行是數(shù)字 k，接著是 k 行要輸 出數(shù)的序號(hào)?！据敵龈袷健?k 行序號(hào)對(duì)應(yīng)的數(shù)字。【輸入樣例】 Secret.in5121 1 126 12373243【輸出樣例】 Secret.out7123121【參考程序】var 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;repeatwhile aplm do dec(pr);if plpr;if pll then qsort(l,pr);end;qsortbeginmainassign(input,secret.in);reset(input);assi