(完整word版)排序算法题目及其代码

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

2、文件 random.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(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 )【问题描述】在一个旧式的火车站旁边有一座桥， 其桥面可以绕

4、河中心的桥墩水平旋转。 一个 车站的职工发现桥的长度最多能容纳两节车厢， 如果将桥旋转 180 度，则可以把 相邻两节车厢的位置交换， 用这种方法可以重新排列车厢的顺序。 于是他就负责 用这座桥将进站的车厢按车厢号从小到大排列。 他退休后， 火车站决定将这一工 作自动化，其中一项重要的工作是编一个程序， 输入初始的车厢顺序， 计算最少 用多少步就能将车厢排序。【输入文件】输入文件有两行数据，第一行是车厢总数N (不大于 10000),第二行是 N 个不同的数表示初始的车厢顺序。【输出文件】一个数据，是最少的旋转次数。【输入样例】 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、众数 (masses.pas) 【问题描述】由文件给出 N 个 1 到 30000 间无序数正整数，其中 K NK10000,同一 个正close(output);整数可能会出现多次， 出现次数最多的整数称为众数。 求出它的众数及它出 现的次数。【输入格式】输入文件第一行是正整数的个数 N,第二行开始为 N 个正整数。 【输出格式】输出文件有若干行，每行两个数，第 1 个是众数，第 2 个是众数出现的 次数。【输入样例】 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 小整数 (knunber.pas) 【问题描述】现有 n 个正整数，nW10000,要求出这 n 个正整数中的第 k 个最小整数 (相同大小的整数只计算一次)，k 1000，正整数均小于 30000。【输入格式】第一行为 n 和 k，第二行开始为 n 个正整数的值，整数间用空格隔开。【输出格式】第 k 个最小整数的值；若无解，则输出“ 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、军事机密 (Secret.pas)【问题描述】军方截获的信息由 n (n=30000)个数字组成，因为是敌国的高端秘密，所以一 时不能破获。最原始的想法就是对这 n 个数进行小到大排序，每个数都对应一个 序号，然后对第 i 个是什么数感兴

11、趣，现在要求编程完成。【输入格式】第一行 n，接着是 n 个截获的数字，接着一行是数字 k，接着是 k 行要输 出数的序号。【输出格式】 k 行序号对应的数字。【输入样例】 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