分治算法試驗(yàn)用分治法查找數(shù)組元素的最大值和最小值

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第一次實(shí)驗(yàn)姓名學(xué)號(hào)班級(jí)時(shí)間10.17上午地點(diǎn)工訓(xùn)樓309實(shí)驗(yàn)名稱分治算法實(shí)驗(yàn)(用分治法查找數(shù)組元素的最大值和最小值)實(shí)驗(yàn)?zāi)康耐ㄟ^上機(jī)實(shí)驗(yàn)，要求掌握分治算法的問題描述、算法設(shè)計(jì)思想、程序設(shè)計(jì)。實(shí)驗(yàn)原理使用分治的算法，根據(jù)不同的輸入用例，能準(zhǔn)確的輸出用例中的最大值與最小值。笄計(jì)算出程序運(yùn)行所需要的時(shí)間。程序思路：利用分治法，將一個(gè)數(shù)組元素大于2的數(shù)組分成兩個(gè)子數(shù)組，然后對(duì)每一個(gè)子數(shù)組遞歸調(diào)用，直到最小的子數(shù)組的元素個(gè)數(shù)為1個(gè)或者是2個(gè)，此時(shí)直接就能得出最大值與最小值，然后合并子數(shù)組，比較2個(gè)子數(shù)組的最大值與最小值，依次進(jìn)行下去，知道找到整個(gè)數(shù)組的最大值與最小值。實(shí)驗(yàn)步驟1 .

2、先解決小規(guī)模的問題，如數(shù)組中只有1個(gè)兀素或者只有兩個(gè)兀素時(shí)候的情況。2 .將問題分解，如果數(shù)組的元素大于等于3個(gè)，將數(shù)組分為兩個(gè)小的數(shù)組。3 .遞歸的解各子問題，將中分解的兩個(gè)小的數(shù)組再進(jìn)行以上兩個(gè)步驟最后都化為小規(guī)模問題。4 .將各子問題的解進(jìn)行比較最終得到原問題的解。關(guān)鍵代碼/分治法處理整個(gè)數(shù)組，求出最大值與最小值voidmerge(inta,intleft,intright,int&Max,int&Min)(intmax1=0,min1=0,max2=0,min2=0;if(right-left>2)/當(dāng)數(shù)組中元素個(gè)數(shù)大于3時(shí)，才實(shí)行分治法(intmid=(righ

3、t+left)/2;merge(a,left,mid,max1,min1);/左半邊遞歸調(diào)用自身，求出最大值與最小值，分別保存在max1,min1中merge(a,mid+1,right,max2,min2);/右半邊遞歸調(diào)用自身，求出最大值與最小值，分別保存在max2,min2中if(max1>=max2)Max=max1;/子序列的兩合并，求出最大值與最小值elseMax=max2;/分別保存在Max與Minif(min1<=min2)Min=min1;elseMin=min2;)else/當(dāng)數(shù)組中元素個(gè)數(shù)少于2時(shí)，直接賦值處理(Max=compmax(a,left,right

4、);Min=compmin(a,left,right);)非遞歸實(shí)現(xiàn):測(cè)試結(jié)果利用分治法（遞歸實(shí)現(xiàn)）S吊算法賣,一匚三通過這次實(shí)驗(yàn)，加深了我對(duì)分治法的理解，明白了分治法到底是怎樣的一個(gè)過程，在代碼實(shí)現(xiàn)分治法的時(shí)候，也使我加深了對(duì)于自己構(gòu)造函數(shù)的理解，明白實(shí)驗(yàn)心得了分治法利用代碼是怎樣實(shí)現(xiàn)的，以及構(gòu)造函數(shù)的傳參與返回值等等地方需要注意的東西，是我認(rèn)識(shí)到我的編程能力的不足，更加加深了我要好好學(xué)習(xí)，多做練習(xí)的想法，總體收獲很大。實(shí)驗(yàn)比較觀察上面兩個(gè)不同的實(shí)現(xiàn)方法所花費(fèi)的時(shí)間，我們可以看到，采用非遞歸的方法實(shí)現(xiàn)，所花費(fèi)的時(shí)間比利用分治法花費(fèi)的時(shí)間多，為什么會(huì)出現(xiàn)這樣的結(jié)果，我們可以知道在分治法需要比較

5、的次數(shù)比非遞歸方法多，甚至是多得多，所以它所花費(fèi)的時(shí)間也多，所以對(duì)于這種求最大值最小值的問題，利用非遞歸的方法相對(duì)會(huì)于-點(diǎn)。實(shí)驗(yàn)得分助教簽名附錄：完整代碼（分治法）#include<iostream>#include<time.h>#include<iomanip>usingnamespacestd;/當(dāng)數(shù)組中的元素個(gè)數(shù)小于3時(shí)，處理最大值intcompmaxQntA口，intstart,intend)intmax;if(start<end)/有兩個(gè)元素if(Astart<=Aend)max=Aend;elsemax=Astart;else/有一

6、個(gè)元素max=Astart;returnmax;/當(dāng)數(shù)組中元素的個(gè)數(shù)小于2時(shí)，處理最小值intcompmin(intA口，intstart,intend)intmin;if(start<end)/有兩個(gè)元素if(Astart<=Aend)min=Astart;elsemin=Aend;)else/有一個(gè)元素min=Astart;returnmin;)/分治法處理整個(gè)數(shù)組，求最大值與最小值voidmerge(inta,intleft,intright,int&Max,int&Min)/Max,Min用來保存最大值與最小值/之所以使用&引用，是由于如果只是簡(jiǎn)單白

