算法实验报告.doc

课程实验报告

课程名称：计算机算法基础

专业班级：

学号：

姓名：

指导教师：

何琨

报告日期：

2016-1-2

计算机科学与技术学院

目录

TOC\o1-3\h\u20340实验一 1

22202一、实验题目 1

32396二、目的与要求 1

11414三、算法设计 1

22182四、实验环境 1

3554五、实验过程 1

4630六、实验结果 4

26927七、结果分析 4

21624实验二 5

11722一、实验题目 5

18815二、目的与要求 5

21457三、算法设计 5

24376四、实验环境 5

13788五、实验过程 5

8088六、实验结果 8

20702七、结果分析 8

实验一

实验题目

编程实现算法4.17：基于二次取中的选择算法，编制一下过程：

PARTITION

INSERTIONSORT

INTERCHANGE

SELECT2

目的与要求

编制测试数据，给出实验结果：给出几个不同的数据集，并选择几个不同的r值进行测试。

算法设计

二次取中规那么的选择算法的说明性描述：

ProcedureSELECT2(A，k，n)

//在集合A中找第k小元素

1假设n=r，那么采用插入法直接对A分类并返回第k小元素

2把A分成大小为r的个子集合，忽略剩余的元素

3设是上面个子集合的中间值的集合

4

5用PARTITION划分A，v作为划分元素

6假设v在位置j

7case

：k=j：return(v)

：k=j：设S是A(1：j-1)中元素的集合

return(SELECT2(S，k，j-1))

：else：

return(SELECT2(R，k-j，n-j))

endcase

endSELECT2

实验环境

编程语言为c语言，在windows操作系统下运行。

五、实验过程

源程序

#includestdio.h

#includestdlib.h

#includemath.h

intr=3;

intPARTITION(intp,intq,intA[])

{

inti,v,temp;

i=p+1;

q=q-1;

v=A[p];

while(1)

{

for(;A[i]v;i++);

for(;A[q]v;q--);

if(iq)

{

temp=A[i];A[i]=A[q];A[q]=temp;

}

else

break;

}

A[p]=A[q];A[q]=v;

returnq;

}

voidINSERTCHANGE(int*a,int*b)

{

intt;

t=*a;

*a=*b;

*b=t;

}

voidINSERTIONSORT(intA[],intp,intq)

{

intitem,j,i;

for(j=p+1;j=q;j++)

{

item=A[j];i=j-1;

while((i=p))

{

A[i+1]=A[i];i=i-1;

}

A[i+1]=item;

}

}

intSEL(intA[],intm,intp,intk)

{

doublenrnr;

intn,i,j,nr;

if(p-m+1=r)

{

INSERTIONSORT(A,m,p);

returnm+k-1;

}

while(1)

{

n=p-m+1;

for(i=1;i=(n/r);i++){

INSERTIONSORT(A,m+(i-1)*r,m+i*r-1);

INSERTCHANGE((A[m+i-1]),(A[m+(i-1)*r+r/2-1]));

}

nrnr=(double)(n/r);

nrnr=(nrnr+1.0000)/2.0000;

nr=ceil(nrnr);

j=SEL(A,m,m+n/r-1,nr