1、实验一 分治与递归算法的应用
一、实验目的
1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。
2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。
3．学会利用分治算法解决实际问题。
二、实验内容
1.问题描述：线性时间选择
给定n个元素和一个整数k，要求用O(n)时间找出这n个元素中第k小元素。
2．算法描述：
Stept1：数据的保存，首先将数据保存到数组e[num]中，并输入k值。
Stept2：选择第一个数据作为分界数据，将比它小的数据储存在它的左边，比它大的储存在右边，这样左右子集就是原问题的两个独立子问题，在用同样的方法解决这些子
2、问题，直到每个子集只有一个数据，就完成了全部的排序。
Stept3：改写快速排序，记一趟快速排序后，分解出左子集中的元素个数为nleft，这选择问题是以下几种情况：
（1） nleft=k-1，则分界数据就是选择问题的解。
（2） nleft>k-1，则选择问题的解继续在左子集中找。
（3） nleft3、 tag=e[i];//用第1个记录作为基准 '
while(i=tag)
j--; //从右向左扫描
e[i]=e[j];
while(i4、
return element[lw];
int q=partition(element,lw,hi);//调用quicksort里面的partition, q指向参考数
int nleft=q-lw+1; // l为左数组长度
if(k==nleft)
return element[q];
if(knleft)
return Seltct(element,q+1,hi,k-nleft);
}
void main()
{
int i=1;
int
5、num;
int k;
int cn;
cout<<"please input the num of element"<>num;
cout<<"please input the elements:"<>cn;
e[i]=cn;
i++;
}
cout<<"请输入K值";
cin>>k;
int mink=Seltct(e,1,num,k);
cout<<"the k min num is:"<
浙ICP备2021020529号-1 | 浙B2-20240490 
