排序算法题目及其代码

1、排序算法题目及其代码 1、明明的随机数( Noip2006) 【问题描述】明明想在学校中请一些同学一起做一项问卷调查， 为了实验的客观性， 他先用计 算机生成了 N个1到1000之间的随机整数(NK 100),对于其中重复的数字， 只保留一个， 把其余相同的数去掉， 不同的数对应着不同的学生的学号。 然后再 把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成 “去重”与“排序”的工作。【输入文件】输入文件 random.in 有 2 行，第 1 行为 1 个正整数，表示所生成的随机数的个数： N 第2行有N个用空格隔开的正整数，为所产生的随机数。【输出文件】输出文件rando

2、m.out也是2行，第1行为1个正整数M表示不相同的随机数 的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机 数。【输入样例】1020 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(outpu

3、t);readln(n);fillchar(b,sizeof(b),false); min:=1000;max:=0;s:=0;for i:=1 to n dobeginread(x);bx:=true;if x<min then min:=x;if x>max 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、车厢重组( carr

4、y.pas )【问题描述】在一个旧式的火车站旁边有一座桥， 其桥面可以绕河中心的桥墩水平旋转。 一个 车站的职工发现桥的长度最多能容纳两节车厢， 如果将桥旋转 180 度，则可以把 相邻两节车厢的位置交换， 用这种方法可以重新排列车厢的顺序。 于是他就负责 用这座桥将进站的车厢按车厢号从小到大排列。 他退休后，火车站决定将这一工 作自动化， 其中一项重要的工作是编一个程序， 输入初始的车厢顺序， 计算最少 用多少步就能将车厢排序。【输入文件】输入文件有两行数据，第一行是车厢总数N (不大于10000),第二行是N个不同的数表示初始的车厢顺序。【输出文件】一个数据，是最少的旋转次数。【输入样例】

5、 carry .in44 3 2 1【输出样例】 carry .out6【参考程序】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

6、 n-i doif aj>aj+1 thenbegint:=aj;aj:=aj+1;aj+1:=t;change:=true;inc(s);end;until not change;writeln(s);close(output);end.3、众数 (masses.pas) 【问题描述】由文件给出N个1到30000间无序数正整数，其中 K NW 10000,同一个正 整数可能会出现多次， 出现次数最多的整数称为众数。 求出它的众数及它出现的 次数。【输入格式】输入文件第一行是正整数的个数N,第二行开始为N个正整数。【输出格式】输出文件有若干行， 每行两个数， 第1个是众数， 第2个是众数

7、出现的次数。 【输入样例】 masses.in122 4 2 3 2 5 3 7 2 3 4 3 【输出样例】 masses.out2 43 4 【参考程序】var n,i,x,min,max,maxx:word;a:array1.30000of word;begin assign(input,'masses.in');reset(input); assign(output,'masses.out');rewrite(output); fillchar(a,sizeof(a),0); min:=30000;max:=0;maxx:=0; readln(n);fo

8、r i:=1 to n dobeginread(x);if x<min then min:=x;if x>max then max:=x;inc(ax);if ax>maxx then maxx:=ax;end;for i:=min to max do if ai=maxx then writeln(i,' ',ai); close(input);close(output);end.4、第 k 小整数 (knunber.pas) 【问题描述】现有n个正整数，nW 10000,要求出这n个正整数中的第k个最小整数(相 同大小的整数只计算一次)，kw 1000，正

9、整数均小于30000。【输入格式】第一行为n和k，第二行开始为n个正整数的值，整数间用空格隔开。【输出格式】第 k 个最小整数的值；若无解，则输出“ NO RESUL”T 。【输入样例】 knunber.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');rewri

10、te(output); fillchar(b,sizeof(b),false);min:=30000;max:=0;s:=0;readln(n,k);for i:=1 to n dobeginread(x);bx:=true;if x<min then min:=x;if x>max then max:=x;end;close(input);for i:=min to max dobeginif bi then inc(s);if s=k then begin writeln(i); close(output); halt; end; end;writeln('NO RES

11、ULT'); close(output);end.5、军事机密 (Secret.pas)【问题描述】军方截获的信息由n (n<=30000)个数字组成，因为是敌国的高端秘密，所以一 时不能破获。最原始的想法就是对这n个数进行小到大排序，每个数都对应一个 序号，然后对第 i 个是什么数感兴趣，现在要求编程完成。【输入格式】第一行n,接着是n个截获的数字，接着一行是数字 k，接着是k行要输出 数的序号。【输出格式】 k 行序号对应的数字。【输入样例】 Secret.in5121 1 126 123 73243【输出样例】 Secret.out7123121 【参考程序】 var n,

12、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 apl<m do inc(pl); while apr>m do dec(pr);if pl<=pr thenbegin t:=apl;apl:=apr;apr:=t; inc(pl);dec(pr);end;until pl>pr;if pl<r then qsort(pl,r);if pr>l then qsort(l,pr); end;qsortbeginmainassign(input,'secret.in');reset(input