7、使用變量，并不會(huì)改變MaxWMin的值，使用指針也可以intmax1=0,min1=0,max2=0,min2=0;if(right-left>2)/當(dāng)數(shù)組中元素個(gè)數(shù)大于等于3時(shí)，進(jìn)行分治intmid=(right+left)/2;merge(a,left,mid,max1,min1);/左半邊遞歸調(diào)用自身，求出最大值最小值，分別保存在max1,min1中merge(a,mid+1,right,max2,min2);/右半邊遞歸調(diào)用自身，求出最大值最小值，分別保存在max2,min2中if(max1>=max2)/子序列兩兩合并，求出最大值與最小值，保存在MaxWMin中Max=m

8、ax1;elseMax=max2;if(min1<=min2)Min=min1;elseMin=min2;)else/數(shù)組中元素個(gè)數(shù)小于3時(shí)的情況，直接賦值Max=compmax(a,left,right);Min=compmin(a,left,right);)voidran(int*input,intn)/隨機(jī)生成數(shù)組元素函數(shù)inti;srand(time(0);for(i=0;i<n;i+)inputi=rand();inputi='0')inta1000000;/定義全局變量用來存放要查找的數(shù)組intmain()(intn;inti;intmax;intmin

9、;cout<<"請(qǐng)輸入要查找的序列個(gè)數(shù)："<<endl;for(i=0;i<5;i+)(cin>>n;ran(a,n);clock_tstart,end,over;/計(jì)算程序運(yùn)行時(shí)間的算法start=clock();end=clock();over=end-start;start=clock();merge(a,0,n-1,max,min);/調(diào)用分治法算法cout<<max<<'"<<min<<endl;end=clock();printf("Thetim

10、eis%6.3f",(double)(end-start-over)/CLK_TCK);/顯示運(yùn)行時(shí)間)system("pause");/停止運(yùn)行窗口return0;)完整代碼(非遞歸方法)#include<iostream>#include<time.h>#include<iomanip>usingnamespacestd;/隨機(jī)生成數(shù)組元素函數(shù)voidran(int*input,intn)(inti;srand(time(0);for(i=0;i<n;i+)inputi=rand();inputi='0')inta1000000;intmain()(intmax=a0,min=a0;inti,j,n;cout<<"請(qǐng)輸入數(shù)據(jù)規(guī)模："<<endl;for(j=0;j<5;j+)(cin>>n;ran(a,n);clock_tstart,end,over;/計(jì)算程序運(yùn)行時(shí)間的算法start=clock();end=clock();over=end-start;start=clock();for(i=1;i<n;i+)(if(ai>max)max=ai;if(ai<min)min=ai;cout&l