实验一分治与递归算法

实验一 分治与递归算法的应用一、实验目的掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。学会利用分治算法解决实际问题。二、实验内容问题描述：题目二：线性时间选择给定n个元素和一个整数k,要求用O（n）时间找出这n个元素中第k小元素。数据输入：个人设定，由键盘输入。要求：1） 完成程序代码的编写2） 独立完成实验及实验报告三・算法设计数据结构:使用容器vector来存储数据元素函数介绍：intPartition（vector<int>&L,intlow,inthigh）将容器内元素分为两部分，返回枢轴下标。intQuickSelect（vector<int>&L,intlow,inthigh,intk）查找所求元素，代码介绍见下面的算法设计。算法的设计：利用快排的算法原理，每次将容器内元素根据根据枢轴分成两部分，返回枢轴的下标pivotloc，将下标与K（第K小元素的K）进行比较，结果分为下面3种情况：1、pivotloc=kvec[pivotloc]比它左边的元素都要大，比它右边的元素都要小，故

vec［pivotloc］必然是第pivotloc小的元素，而pivotloc=k则说明vec［pivotloc］就是所要查找的元素，递归结束。2、 pivotloc>k说明所要查找的元素在下标pivotloc的左边，则对区间［1,pivotloc-1］内元素再次调用intPartition（vector<int>&L,intlow,inthigh）函数。3、 pivotloc<k说明所要查找的元素在下标pivotloc的右边，则对区间［pivotloc+1,n］内元素再次调用intPartition(vector<int>&L,intlow,inthigh)函数.程序调试及运行结果分析U>禺"统性时间通择〔生成」遍行）X线性时间选择〔证行）U>禺"请输入元素个数及查找第几小的元素.62请输入6个元素468923第2小的元素是3.运行成功〔总计时间：12s）_线性时间选择〔生成，运行）x绶性时间选择（运行）乂

Ct>请输入元素T数及查找第几小的元素.岫请输入8个元素019283740第4小的元素是3.运行成功〔总计时间：15s）□五.实验总结附录:#include<stdio.h>#include<vector>#include<iostream>usingnamespacestd;intPartition(vector<int>&L,intlow,inthigh){intpivotkey=L[low];while(low<high){while(low<high&&L[high]>=pivotkey)—high;L[low]=L[high];while(low<high&&L[low]<=pivotkey)++low;L[high]=L[low];}L[low]=pivotkey;returnlow;}intQuickSelect(vector<int>&L,intlow,inthigh,intk){if(low<=high){intpivotloc=Partition(L,low,high);if(pivotloc==k)returnpivotloc;elseif(pivotloc>k)returnQuickSelect(L,low,pivotloc-1,k);elsereturnQuickSelect(L,pivotloc+1,high,k);}}intmain(intargc,char**argv){intn,k,t;vector<int>vec;vec.push_back(0);//0下标元素闲置不用printf("请输入元素个数及查找第几小的元素.\n");cin>>n>>k;printf("请输A%d个元素\n”,n);for(inti=0;i<n;++i){cin>>t;vec.push_bac