实验一分治及递归算法

《实验一分治及递归算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计科101冯康201000814128实验一分治与递归算法的应用一、实验目的1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。3．学会利用分治算法解决实际问题。二、实验内容1.问题描述：题目二：线性时间选择给定n个元素和一个整数k，要求用O(n)时间找出这n个元素中第k小元素。2.数据输入：个人设定，由键盘输入。3.要求：1）完成程序代码的编写2）独立完成实验及实验报告三．算法设计数据结构:使用容器vector来存储数据元素函数介绍：intPar

2、tition(vector&L,intlow,inthigh)将容器内元素分为两部分，返回枢轴下标。intQuickSelect(vector&L,intlow,inthigh,intk)查找所求元素，代码介绍见下面的算法设计。算法的设计：利用快排的算法原理，每次将容器内元素根据根据枢轴分成两部分，返回枢轴的下标pivotloc，将下标与K(第K小元素的K)进行比较，结果分为下面3种情况：1、pivotloc=kvec[pivotloc]比它左边的元素都要大，比它右边的元素都要小，故vec[piv

3、otloc]必然是第pivotloc小的元素，而pivotloc=k则说明vec[pivotloc]就是所要查找的元素，递归结束。4计科101冯康2010008141281、pivotloc>k说明所要查找的元素在下标pivotloc的左边，则对区间[1,pivotloc-1]内元素再次调用intPartition(vector&L,intlow,inthigh)函数。2、pivotloc

4、ion(vector&L,intlow,inthigh)函数四.程序调试及运行结果分析五.实验总结附录：#include#include#includeusingnamespacestd;intPartition(vector&L,intlow,inthigh){intpivotkey=L[low];while(low=pivotkey)--high;4计科101冯康20100081

5、4128L[low]=L[high];while(low&L,intlow,inthigh,intk){if(low<=high){intpivotloc=Partition(L,low,high);if(pivotloc==k)returnpivotloc;elseif(pivotloc>k)returnQuickSel

6、ect(L,low,pivotloc-1,k);elsereturnQuickSelect(L,pivotloc+1,high,k);}}intmain(intargc,char**argv){intn,k,t;vectorvec;vec.push_back(0);//0下标元素闲置不用printf("请输入元素个数及查找第几小的元素.");cin>>n>>k;printf("请输入%d个元素",n);for(inti=0;i>t;vec.push_back(t);}cout

7、<