资源描述：
《算法设计与分析实验(第2、3章).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、暨南大学本科实验报告专用纸(附页)暨南大学本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称分治策略与动态规划指导教师李展实验项目编号01实验项目类型设计类实验地点南海楼6楼学生姓名陈奕豪学号2012051351学院信息科学技术学院系计算机系专业软件工程实验时间年月日一、实验目的：本实验涉及用分治策略和动态规划算法来求解优化组合问题。通过上机实验使学员学会程序的录入和调试；通过实验结果的比较，使学员了解两种算法的主要特点。二、实验内容：第二章实验题必做——算法分析题1:线性时间选择问题l问题描述给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素l主要思路
2、及步骤1.把a数组中元素分为5个一组,选每组中位数后分别将他们移向数组头,再用同样的方法选取中位数的中位数x,然后按x把a数组分为两个划分,重复上述过程直至划分中元素个数少于75,返回要求值l算法描述暨南大学本科实验报告专用纸(附页)TypeSelect(Typea[],intp,intr,intk)
{
if(r-p<75){
用某个简单排序算法对数组a[p:r]排序;
returna[p+k-1];
};
for(inti=0;i<=(r-p-4)/5;i++)
将a[p+5*i]至a[p+5*i+4]的第3小元素
与a[p+i]交换位置;
//找中位数的中位数，r-p-4即上面所说的n-
3、5
Typex=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);inti=Partition(a,p,r,x),
j=i-p+1;
if(k<=j)returnSelect(a,p,i,k);
elsereturnSelect(a,i+1,r,k-j);
}l输入和输出自行设计数组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为基准元素的划分。源代码：:#in
4、clude#include#includevoidSwap(int*i,int*j){inta;a=*i;暨南大学本科实验报告专用纸(附页)*i=*j;*j=a;}//交换函数intPartition(int*a,intp,intr){inti=p,j=r+1;intx=a[p];while(true){while(a[++i]x);if(i>=j)break;Swap(&a[i],&a[j]);}a[p]=a[j];a[j]=x;returnj;}voidQuickSort(int*a,intp
5、,intr){if(p6、e(a[--j]>x);if(i>=j)break;Swap(&a[i],&a[j]);}a[p]=a[j];a[j]=x;returnj;}//划分函数intSelect(int*a,intp,intr,intk){if(r-p<75){QuickSort(a,p,r);returna[p+k-1];}inti,j,t;for(i=0;i<=(r-p-4)/5;i++){QuickSort(a,p+5*i,p+5*i+4);inttemp=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
7、(i=p;i<=p+(r-p-4)/5;i++)printf("%d",a[i]);//输出(1)intx=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);printf("拟中位数:%d",x);//输出(2)intcount=0;i=Partition_S(a,p,r,x,&count);printf("以%d为基准的划分:",x);for(t=p;t<=r;t++
