算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告求最大子段和實(shí)驗(yàn)報(bào)告（含源代碼）

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

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

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

4、 : defines the entry point for the console application./*author劉召 on 2011-11-26此程序在visual studio 8平臺(tái)上調(diào)試運(yùn)行的此程序用到了c+委員會(huì)建立的boost社區(qū)開發(fā)的boost開源c+庫(kù)函數(shù)求解最大子段和簡(jiǎn)易系統(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注銷計(jì)算機(jī)！endl; coutt3關(guān)閉計(jì)算機(jī)！endl; coutt4重啟計(jì)算機(jī)！endl; cout; cini

7、;i-=2; shutdown(i); void choice()cout;void choising(char* str)coutn數(shù)據(jù)量較大，是否要str?這將會(huì)花很長(zhǎng)時(shí)間！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要輸入任意個(gè)個(gè)數(shù)的數(shù)據(jù)！endl;coutt2要輸入的數(shù)據(jù)個(gè)數(shù)已確定！endl;coutt3要隨機(jī)產(chǎn)生一定個(gè)數(shù)的數(shù)據(jù)作為輸入數(shù)據(jù)！k;if(k=1)while (i=1)cout請(qǐng)輸入第leftsetw(3)hj;(*integerlist).push_back(j);+h;coutn1繼續(xù)輸入下一個(gè)數(shù)字！t2退出輸入數(shù)據(jù)模塊！i;else if (k=2)cout請(qǐng)輸入你要輸入的數(shù)據(jù)的個(gè)數(shù):k;for (int i1=1;i1=k;i1+)cout請(qǐng)輸入第leftsetw(3)i1j;(*integerlist).push_back(j); elsecout

9、請(qǐng)輸入你要隨機(jī)產(chǎn)生的數(shù)據(jù)的個(gè)數(shù):k1;mt19937 wng(time(0);jk=abs(long(wng()/177)%1771;for(long i=0;i=jk;i+)ko=rand();ko=rand();coutn正在產(chǎn)生隨機(jī)數(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=輸出隨機(jī)產(chǎn)生的數(shù)據(jù);choising(str);cinqw;if(qw=1)|(*integ

10、erlist).size()=6000)ofstream outdata;outdata.open(random output numbers.txt);coutendlstr(*integerlist).size()個(gè)數(shù)字，他們是：500)coutmn;coutn第t*mn個(gè)數(shù)據(jù)到第i*mn個(gè)數(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個(gè)數(shù)據(jù)到第c個(gè)數(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正在用窮舉法進(jìn)行運(yùn)算;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請(qǐng)按回車鍵（enter）以進(jìn)入str運(yùn)算模塊！;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相應(yīng)的子段是從第textori.start+1個(gè)數(shù)字（numlisttextori.start）到第textori.ed+1個(gè)數(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()個(gè)這樣的最大字段!它們分別是：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)歡迎使用求解最大子段和簡(jiǎn)易系統(tǒng)(release 2.0)nendl;couttttt學(xué) 校：昆明理工大學(xué)endl;couttttt學(xué) 院：信息

21、工程與自動(dòng)化學(xué)院endl;couttttt專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)endl;couttttt指導(dǎo)老師：張晶endl;couttttt制 作 人：劉召endl;couttttt學(xué) 號(hào)：200910405201endl;coutttttqq 郵箱：329245767nendl;void exitsession()coutn正在退出本系統(tǒng)，請(qǐng)稍后;progress_display p(1e9);for (long i=0;i1e9;i+) p+;coutn你已經(jīng)成功退出本系統(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(動(dòng)態(tài)規(guī)劃法);system(color 4a);coutn正在用動(dòng)態(tài)規(guī)劃法進(jìn)行運(yùn)算;tcounter.restart();result=dynamicmethod(integerlist,&countoer);m=tcounter.

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

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

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

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

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