贪心算法实例

《贪心算法实例》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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）nleft

3、;//用第1个记录作为基准'while(i=tag)j--;//从右向左扫描e[i]=e[j];while(i

4、rt里面的partition,q指向参考数intnleft=q-lw+1;//l为左数组长度if(k==nleft)returnelement[q];if(knleft)returnSeltct(element,q+1,hi,k-nleft);}voidmain(){inti=1;intnum;intk;intcn;cout<<"pleaseinputthenumofelement"<>num;cout<<"pleaseinp

5、uttheelements:"<>cn;e[i]=cn;i++;}cout<<"请输入K值";cin>>k;intmink=Seltct(e,1,num,k);cout<<"thekminnumis:"<