暨南大学本科实验报告专用纸
课程名称算法设计与分析成绩评定
实验项目名称分治策略与动态规划指导教师李展
实验项目编号01 实验项目类型设计类实验地点南海楼6楼学生姓名陈奕豪学号2012051351
学院信息科学技术学院系计算机系专业软件工程实验时间年月日
一、实验目的：
本实验涉及用分治策略和动态规划算法来求解优化组合问题。通过上机实验使学员学会程序的录入和调试；通过实验结果的比较，使学员了解两种算法的主要特点。
二、实验内容：
第二章实验题
必做——算法分析题1: 线性时间选择问题
●问题描述
给定线性序集中n个元素和一个整数k, 1≤k≤n, 要求找出这n个元素中第k小的元素
●主要思路及步骤
1.把a数组中元素分为5个一组,选每组中位数后分别将他们移向数
组头,再用同样的方法选取中位数的中位数x,然后按x把a数组分为两个划分,重复上述过程直至划分中元素个数少于75,返回要求值
●算法描述
Type Select(Type a[], int p, int r, int k)
{
if (r-p<75) {
用某个简单排序算法对数组a[p:r]排序;
return a[p+k-1];
};
for ( int i = 0; i<=(r-p-4)/5; i++ )
将a[p+5*i]至a[p+5*i+4]的第3小元素
与a[p+i]交换位置;
//找中位数的中位数，r-p-4即上面所说的n-5
Type x = Select(a, p, p+(r-p-4)/5, (r-p+6)/10);
int i=Partition(a,p,r, x),
j=i-p+1;
if (k<=j) return Select(a,p,i,k);
else return Select(a,i+1,r,k-j);
}
输入和输出
自行设计数组a的元素的值，要求元素个数不少于80个，并实现以下输出：（1）输出数组a中下标范围从p到p+(r-p-4)/5的元素；
（2）输出x的值，判断x是否为数组a中下标范围从p到p+(r-p-4)/5的拟中位数；
（3）输出数组a中下标范围从p到r的元素，验证其是否为以x为基准元素的划分。
源代码：:
#include
#include
#include
void Swap(int *i,int *j){
int a;
a=*i;
*i=*j;
*j=a;
}//交换函数
int Partition(int *a, int p, int r){
int i=p,j=r+1;
int x=a[p];
while(true){
while(a[++i]while(a[--j]>x);
if(i>=j) break;
Swap(&a[i],&a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
void QuickSort(int *a, int p, int r){
if(pint q=Partition(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
}//快速排列
int Partition_S(int *a, int p, int r, int x,int *count){ int i,j=p,temp,z=0;
for(i=0;i<=r;i++){
if(a[i]!=x) z++;
else{
temp=a[z];
a[z]=a[j];
a[j]=temp;
j++;
z++;
(*count)++;
}
}
i=p,j=r+1;
while(true){
while(a[++i]while(a[--j]>x);
if(i>=j) break;
Swap(&a[i],&a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}//划分函数
int Select(int *a, int p, int r, int k){
if(r-p<75){
QuickSort(a,p,r);
return a[p+k-1];
}
int i,j,t;
for(i=0;i<=(r-p-4)/5;i++){
QuickSort(a,p+5*i,p+5*i+4);
int temp=a[p+i];
a[p+i]=a[p+i*5+2];
a[p+i*5+2]=temp;
}
printf("数组a下标p到p+(r-p-4)/5的元素");
for(i=p;i<=p+(r-p-4)/5;i++)
printf("%d ",a[i]);//输出(1)
int x=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);
printf("\n拟中位数:%d\n",x);//输出(2)
int count=0;
i=Partition_S(a,p,r,x,&count);
printf("以%d为基准的划分:",x);
for(t=p;t<=r;t++)
printf("%d ",a[t]);//输出(3)
printf("\n\n");
j=i-p;
if(k<=j) return Select(a,p,i-1,k);
else if(count>=1 && jelse return Select(a,i+count,r,k-j-count);
