《算法分析与设计实验报告求最大子段和实验报告（含源代码）》由会员分享，可在线阅读，更多相关《算法分析与设计实验报告求最大子段和实验报告（含源代码）（15页珍藏版）》请在金锄头文库上搜索。
1、昆明理工大学信息工程与自动化学院学生实验报告（ 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.没有 教师签名： 年 月 日一、上机目的及内
2、容1.上机内容给定有n个整数（可能有负整数）组成的序列（a1,a2,an），求改序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）分别用穷举法、分治法和动态规划法设计最大子段和问题的算法；穷举法的设计算法流程图如图1所示，动态规划算法流程图如图2所示，分治发没有给出流程图。（2）对所设计的算法采用大
3、O符号进行时间复杂性分析；穷举法的时间复杂度是：O（n3）分治发的时间复杂度是：O（nlg（n）动态规划时间复杂度是：O（n）（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；对于所测算的时间与计数器可以参见运行结果图，也可以运行电子文档里的可运行程序（MaxSubSum.exe）（4）通过分析对比，得出自己的结论。动态规划算法时间复杂度较好，分治发次之，穷举法较差！图（1）图（2）三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUAL Studio2005软件，Boost函数库四、实验方法、步骤（或：程序代码或操作过程）源代码：/ MaxSubSum.cpp
4、 : 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 #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数据量较大，是否要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、系统数据！nendl;coutt1要输入任意个个数的数据！endl;coutt2要输入的数据个数已确定！endl;coutt3要随机产生一定个数的数据作为输入数据！k;if(k=1)while (i=1)cout请输入第leftsetw(3)hj;(*integerlist).push_back(j);+h;coutn1继续输入下一个数字！t2退出输入数据模块！i;else if (k=2)cout请输入你要输入的数据的个数:k;for (int i1=1;i1=k;i1+)cout请输入第leftsetw(3)i1j;(*integerlist).push_back(j); elsecout
9、请输入你要随机产生的数据的个数:k1;mt19937 wng(time(0);jk=abs(long(wng()/177)%1771;for(long i=0;i=jk;i+)ko=rand();ko=rand();coutn正在产生随机数据;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=输出随机产生的数据;choising(str);cinqw;if(qw=1)|(*integ
10、erlist).size()=6000)ofstream outData;outData.open(Random output numbers.txt);coutendlstr(*integerlist).size()个数字，他们是：500)coutmn;coutn第t*mn个数据到第i*mn个数据是：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();coutn第t*mn个数据到第c个数据是(按回车键以继续输出下面的数据）：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 co
