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

實(shí)驗(yàn)二 分治與遞歸算法的應(yīng)用一、實(shí)驗(yàn)?zāi)康?．掌握分治算法的基本思想（分 -治-合）、技巧和效率分析方法。2．熟練掌握用遞歸設(shè)計(jì)分治算法的基本步驟（基準(zhǔn)與遞歸方程） 。3．學(xué)會(huì)利用分治算法解決實(shí)際問題。二、實(shí)驗(yàn)內(nèi)容問題描述：題目一：線性時(shí)間選擇給定n個(gè)元素和一個(gè)整數(shù)k，要求用O(n)時(shí)間找出這n個(gè)元素中第k小元素。題目二：金塊問題老板有一袋金塊（共n塊，n是2的冪（n≥2））,最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺(tái)比較重量的儀器，希望用最少的比較次數(shù)找出最重和最輕的金塊。并對(duì)自己的程序進(jìn)行復(fù)雜性分析?！据斎胼敵鰳永款}目三：求最大兩個(gè)數(shù)和最小兩個(gè)數(shù)利用分治法求一組數(shù)據(jù)中最大的兩個(gè)數(shù)和最小的兩個(gè)數(shù)。數(shù)據(jù)輸入：個(gè)人設(shè)定，由鍵盤輸入。要求：1）上述題目任選其二。上機(jī)前，完成程序代碼的編寫精選范本,供參考！2）獨(dú)立完成實(shí)驗(yàn)及實(shí)驗(yàn)報(bào)告三、實(shí)驗(yàn)步驟理解算法思想和問題要求；編程實(shí)現(xiàn)題目要求；上機(jī)輸入和調(diào)試自己所編的程序；驗(yàn)證分析實(shí)驗(yàn)結(jié)果；整理出實(shí)驗(yàn)報(bào)告。精選范本,供參考！一．實(shí)驗(yàn)?zāi)康亩畣栴}描述三．算法設(shè)計(jì)包含：數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述、函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)、主要算法流程圖等金塊問題：考慮到可能輸入數(shù)據(jù)有一個(gè)或者兩個(gè)這種情況，所以解決問題時(shí)分三種情況考慮，然后通過函數(shù)調(diào)用來實(shí)現(xiàn)尋找最大最小的數(shù)值。復(fù)雜性分析：當(dāng)n是2的冪時(shí)，即對(duì)于某個(gè)正整數(shù)k，n等于2的k次方，可以證明，任何以元素比較為基礎(chǔ)的找最大和最小元素的算法，其元素比較下界均為[3n/2]-2次。因此，過程maxmin在這種意義上是最優(yōu)的。T(n)=2T(n/2)+2Main函數(shù)輸 循入 環(huán)金 讀塊 入數(shù) 數(shù)量 據(jù)調(diào)用maxmin函數(shù)輸出結(jié)果精選范本,供參考！最大最小兩個(gè)數(shù)：與金塊問題類似，這是尋找最大最小的兩個(gè)數(shù)。利用循環(huán)嵌套條件語句進(jìn)行判斷，選擇出最大最小的兩個(gè)數(shù)。Main函數(shù)輸入相關(guān)數(shù)據(jù)調(diào)用_maxmin函數(shù)利用條件語句進(jìn)行判斷返回maxmin輸出結(jié)果四.程序調(diào)試及運(yùn)行結(jié)果分析1)有五個(gè)金塊，其重量分別為 2.3，1.3，6.9，2，1成功運(yùn)行程序后輸出最重和最輕的金塊的重量。精選范本,供參考！如下圖所示，輸入六個(gè)數(shù)分別為：5,9,12,3,16,2成功運(yùn)行后，輸出最大的2個(gè)元素16，12最小的2個(gè)元素2,3。五.實(shí)驗(yàn)總結(jié)通過本次實(shí)驗(yàn)，我學(xué)會(huì)了如何運(yùn)用分治法將整個(gè)問題分解成若干個(gè)小問題后分而治之，使其產(chǎn)生出方便求解的子問題， 必要時(shí)逐步合并這些子問題的解，從而得到問題的解。在實(shí)驗(yàn)中我觀察了相關(guān)算法結(jié)合老師上課講解的，我覺得這類問題實(shí)際可以用一個(gè)遞歸方程來表示，通過遞歸逐步求解問題。同時(shí)，通過本次實(shí)驗(yàn)我也發(fā)現(xiàn)遞歸算法的重要性，自己對(duì)遞歸算法還不能熟練的應(yīng)用。所以，在課下我會(huì)繼續(xù)努精選范本,供參考！力掌握這種算法，以便能在以后熟練的應(yīng)用它。通過第三題明白了眼過千變不如手動(dòng)一遍,上課是聽懂了.課下我又仔細(xì)的上網(wǎng)看了研究了一下,但是今天敲出來還是有一些問題,我覺得一些問題是值得注意的.附錄：程序清單 （程序過長，可附主要部分）金塊問題程序如下：#include<iostream>usingnamespacestd;inti,n;floata[100];voidmaxmin(inti,intj,float&fmax,float&fmin){intmid;floatlmax,lmin,rmax,rmin;if(i==j){fmax=a[i];fmin=a[i];}elseif(i==j-1)if(a[i]<a[j]){fmax=a[j];fmin=a[i];}else{fmax=a[i];fmin=a[j];}else{mid=(i+j)/2;maxmin(i,mid,lmax,lmin);maxmin(mid+1,j,rmax,rmin);if(lmax>rmax)fmax=lmax;else精選范本,供參考！fmax=rmax;if(lmin>rmin)fmin=rmin;elsefmin=lmin;}}intmain(){cout<<"請(qǐng)輸入金塊的數(shù)量： "<<endl;cin>>n;cout<<"請(qǐng)輸入"<<n<<"塊金子的重量 "<<endl;for(i=1;i<=n;i++)cin>>a[i];floatmax,min;maxmin(1,n,max,min);cout<<"最重金塊是"<<max<<""<<" 最輕金塊是"<<min<<endl;return0;}求最大兩個(gè)數(shù)和最小兩個(gè)數(shù)#include<iostream>usingnamespacestd;inta[100];void_maxmin(inti,intj,int*max1,int*min1,int*max2,int*min2){intmax,min,minmax,minmin;if(i==j){*max1=*min1=*min2=*max2=a[i];}else{if(i==j-1){if(a[i]<a[j]){*max1=*min2=a[j];*min1=*max2=a[i];}else{*max1=*min2=a[i];*min1=*max2=a[j];}}else{intm=(i+j)/2;_maxmin(i,m,max1,min1,max2,min2);_maxmin(m+1,j,&max,&min,&minmax,&minmin);if(*max1<max)精選范本,供參考！{*max2=*max1;*max1=max;if(max!=minmax){if(*max2<minmax){*max2=minmax;}}}else{if(*max2<max){*max2=max;}}if(*min1>min){*min2=*min1;*min1=min;if(min!=minmin)if(*min2>minmin){*min2=minmin;}}else{if(*min2>min){*min2=min;}}}}}intmain(){intn,i,m,max[2],min[2];cout<<"你要輸入幾個(gè)數(shù)？ "<<endl;cin>>n;cout<<"請(qǐng)分別輸入："<<endl;for(i=0;i<n;i++){cin>>m;a[i]=m;}_maxmin(0,n-1,&max[0],&min[0],&max[1],&min[1]);cout<<"輸入的數(shù)中最大的 2個(gè)元素為："<<max[0