实验一分治与递归算法.doc

计科101 冯康 201000814128实验一 分治与递归算法的应用 一、实验目的1掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。2熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。3学会利用分治算法解决实际问题。二、实验内容 1.问题描述：题目二：线性时间选择给定n个元素和一个整数k，要求用O(n)时间找出这n个元素中第k小元素。2.数据输入：个人设定，由键盘输入。3.要求：1）完成程序代码的编写2）独立完成实验及实验报告三算法设计数据结构:使用容器vector来存储数据元素函数介绍：int Partition(vector&L,int low,int high)将容器内元素分为两部分，返回枢轴下标。int QuickSelect(vector&L,int low,int high,int k)查找所求元素，代码介绍见下面的算法设计。算法的设计：利用快排的算法原理，每次将容器内元素根据根据枢轴分成两部分，返回枢轴的下标pivotloc，将下标与K(第K小元素的K)进行比较，结果分为下面3种情况：1、 pivotloc=kvecpivotloc比它左边的元素都要大，比它右边的元素都要小，故vecpivotloc必然是第pivotloc小的元素，而pivotloc=k则说明vecpivotloc就是所要查找的元素，递归结束。2、 pivotlock说明所要查找的元素在下标pivotloc的左边，则对区间1, pivotloc-1内元素再次调用int Partition(vector&L,int low,int high)函数。3、 pivotlock说明所要查找的元素在下标pivotloc的右边，则对区间pivotloc+1,n内元素再次调用int Partition(vector&L,int low,int high)函数四.程序调试及运行结果分析五.实验总结附录：#include #include #include using namespace std;int Partition(vector&L,int low,int high) int pivotkey=Llow; while(lowhigh) while(low=pivotkey) -high; Llow=Lhigh; while(lowhigh&Llow=pivotkey) +low; Lhigh=Llow; Llow=pivotkey; return low; int QuickSelect(vector&L,int low,int high,int k) if(lowk) return QuickSelect(L,low,pivotloc-1,k); else return QuickSelect(L,pivotloc+1,high,k); int main(int argc, char* argv) int n,k,t; vector vec; vec.push_back(0);/0下标元素闲置不用 printf(请输入元素个数及查找第几小的元素.n); cinnk; printf(请输入%d个元素n,n); for(int i=0;it; vec.push_back(t); co