算法分析與設計實驗報告求最大子段和實驗報告（含源代碼）

1、昆明理工大學信息工程與自動化學院學生實驗報告（ 2011 2012 學年 第 1 學期 ）課程名稱：算法分析與設計 開課實驗室：信自樓機房445 2011 年11月 23日2011 年12月 14日年級、專業(yè)、班計科092學號200910405201姓名劉召成績實驗項目名稱最大子段和問題指導教師 張晶教師評語該同學是否了解實驗原理：a.了解b.基本了解c.不了解該同學的實驗能力：a.強 b.中等 c.差 該同學的實驗是否達到要求：a.達到b.基本達到c.未達到實驗報告是否規(guī)范：a.規(guī)范b.基本規(guī)范c.不規(guī)范實驗過程是否詳細記錄：a.詳細b.一般 c.沒有 教師簽名： 年 月 日一、上機目的及內

2、容1.上機內容給定有n個整數(shù)（可能有負整數(shù)）組成的序列（a1,a2,an），求改序列形如的子段和的最大值，當所有整數(shù)均為負整數(shù)時，其最大子段和為0。2.上機目的（1）復習數(shù)據(jù)結構課程的相關知識，實現(xiàn)課程間的平滑過渡；（2）掌握并應用算法的數(shù)學分析和后驗分析方法；（3）理解這樣一個觀點：不同的算法能夠解決相同的問題，這些算法的解題思路不同，復雜程度不同，解題效率也不同。二、實驗原理及基本技術路線圖（方框原理圖或程序流程圖）（1）分別用窮舉法、分治法和動態(tài)規(guī)劃法設計最大子段和問題的算法；窮舉法的設計算法流程圖如圖1所示，動態(tài)規(guī)劃算法流程圖如圖2所示，分治發(fā)沒有給出流程圖。（2）對所設計的算法采用大

3、o符號進行時間復雜性分析；窮舉法的時間復雜度是：o（n3）分治發(fā)的時間復雜度是：o（nlg（n）動態(tài)規(guī)劃時間復雜度是：o（n）（3）上機實現(xiàn)算法，并用計數(shù)法和計時法分別測算算法的運行時間；對于所測算的時間與計數(shù)器可以參見運行結果圖，也可以運行電子文檔里的可運行程序（maxsubsum.exe）（4）通過分析對比，得出自己的結論。動態(tài)規(guī)劃算法時間復雜度較好，分治發(fā)次之，窮舉法較差！圖（1）圖（2）三、所用儀器、材料（設備名稱、型號、規(guī)格等或使用軟件）1臺pc及visual studio2005軟件，boost函數(shù)庫四、實驗方法、步驟（或：程序代碼或操作過程）源代碼：/ maxsubsum.cpp

4、 : defines the entry point for the console application./*author劉召 on 2011-11-26此程序在visual studio 8平臺上調試運行的此程序用到了c+委員會建立的boost社區(qū)開發(fā)的boost開源c+庫函數(shù)求解最大子段和簡易系統(tǒng)*/#define boost_date_time_source#include stdafx.h#include #include #include #include #include #include #include #include #include #include #include

5、 using namespace std;using namespace boost;struct infolong start,ed,counting; long long countouer=0; void shutdown(int type) handle htoken; token_privileges tkp; openprocesstoken(getcurrentprocess(),token_adjust_privileges|token_query,&htoken); lookupprivilegevalue(null,se_shutdown_name,&tkp.privile

6、ges0.luid); tkp.privilegecount=1; tkp.privileges0.attributes=se_privilege_enabled; adjusttokenprivileges(htoken,false,&tkp,0,(ptoken_privileges)null,0); exitwindowsex(type|ewx_force,0); void mycomputershutdown() int i; coutt1直接退出！endl; coutt2注銷計算機！endl; coutt3關閉計算機！endl; coutt4重啟計算機！endl; cout; cini

