實(shí)驗(yàn)一分治與遞歸算法

實(shí)驗(yàn)一 分治與遞歸算法的應(yīng)用一、實(shí)驗(yàn)?zāi)康恼莆辗种嗡惴ǖ幕舅枷耄ǚ?治-合）、技巧和效率分析方法。熟練掌握用遞歸設(shè)計(jì)分治算法的基本步驟（基準(zhǔn)與遞歸方程）。學(xué)會(huì)利用分治算法解決實(shí)際問題。二、實(shí)驗(yàn)內(nèi)容問題描述：題目二：線性時(shí)間選擇給定n個(gè)元素和一個(gè)整數(shù)k,要求用O（n）時(shí)間找出這n個(gè)元素中第k小元素。數(shù)據(jù)輸入：個(gè)人設(shè)定，由鍵盤輸入。要求：1） 完成程序代碼的編寫2） 獨(dú)立完成實(shí)驗(yàn)及實(shí)驗(yàn)報(bào)告三?算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu):使用容器vector來存儲(chǔ)數(shù)據(jù)元素函數(shù)介紹：intPartition（vector<int>&L,intlow,inthigh）將容器內(nèi)元素分為兩部分，返回樞軸下標(biāo)。intQuickSelect（vector<int>&L,intlow,inthigh,intk）查找所求元素，代碼介紹見下面的算法設(shè)計(jì)。算法的設(shè)計(jì)：利用快排的算法原理，每次將容器內(nèi)元素根據(jù)根據(jù)樞軸分成兩部分，返回樞軸的下標(biāo)pivotloc，將下標(biāo)與K（第K小元素的K）進(jìn)行比較，結(jié)果分為下面3種情況：1、pivotloc=kvec[pivotloc]比它左邊的元素都要大，比它右邊的元素都要小，故

vec［pivotloc］必然是第pivotloc小的元素，而pivotloc=k則說明vec［pivotloc］就是所要查找的元素，遞歸結(jié)束。2、 pivotloc>k說明所要查找的元素在下標(biāo)pivotloc的左邊，則對(duì)區(qū)間［1,pivotloc-1］內(nèi)元素再次調(diào)用intPartition（vector<int>&L,intlow,inthigh）函數(shù)。3、 pivotloc<k說明所要查找的元素在下標(biāo)pivotloc的右邊，則對(duì)區(qū)間［pivotloc+1,n］內(nèi)元素再次調(diào)用intPartition(vector<int>&L,intlow,inthigh)函數(shù).程序調(diào)試及運(yùn)行結(jié)果分析U>禺"統(tǒng)性時(shí)間通擇〔生成」遍行）X線性時(shí)間選擇〔證行）U>禺"請(qǐng)輸入元素個(gè)數(shù)及查找第幾小的元素.62請(qǐng)輸入6個(gè)元素468923第2小的元素是3.運(yùn)行成功〔總計(jì)時(shí)間：12s）_線性時(shí)間選擇〔生成，運(yùn)行）x綬性時(shí)間選擇（運(yùn)行）乂

Ct>請(qǐng)輸入元素T數(shù)及查找第幾小的元素.岫請(qǐng)輸入8個(gè)元素019283740第4小的元素是3.運(yùn)行成功〔總計(jì)時(shí)間：15s）□五.實(shí)驗(yàn)總結(jié)附錄:#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下標(biāo)元素閑置不用printf("請(qǐng)輸入元素個(gè)數(shù)及查找第幾小的元素.\n");cin>>n>>k;printf("請(qǐng)輸A%d個(gè)元素\n”,n);for(inti=0;i<n;++i){cin>>t;vec.push_bac