算法设计与分析实验(第2、3章).doc

算法设计与分析实验(第2、3章).doc

ID:57985823

大小:125.50 KB

页数:11页

时间:2020-04-05

算法设计与分析实验(第2、3章).doc_第1页
算法设计与分析实验(第2、3章).doc_第2页
算法设计与分析实验(第2、3章).doc_第3页
算法设计与分析实验(第2、3章).doc_第4页
算法设计与分析实验(第2、3章).doc_第5页
资源描述:

《算法设计与分析实验(第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(p

6、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++

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。