分治算法實(shí)驗(yàn)報(bào)告(共4頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第 1 次實(shí)驗(yàn)姓名學(xué)號(hào)班級(jí)時(shí)間10.17上午地點(diǎn)四合院102 實(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è)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。實(shí)驗(yàn)步驟 先解決小規(guī)模的問題，如數(shù)組中只有1 個(gè)元素或者只有兩個(gè)元素時(shí)候的情況

2、。 將問題分解，如果數(shù)組的元素大于等于3 個(gè)，將數(shù)組分為兩個(gè)小的數(shù)組。 遞歸的解各子問題，將(中分解的兩個(gè)小的數(shù)組再進(jìn)行以上兩個(gè)步驟(最后都化為小規(guī)模問題。 將各子問題的解進(jìn)行比較最終得到原問題的解。關(guān)鍵代碼void SelectMaxMin(int *a,int i,int j,int &max,int &min)if(i=j)max= ai;min =ai;return; else int mid=(i+j)/2; int maxi,maxj,mini,minj; SelectMaxMin(a,i,(i+j)/2,maxi,mini); SelectMaxMin(a,(i+

3、j)/2)+1,j,maxj,minj); if(maxi>maxj) max=maxi; else max=maxj; if(mini<minj) min=mini; else min=minj; return; srand(unsigned int)time(NULL);cout << "隨機(jī)產(chǎn)生的數(shù)據(jù)(0-100)：" for(int i=0; i<m; i+)ai = rand()%100;測(cè)試結(jié)果實(shí)驗(yàn)心得由于本次實(shí)驗(yàn)的算法思想之前數(shù)據(jù)結(jié)構(gòu)課程就有了解，相對(duì)來說難度不是很大，通過本次實(shí)驗(yàn)，加深了對(duì)分治法算法的理解，同時(shí)再次鞏固了之前所學(xué)

4、的隨機(jī)數(shù)的產(chǎn)生的使用。實(shí)驗(yàn)中，更加明確了如何分析具體的問題，以及具體寫算法思想以及步驟。要想更好的掌握還得要理論與實(shí)踐結(jié)合！我懂得，程序、工程都是由一個(gè)個(gè)細(xì)節(jié)堆碼起來的，不能忽視任何一個(gè)小問題，要想熟練地寫代碼，還是要扎扎實(shí)實(shí)的練習(xí)！實(shí)驗(yàn)得分助教簽名附錄：完整代碼SelectMaxMin.cpp:#include <iostream>#include <ctime>#include <cstdio>#include <iomanip>#include <cstdlib>using namespace std;void SelectMa

5、xMin(int *a,int i,int j,int &max,int &min)if(i=j)max= ai;min =ai;return; else int mid=(i+j)/2; int maxi,maxj,mini,minj; SelectMaxMin(a,i,(i+j)/2,maxi,mini); SelectMaxMin(a,(i+j)/2)+1,j,maxj,minj); if(maxi>maxj) max=maxi; else max=maxj; if(mini<minj) min=mini; else min=minj; return; int

6、 main()clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();/freopen("in.txt","r",stdin); /freopen("out.txt","w",stdout);int m;cout <<"Please input the number : " cin>> m;int am;srand(unsigned int)time(NULL);cout

7、<< "隨機(jī)產(chǎn)生的數(shù)據(jù)(0-100)：" for(int i=0; i<m; i+)ai = rand()%100;for(int i=0; i<m; i+)cout << ai << " "cout << endl;int max,min;SelectMaxMin(a,0,m-1,max,min);cout << "max = " << max << endl;cout << "min = " <<