算法实验报告_数学_自然科学_专业资料

《算法实验报告_数学_自然科学_专业资料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程实验报告课程名称：计算机算法基础何琨2016-1-2专业班级:学号:姓名:指导教师:报告日期:计算机科学与技术学院目录实验一1一、实验题目1二、目的与要求1三、算法设计1四、实验环境1五、实验过程1六、实验结果4七、结果分析4实验二5一、实验题冃5二、冃的与要求5三、算法设计5四、实验环境5五、实验过程5六、实验结果8七、结果分析8实验一一、实验题目编程实现算法4.17：基于二次取中的选择算法，编制一下过程：PARTITIONINSERTIONSORTINTERCHANGESELECT2二、目的与要

2、求编制测试数据，给岀实验结呆：给出几个不同的数据集，并选择几个不同的r值进行测试。三、算法设计二次取中规则的选择算法的说明性描述：ProcedureSELECT2(A,k,n)〃在集合A中找第k小元素1若n<=r,则釆用插入法直接对A分类并返冋第1<小元索2把A分成大小为1•的山/打个了集合，忽略剩余的元素3设M=｛叫叫,m3，・・.m

3、_n/r」｝是上面»/厂」个子集合的中间值的集合4v<-SELECT2(M9[[_n/r]/2~

4、,[n/rJ)5用PARTITION划分A,v作为划分元索6假设v在位

5、置j7case:k=j：retum(v):k=j：设S是A(l：j・l)屮元素的集合retum(SELECT2(S,k,j-1)):else：return(SELECT2(R,k-j,n-j))endcaseendSELECT2四、实验环境编程语言为c语言，在windows操作系统下运行。五、实验过程源程序#include#includc#includeintr=3;intPARTITION(intp,intq,intA[])Iinti,v,temp

6、;匸p+1；q=q・l;v=A[p];vvhile(l)(for(;A[i]v;q-)；if(i

7、l,inlp,inlq){intitemJJ;for(j=p+l;j<=q;j++

8、){item=A

9、j]；i=j-l；while((i>=p)){A[i+l]=A[i];i=i-l;)A

10、i+ll=item;intSEL(intA[],intm,intp,intk)doubonmnisif(p,m+-A=r)(INSERTIONSORT(Amp=returnm+k・1八wh=e(l)(nup・m+rrfor(H-l八AH(n、r)；i++)(INSERT一ONSORT(Am+(一,1)£m+771)；INSERTCHANGEC&(>m+T-二)4(>m+(i*)*r+H2*H)；nm

11、n=(dou2:c)(n、rrnmrAnmr+lOOOOV2.OOOPnrucei=nn】r=j=SEL(>m・m+nT13r)；一NSERTCHANGE(£>m_)4(A_j_))-〒p+rrjupARTmoN(mj>)；ifo,m+H=k)elseif(〒m+-vk)PHjrrelse(kur宁m+1)_m丄+-八intmain。(int>ll6521346700二jrng1.W2一或赛議*“=)；for(kupkcmk++)prins=%d=Ar)；一printf(=rH%d=r)_p_.in

12、tf(=«»>戈n=)；scanf(=%d=4j)；i=SEL(A,0,7,j);printf("第％d小元素为:",j);printf(”％d”,A[i]);printf(”排序后的数据为:”)；for(i=0;i<=7;i++)printf(H%2d",A[i]);rctum0;)六、实验结果测试数组A[]={0,5,5,2,3,4,3,9,8}。r=4,k=2的实验结果见图r=3,k=3的实验结果见图1・2；尸6,k=6的实验结果见图1・3。[测试数据为：055234398p?=4请输入k

13、2第2小元素为:2排序后的数据为：023345598.Process:returned0(0x0)executiontime:1.826srressanykeytocontinue.图1T测试结果(r=4,k=2)测试数据为^055234398r=3请希入ko第3小元素为：3排序后的数据为：023345598Processreturned0(0x0)executiontime:1.858s[Pressanykeytocontinue.图1-