贪心算法实例.docx

实验一 分治与递归算法的应用

一、实验目的
1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。
2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。
3．学会利用分治算法解决实际问题。
二、实验内容
1.问题描述：线性时间选择
给定n个元素和一个整数k，要求用O(n)时间找出这n个元素中第k小元素。
2．算法描述：
Stept1：数据的保存，首先将数据保存到数组e[num]中，并输入k值。
Stept2：选择第一个数据作为分界数据，将比它小的数据储存在它的左边，比它大的储存在右边，这样左右子集就是原问题的两个独立子问题，在用同样的方法解决这些子问题，直到每个子集只有一个数据，就完成了全部的排序。
Stept3：改写快速排序，记一趟快速排序后，分解出左子集中的元素个数为nleft，这选择问题是以下几种情况：
（1） nleft=k-1，则分界数据就是选择问题的解。
（2） nleft>k-1，则选择问题的解继续在左子集中找。
（3） nleft<k-1, 则选择问题的解继续在右子集中找。
这样问题的规模就减小了。
3．测试数据
5 12 23 10 45 92 3 30
K值：3
4实验结果如图：

5关键代码：
int partition(int e[],int i,int j)
{
int tag=e[i];//用第1个记录作为基准 '
while(i<j)
{ //从区间两端交替向中间扫描，直至i=j为止
while(i<j&&e[j]>=tag)
j--; //从右向左扫描
e[i]=e[j];
while(i<j&&e[i]<=tag)
i++;
e[j]=e[i];
}
e[i]=tag;//基准记录已被最后定位
return i;
}

int Seltct(int element[],int lw,int hi,int k)
{
if(lw==hi)
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(k<nleft)
return Seltct(element,lw,q,k);
if(k>nleft)
return Seltct(element,q+1,hi,k-nleft);
}
void main()
{
int i=1;
int num;
int k;
int cn;
cout<<"please input the num of element"<<endl;
cin>>num;
cout<<"please input the elements:"<<endl;
int *e=new int[num];
while(i<=num)
{
cin>>cn;
e[i]=cn;
i++;
}
cout<<"请输入K值";
cin>>k;
int mink=Seltct(e,1,num,k);
cout<<"the k min num is:"<<mink<<endl;
}