排序实验报告.doc

学生课程实验报告书
09级计算机科学与信息技术系
网络工程专业02班
学号:0930040250 姓名:郭文明

2010-2011学年第二学期

实验项目: 实验六排序
实验目的:
①熟悉掌握各种排序的方法,深刻理解排序算法及其执行的过程。
②学会分析各种排序算法的性能;
③了解各种方法的优缺点,对于实际问题能够选择一种较好的排序方案。
实验内容:
一、最优服务问题
【问题描述】
设有n 个顾客同时等待一项服务。顾客i需要的服务时间为 ti(1<=i<= n)。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是 n 个顾客等待服务时间的总和除以n。
【编程任务】
对于给定的n个顾客需要的服务时间,编程计算最优服务次序。
【数据输入】
输入数据:第一行是正整数n,表示有n 个顾客。接下来的1 行中,有n个正整数,表示n个顾客需要的服务时间。
【结果输出】
将编程计算出的最小平均等待时间输出在屏幕上
输入文件示例
输出文件示例
10

56 12 1 99 1000 234 33 55 99 812
【实验程序如下】
#include<>
void InsertSort(int a[],int n)
{
//希尔排序
int i,j,x,gap=n/2;
float sum=0,avg=0;
while(gap>0)
{
for(i=gap;i<n;i++)
{
j=i-gap;
while(j>=0)
{
if(a[j]>a[j+gap])
{
x=a[j];a[j]=a[j+gap];a[j+gap]=x;
j=j-gap;
}
else
j=-1;
}
}
gap=gap/2;
}
for(i=0;i<n;i++)
sum=sum+(n-i)*a[i];
avg=sum/n;
printf("最小平均等待时间为%f\n",avg);
}
void main()
{
int i,n;
printf("请输入顾客个数n的值:");
scanf("%d",&n);
int c[100];
printf("请输入每个顾客的需要的服务时间:\n");
for(i=0;i<n;i++)
scanf("%d",&c[i]);
InsertSort(c,n);
}
【实验输出】

二、众数问题
【问题描述】
给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。
【编程任务】
对于给定的由n个自然数组成的多重集S,编程计算S的众数及其重数。
【数据输入】
输入数据由文件名为mode*.in的文本文件提供。
文件的第1行多重集S中元素个数n;接下来的n行中,每行有一个自然数。
【结果输出】
程序运行结束时,将计算结果输出到文件mode*.out中。输出文件有2行,第1行给出众数,第2行是重数。
输入文件示例
输出文件示例


6
1
2
2
2
3
5
2
3
【实验程序如下】
#include<>
#define N 100
void main()
{
int a[N];
int count[N]={0};
int i,n,value, max =0, max_index=0;
printf("请输入多重集S的元素个数n的值:");
scanf("%d",&n);
printf("请输入多重集S的%d个元素:\n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
value=++count[a[i]-1];
if(value>max)
{
max= value;
max_index = a[i];
}
}
printf("出现次数最多的数%d,共出现%d次\n",a[max_index],max);
}
【实验输出】

三、士兵站队问题(选作)
【问题描述】
在一个划分成网格的操场上,n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步,但在同一时刻任一网格点上只能有一名士兵。按照军官的命令,士兵们要整齐地列成一个水平队列,即排列成(x