算法分析与设计实验报告求最大子段和实验报告（含源代码）

昆明理工大学信息工程与自动化学院学生实验报告（ 2011 2012 学年 第 1 学期 ）课程名称：算法分析与设计 开课实验室：信自楼机房445 2011 年11月 23日2011 年12月 14日年级、专业、班计科092学号200910405201姓名刘召成绩实验项目名称最大子段和问题指导教师 张晶教师评语该同学是否了解实验原理：A.了解B.基本了解C.不了解该同学的实验能力：A.强 B.中等 C.差 该同学的实验是否达到要求：A.达到B.基本达到C.未达到实验报告是否规范：A.规范B.基本规范C.不规范实验过程是否详细记录：A.详细B.一般 C.没有 教师签名： 年 月 日一、上机目的及内容1.上机内容给定有n个整数（可能有负整数）组成的序列（a1,a2,an），求改序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）分别用穷举法、分治法和动态规划法设计最大子段和问题的算法；穷举法的设计算法流程图如图1所示，动态规划算法流程图如图2所示，分治发没有给出流程图。（2）对所设计的算法采用大O符号进行时间复杂性分析；穷举法的时间复杂度是：O（n3）分治发的时间复杂度是：O（nlg（n）动态规划时间复杂度是：O（n）（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；对于所测算的时间与计数器可以参见运行结果图，也可以运行电子文档里的可运行程序（MaxSubSum.exe）（4）通过分析对比，得出自己的结论。动态规划算法时间复杂度较好，分治发次之，穷举法较差！图（1）图（2）三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUAL Studio2005软件，Boost函数库四、实验方法、步骤（或：程序代码或操作过程）源代码：/ MaxSubSum.cpp : Defines the entry point for the console application./*author刘召 on 2011-11-26此程序在Visual Studio 8平台上调试运行的此程序用到了C+委员会建立的Boost社区开发的Boost开源C+库函数求解最大子段和简易系统*/#define BOOST_DATE_TIME_SOURCE#include "stdafx.h"#include <iostream>#include <string>#include <vector>#include <ctime>#include <cmath>#include <fstream>#include <iomanip>#include <Windows.h>#include <boost/random.hpp>#include <boost/progress.hpp>#include <boost/timer.hpp>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.Privileges0.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; cout<<"t1直接退出！"<<endl; cout<<"t2注销计算机！"<<endl; cout<<"t3关闭计算机！"<<endl; cout<<"t4重启计算机！"<<endl; cout<<"请输入你的选择>>" cin>>i;i-=2; shutDown(i); void choice()cout<<"请输入你的选择>>"void choising(char* str)cout<<"n数据量较大，是否要"<<str<<"?这将会花很长时间！"<<endl;cout<<"1是t2否"<<endl;choice();void aLine(int k,char c);void inputTheNumberList(vector<long>*integerlist)long j,i=1,h=1,t=0,k;string str="你共输入"if(!(*integerlist).empty()(*integerlist).clear();cout<<endl<<right;cout<<setw(48)<<"初始化系统数据！n"<<endl;cout<<"t1要输入任意个个数的数据！"<<endl;cout<<"t2要输入的数据个数已确定！"<<endl;cout<<"t3要随机产生一定个数的数据作为输入数据！"<<endl;choice();cin>>k;if(k=1)while (i=1)cout<<"请输入第"<<left<<setw(3)<<h<<"个整数>>"<<flush;cin>>j;(*integerlist).push_back(j);+h;cout<<"n1继续输入下一个数字！t2退出输入数据模块！"<<endl;choice();cin>>i;else if (k=2)cout<<"请输入你要输入的数据的个数:"<<flush;cin>>k;for (int i1=1;i1<=k;i1+)cout<<"请输入第"<<left<<setw(3)<<i1<<"个整数>>"<<flush;cin>>j;(*integerlist).push_back(j); elsecout<<"请输入你要随机产生的数据的个数:"<<flush;long ko,mk,jk;long long k1;cin>>k1;mt19937 wng(time(0);jk=abs(long(wng()/177)%1771;for(long i=0;i<=jk;i+)ko=rand();ko=rand();cout<<"n正在产生随机数据"progress_display pg2(k1);mt19937 rng(rand();uniform_int<>ui(0,ko);while(k1) ko=ui(rng);pg2+;jk=ui(rng);mk=ui(rng);if(mk<0) mk=-mk;j=ui(rng);if (j%177)%2)j=jk-mk;else j=ko-mk*2;(*integerlist).push_back(j);k1-;str="随机产生了"aLine(79,$);int qw=0;if (*integerlist).size()>6000)char* str="输出随机产生的数据"choising(str);cin>>qw;if(qw=1)|(*integerlist).size()<=6000)ofstream outData;outData.open("Random output numbers.txt");cout<<endl<<str<<(*integerlist).size()<<"个数字，他们是："<<endl; long g=1;long long mn=500;if(*integerlist).size()>500)cout<<"n数据较多，请输入每次要显示的数据的个数："cin>>mn;cout<<"n第"<<t*mn<<"个数据到第"<<i*mn<<"个数据是："<<endl;cin.ignore(12,n);t+;i+;outData<<left<<"第"<<setw(4)<<1<<"行："for (long y=0;y<(*integerlist).size();y+) if(*integerlist).size()>mn)&&(g>mn)long long c=i*mn;if(i*mn>=(*integerlist).size() c=(*integerlist).size();cout<<"n第"<<t*mn<<"个数据到第"<<c<<"个数据是(按回车<Enter>键以继续输出下面的数据）："<<endl;cin.ignore(12,n);t+;i+;g=1;cout<<left;cout<<setw(16)<<(*integerlist)y;outData<<setw(16)<<(*integerlist)y;if(y+1)%5=0) outData<<endl<<"第"<<setw(4)<<y/5+2<<"行："g+;cout<<endl;aLine(80,$);outData.close();vector<info> directMethod(vector<long>intList,long long* counter)vector<info> textor;long countor=0,lisize=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(lisize>2940) 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 5: df=0.282;break;else if(lisize<12) 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(lisize<24) df=0.1964;else if(lisize<50) df=0.1864;else if(lisize<100) df=0.1764;cout<<"n正在用穷举法进行运算"progress_display pg3(kp*df);for (int i=0;i<lisize;i+)for (long j=i;j<lisize;j+)countor=0;for ( long k=j;k<lisize;k+)(*counter)+;countor+=intListk;if(lisize<=2940) pg3+;else if(pk<(*counter)*f)pg3+;pk+;if (countor>=textor0.counting)hhtt.counting=countor;hhtt.start=j;hhtt.ed=k;if (countor!=textor0.counting)textor.clear();textor.push_back(hhtt);elsebool t=true;for ( long p=0;p<textor.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;i<k;i+)cout<<c;void sho(vector<info> textor,vector< long>numList, long i,string str)cout<<"n由"<<str<<"得到最大字段和是："<<textori.counting<<endl;cout<<"相应的子段是从第"<<textori.start+1<<"个数字（"<<numListtextori.start<<"）到第"<<textori.ed+1<<"个数字（"<<numListtextori.ed<<"）"<<endl;cout<<"它们分别是："<<endl;int op,p=1;op=0;ofstream outData;outData.open("DirectMethod output Submax.txt");outData<<left<<"第"<<setw(4)<<p<<"行："for (long j=textori.start;j<=textori.ed;j+)cout<<left;cout<<setw(16)<<numListj;outData<<setw(16)<<numListj;op+;if(op%5=0) outData<<endl<<"第"<<setw(4)<<+p<<"行："cout<<endl;aLine(79,*);outData.close();void showTheMethodResult(vector<info> textor,vector< long>numList,string str)if (textor.size()=1)sho(textor,numList,0,str); elsecout<<"tt由"<<str<<"共得到"<<textor.size()<<"个这样的最大字段!它们分别是：n"<<endl;for ( long k=0;k<textor.size();k+)cout<<"第"<<k+1<<"组最大子段的信息："<<endl;sho(textor,numList,k,str);long SubDealMethod(vector< long>integerList,long long left,long long right)long sum;if (left=right)+countouer;if (integerListleft>0)sum=integerListleft; elsesum=0; elselong long center=(left+right)/2;long long leftSum=SubDealMethod(integerList,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 (aleft>s1) s1=aleft;+countouer;for (long long i=center+1;i<=right;i+)aright+=integerListi;if(aright>s2) s2=aright;+countouer;sum=s1+s2;if(sum<leftSum)sum=leftSum;if(sum<rightSum)sum=rightSum;return sum;long dynamicMethod(vector<long > integerList,long long *coutor)long sum=0,b=0;for (long i=0;i<integerList.size();i+)if (b>0)b+=integerListi; elseb=integerListi;if(b>sum) sum=b; (*coutor)+;return sum;void welcome()cout<<"n"<<setw(66)<<"欢迎使用求解最大子段和简易系统(Release 2.0)n"<<endl;cout<<"tttt学 校：昆明理工大学"<<endl;cout<<"tttt学 院：信息工程与自动化学院"<<endl;cout<<"tttt专 业：计算机科学与技术"<<endl;cout<<"tttt指导老师：张晶"<<endl;cout<<"tttt制 作 人：刘召"<<endl;cout<<"tttt学 号：200910405201"<<endl;cout<<"ttttQQ 邮箱：329245767n"<<endl;void exitSession()cout<<"n正在退出本系统，请稍后"progress_display p(1e9);for (long i=0;i<1e9;i+) p+;cout<<"n你已经成功退出本系统！n谢谢你的使用，再见！"<<endl;Sleep(1500);int main(int argc, char* argv) vector<long>integerList;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("动态规划法");system("color 4a");cout<<"n正在用动态规划法进行运算"tCounter.restart();result=dynamicMethod(integerList,&countoer);m=tCounter.elapsed();cout<<"n动态规划法运算所用时间为："cout<<m<<"秒n循环次数大约为："cout<<countoer<<"次n动态规划法运算的结果是："<<result<<endl;aLine(79,-);needKey("分治法");system("color 1c");cout<<"n正在用分治法进行运算(这可能需要几秒甚至几分钟)"tCounter.restart();result=SubDealMethod(integerList,0,integerList.size()-1);m=tCounter.elapsed();cout<<"n分治法运算所用时间为："cout<<m<<"秒n循环次数大约为："cout<<countouer<<"次n由分治法运算的结果是："cout<<result<<endl;aLine(79,-);countoer=0;short ip=0;if (integerList.size()>2940)char* str1="用穷举法进行运算"choising(str1);cin>>ip;if (integerList.size()<=2940)|(ip=1)needKey("穷举法");system("color c0");tCounter.restart();vector<info> mid=directMethod(integerList,&countoer);m=tCounter.elapsed();cout<<"n穷举法运算所用时间为："cout<<m<<"秒n循环次数大约为："cout<<countoer<<"次n由穷举法运算的结果是："<<endl;showTheMethodResult(mid,integerList,"穷举法"); cout<<"n1继续使用本系统，并求解下一组数据的最大子段和n"cout<<"2退出本系统n"countouer=0;choice();cin>>k;aLine(80,&);integerList.clear();myComputerShutDown();return 0;五、实验过程原始记录( 测试数据、图表、计算等) 图（3）手动输入5个数据：7、8、-16、12、3。用动态规划算法运行所得到的最大子段和是15；运行用时不足1毫秒，用计数器测得循环次数为5次！图（4）在图（4）中，对于图（3）中的5个数据，用分治发所得到的最大子段和是15，用计时器测得用时也不足1毫秒，用计数器测得循环17次。用穷举法（直接法）得到的最大子段和也是15，穷举法可以找到所有具有最大子段和的响应的子段，这5 个数据由两个最大子段；用计时器测得穷举法用时0.031秒，用计数器测得循环35次。由此可以看出，穷举法用时明显多于动态规划与分治发。图（5）由于动态规划与分治发时间复杂度较低，所以设置了可以自动随机产生数据的功能，对于随机产生大于6000个数据时，可以选择是否输出所产生的数据！这里随机产生了2940个数据，因为当随机产生的数据较多时，可能很耗时，所以设置了完成工作的进度显示功能；若要输出随机产生的数据，当产生的数据个数大于500时，可以选择每次输出的数据的个数，可以按回车键输出下面的数据！由于产生的数据较多，在这里只显示一部分。图（6）由于穷举法用时较长，所以为穷举法设置了完成作业的进度显示。运算随机产生的2940个数据，三种方法得到的最大子段和结果都是665。用计时器测得动态规划法用时0.015秒，用计数器测得循环了2940次。对于分治发，用计时器测得用时0.016秒，用计数器测得循环了37064次。对于穷举法，用计时器测得用时31.247秒，用计数器测得循环了4239686780次。显然，穷举法的性能较差，下面随机产生更多的数据继续比较动态规划法与分治发的性能。图（7）这次随机产生了五万个数据，由于数据量较大，选择了不输出随机产生的数据，由于五万个数据用穷举法将会要很长时间，这里跳过用穷举法进行运算，说明一下，当数据量超过2940个时，将会提示是否用穷举法进行运算，可以选择用或不用。用动态规划法对这50000个数据运算用时为0.016秒，循环次数为50000次。对于分治法，用计时器测得对这50000个数据运算用时为14.727秒，用计数器测得循环了834464次。由此可以看出，动态规划法性能优于分治法！若要得到更多的测试，可以运行电子版文档附带的运行程序（MaxSubSum.exe）。6、 实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）程序设计时，深刻体会到了动态规划法、分治法及穷举法的设计思想与方法。 由于所用到的计时器是Boost函数库里的Timer计时器，其在windows环境下最大精度为毫秒级，在Unix环境下最大精度为微妙级。而Boost里的Ptimer函数虽然经过“改装”可以在windows下达到微秒级，但遗憾的是，我配置的Boost函数库好像并不是很完美，对Date_time库支持的不是很好，还只能用Timer来计时。然而，动态规划法与分治法的时间性能较好，运行几百个数据可能都不用1毫秒，为免去输入数据的麻烦，也为更好地测试动态规划法与分治法的性能，就设计了随机产生数据的功能，一开始我用的是C函数库里的rand（）函数随机产生数据，但不久就发现rand（）产生的数据并不是真正的随机数据，例如，每次重新运行程序时，第一个数据总是41，以后的数据都与上一次运行程序时一样的序列产生。所以又用了Boost函数库里的random库函数，然后用时间作为产生随机数据的种子，这样每次重新运行程序就不会出现Rand（）那样的情况了，由于mt19937产生的数据较大（有6个数量级左右），在求最大子段和时，很可能产生数据溢出的现象，也不利于对数据的观看，所以又用rand（）限制了它产生数据的范围。在用穷举法时，所用的时间较多，所以就用Boost函数库里的progress_display函数为它设计了一个显示完成进度的功能。不过，由于不能准确计算得到所要运算的次数，所以进度显示设置可能会有误差，所以设置了一段代码，专用于调试设置的参数，显示进度的误差减小了许多，基本达到满意。然而，progress_display对传入的参数范围有一些限制，我发现，当传入参数大于2945的3次方时，会出现输出紊乱的现象，所以当输入的数据个数大于2940时，我用比例计算进行数据的平衡，以保证函数的正常运行；但是当产生多于2950个数据时，用穷举法运算将会很耗时，所以就设置了一些选择项，可以选择是否用穷举法运算。-15-