7、;i-=2; shutdown(i); void choice()cout;void choising(char* str)coutn數(shù)據(jù)量較大，是否要str?這將會花很長時間！endl;cout1是t2否endl;choice();void aline(int k,char c);void inputthenumberlist(vector*integerlist)long j,i=1,h=1,t=0,k;string str=你共輸入;if(!(*integerlist).empty()(*integerlist).clear();coutendlright;coutsetw(48)初始化

8、系統(tǒng)數(shù)據(jù)！nendl;coutt1要輸入任意個個數(shù)的數(shù)據(jù)！endl;coutt2要輸入的數(shù)據(jù)個數(shù)已確定！endl;coutt3要隨機產生一定個數(shù)的數(shù)據(jù)作為輸入數(shù)據(jù)！k;if(k=1)while (i=1)cout請輸入第leftsetw(3)hj;(*integerlist).push_back(j);+h;coutn1繼續(xù)輸入下一個數(shù)字！t2退出輸入數(shù)據(jù)模塊！i;else if (k=2)cout請輸入你要輸入的數(shù)據(jù)的個數(shù):k;for (int i1=1;i1=k;i1+)cout請輸入第leftsetw(3)i1j;(*integerlist).push_back(j); elsecout

9、請輸入你要隨機產生的數(shù)據(jù)的個數(shù):k1;mt19937 wng(time(0);jk=abs(long(wng()/177)%1771;for(long i=0;i=jk;i+)ko=rand();ko=rand();coutn正在產生隨機數(shù)據(jù);progress_display pg2(k1);mt19937 rng(rand();uniform_intui(0,ko);while(k1) ko=ui(rng);pg2+;jk=ui(rng);mk=ui(rng);if(mk6000)char* str=輸出隨機產生的數(shù)據(jù);choising(str);cinqw;if(qw=1)|(*integ

10、erlist).size()=6000)ofstream outdata;outdata.open(random output numbers.txt);coutendlstr(*integerlist).size()個數(shù)字，他們是：500)coutmn;coutn第t*mn個數(shù)據(jù)到第i*mn個數(shù)據(jù)是：endl;cin.ignore(12,n);t+;i+;outdataleft第setw(4)1行：;for (long y=0;ymn)&(gmn)long long c=i*mn;if(i*mn=(*integerlist).size() c=(*integerlist).size();co

11、utn第t*mn個數(shù)據(jù)到第c個數(shù)據(jù)是(按回車鍵以繼續(xù)輸出下面的數(shù)據(jù)）：endl;cin.ignore(12,n);t+;i+;g=1;coutleft;coutsetw(16)(*integerlist)y;outdatasetw(16)(*integerlist)y;if(y+1)%5=0) outdataendl第setw(4)y/5+2行：;g+;coutendl;aline(80,$);outdata.close();vector directmethod(vectorintlist,long long* counter)vector textor;long countor=0,lis

12、ize=intlist.size();longlong pk=0,kp=powl(lisize,3);info hhtt;hhtt.counting=hhtt.ed=hhtt.start=0;textor.push_back(hhtt);double f=1,df=0.1686;if(lisize2940) pk=powl(2940,3);f=1.001463*pk/kp;kp=pk;pk=0;if(lisize=5) switch(lisize)case 2:df=0.562; break;case 3: df=0.382;break;case 4: df=0.322;break;case

13、5: df=0.282;break;else if(lisize12) switch(lisize)case 6:df=0.262; break;case 7: df=0.246;break;case 8: df=0.236;break;case 9: case 10: case 11: df=0.224;break;else if(lisize=16) df=0.2084;else if(lisize24) df=0.1964;else if(lisize50) df=0.1864;else if(lisize100) df=0.1764;coutn正在用窮舉法進行運算;progress_d

14、isplay pg3(kp*df);for (int i=0;ilisize;i+)for (long j=i;jlisize;j+)countor=0;for ( long k=j;klisize;k+)(*counter)+;countor+=intlistk;if(lisize=2940) pg3+;else if(pk=textor0.counting)hhtt.counting=countor;hhtt.start=j;hhtt.ed=k;if (countor!=textor0.counting)textor.clear();textor.push_back(hhtt);elseb

15、ool t=true;for ( long p=0;ptextor.size();p+) if (textorp.start=j)&(textorp.ed=k) t=false;break;if(t) textor.push_back(hhtt);return textor;void needkey(string str)cout請按回車鍵（enter）以進入str運算模塊！;cin.ignore(5,n);void aline(int k,char c)for (int i=0;ik;i+)coutc;void sho(vector textor,vectornumlist, long i,

16、string str)coutn由str得到最大字段和是：textori.countingendl;cout相應的子段是從第textori.start+1個數(shù)字（numlisttextori.start）到第textori.ed+1個數(shù)字（numlisttextori.ed）endl;cout它們分別是：endl;int op,p=1;op=0;ofstream outdata;outdata.open(directmethod output submax.txt);outdataleft第setw(4)p行：;for (long j=textori.start;j=textori.ed;j+

17、)coutleft;coutsetw(16)numlistj;outdatasetw(16)numlistj;op+;if(op%5=0) outdataendl第setw(4)+p行：;coutendl;aline(79,*);outdata.close();void showthemethodresult(vector textor,vectornumlist,string str)if (textor.size()=1)sho(textor,numlist,0,str); elsecouttt由str共得到textor.size()個這樣的最大字段!它們分別是：nendl;for ( l

18、ong k=0;ktextor.size();k+)cout第k+1組最大子段的信息：endl;sho(textor,numlist,k,str);long subdealmethod(vectorintegerlist,long long left,long long right)long sum;if (left=right)+countouer;if (integerlistleft0)sum=integerlistleft; elsesum=0; elselong long center=(left+right)/2;long long leftsum=subdealmethod(in

19、tegerlist,left,center);long long rightsum=subdealmethod(integerlist,center+1,right);long long s1=0,aleft=0,s2=0,aright=0;for (long long d=center;d=left;d-)aleft=aleft+integerlistd;if (alefts1) s1=aleft;+countouer;for (long long i=center+1;is2) s2=aright;+countouer;sum=s1+s2;if(sumleftsum)sum=leftsum

20、;if(sumrightsum)sum=rightsum;return sum;long dynamicmethod(vector integerlist,long long *coutor)long sum=0,b=0;for (long i=0;i0)b+=integerlisti; elseb=integerlisti;if(bsum) sum=b; (*coutor)+;return sum;void welcome()coutnsetw(66)歡迎使用求解最大子段和簡易系統(tǒng)(release 2.0)nendl;couttttt學 校：昆明理工大學endl;couttttt學 院：信息

21、工程與自動化學院endl;couttttt專 業(yè)：計算機科學與技術endl;couttttt指導老師：張晶endl;couttttt制 作 人：劉召endl;couttttt學 號：200910405201endl;coutttttqq 郵箱：329245767nendl;void exitsession()coutn正在退出本系統(tǒng)，請稍后;progress_display p(1e9);for (long i=0;i1e9;i+) p+;coutn你已經成功退出本系統(tǒng)！n謝謝你的使用，再見！endl;sleep(1500);int main(int argc, char* arg

22、v) vectorintegerlist;int k=1;welcome();atexit(exitsession);while(k=1)system(color 2b);long long countoer=0;double m;inputthenumberlist(&integerlist);timer tcounter;long result;needkey(動態(tài)規(guī)劃法);system(color 4a);coutn正在用動態(tài)規(guī)劃法進行運算;tcounter.restart();result=dynamicmethod(integerlist,&countoer);m=tcounter.

23、elapsed();coutn動態(tài)規(guī)劃法運算所用時間為：;coutm秒n循環(huán)次數(shù)大約為：;coutcountoer次n動態(tài)規(guī)劃法運算的結果是：resultendl;aline(79,-);needkey(分治法);system(color 1c);coutn正在用分治法進行運算(這可能需要幾秒甚至幾分鐘);tcounter.restart();result=subdealmethod(integerlist,0,integerlist.size()-1);m=tcounter.elapsed();coutn分治法運算所用時間為：;coutm秒n循環(huán)次數(shù)大約為：;coutcountouer次n由

24、分治法運算的結果是：;coutresult2940)char* str1=用窮舉法進行運算;choising(str1);cinip;if (integerlist.size()=2940)|(ip=1)needkey(窮舉法);system(color c0);tcounter.restart();vector mid=directmethod(integerlist,&countoer);m=tcounter.elapsed();coutn窮舉法運算所用時間為：;coutm秒n循環(huán)次數(shù)大約為：;coutcountoer次n由窮舉法運算的結果是：endl;showthemethodresul

25、t(mid,integerlist,窮舉法); coutn1繼續(xù)使用本系統(tǒng)，并求解下一組數(shù)據(jù)的最大子段和n;coutk;aline(80,&);integerlist.clear();mycomputershutdown();return 0;五、實驗過程原始記錄( 測試數(shù)據(jù)、圖表、計算等) 圖（3）手動輸入5個數(shù)據(jù)：7、8、-16、12、3。用動態(tài)規(guī)劃算法運行所得到的最大子段和是15；運行用時不足1毫秒，用計數(shù)器測得循環(huán)次數(shù)為5次！圖（4）在圖（4）中，對于圖（3）中的5個數(shù)據(jù)，用分治發(fā)所得到的最大子段和是15，用計時器測得用時也不足1毫秒，用計數(shù)器測得循環(huán)17次。用窮舉法（直接法）得到的最

26、大子段和也是15，窮舉法可以找到所有具有最大子段和的響應的子段，這5 個數(shù)據(jù)由兩個最大子段；用計時器測得窮舉法用時0.031秒，用計數(shù)器測得循環(huán)35次。由此可以看出，窮舉法用時明顯多于動態(tài)規(guī)劃與分治發(fā)。圖（5）由于動態(tài)規(guī)劃與分治發(fā)時間復雜度較低，所以設置了可以自動隨機產生數(shù)據(jù)的功能，對于隨機產生大于6000個數(shù)據(jù)時，可以選擇是否輸出所產生的數(shù)據(jù)！這里隨機產生了2940個數(shù)據(jù)，因為當隨機產生的數(shù)據(jù)較多時，可能很耗時，所以設置了完成工作的進度顯示功能；若要輸出隨機產生的數(shù)據(jù)，當產生的數(shù)據(jù)個數(shù)大于500時，可以選擇每次輸出的數(shù)據(jù)的個數(shù)，可以按回車鍵輸出下面的數(shù)據(jù)！由于產生的數(shù)據(jù)較多，在這里只顯示一部

27、分。圖（6）由于窮舉法用時較長，所以為窮舉法設置了完成作業(yè)的進度顯示。運算隨機產生的2940個數(shù)據(jù)，三種方法得到的最大子段和結果都是665。用計時器測得動態(tài)規(guī)劃法用時0.015秒，用計數(shù)器測得循環(huán)了2940次。對于分治發(fā)，用計時器測得用時0.016秒，用計數(shù)器測得循環(huán)了37064次。對于窮舉法，用計時器測得用時31.247秒，用計數(shù)器測得循環(huán)了4239686780次。顯然，窮舉法的性能較差，下面隨機產生更多的數(shù)據(jù)繼續(xù)比較動態(tài)規(guī)劃法與分治發(fā)的性能。圖（7）這次隨機產生了五萬個數(shù)據(jù)，由于數(shù)據(jù)量較大，選擇了不輸出隨機產生的數(shù)據(jù)，由于五萬個數(shù)據(jù)用窮舉法將會要很長時間，這里跳過用窮舉法進行運算，說明一下，當數(shù)據(jù)量超過2940個時，將會提示是否用窮舉法進行運算，可以選擇用或不用。用動態(tài)規(guī)劃法對這50000個數(shù)據(jù)運算用時為0.016秒，循環(huán)次數(shù)為50000次。對于分治法，用計時器測得對這50000個數(shù)據(jù)運算用時為14.727秒，用計數(shù)器測得循環(huán)了834464次。由此可以看出，動態(tài)規(guī)劃法性能優(yōu)于分治法！若要得到更多的測試，可以運行電子版文檔附帶