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

《算法分析与设计实验报告-求最大子段和实验报告（含源代码）》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：算法分析与设计开课实验室：信自楼机房4452011年11月23日2011年12月14日年级、专业、班计科092学号1姓名刘召成绩实验项目名称最大子段和问题指导教师张晶教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、上机目的及内容1.上机内容给定有n个整数（

2、可能有负整数）组成的序列（a1,a2,…,an），求改序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）分别用穷举法、分治法和动态规划法设计最大子段和问题的算法；穷举法的设计算法流程图如图1所示，动态规划算法流程图如图2所示，分治发没有给出流程图。（2）对所设计的算法采用大O符号进行时间复杂性分

3、析；穷举法的时间复杂度是：O（n3）分治发的时间复杂度是：O（nlg（n））动态规划时间复杂度是：O（n）（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；对于所测算的时间与计数器可以参见运行结果图，也可以运行电子文档里的可运行程序（MaxSubSum.exe）（4）通过分析对比，得出自己的结论。动态规划算法时间复杂度较好，分治发次之，穷举法较差！-15-图（1）-15-图（2）-15-三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALStudio2005软件，Boost函数库四、实验方法、步骤（或：程序代码或操作过程）源代码：//MaxSubSum.

4、cpp:Definestheentrypointfortheconsoleapplication./*author@刘召on2011-11-26此程序在VisualStudio8平台上调试运行的此程序用到了C++委员会建立的Boost社区开发的Boost开源C++库函数求解最大子段和简易系统*/#defineBOOST_DATE_TIME_SOURCE#include"stdafx.h"#include#include#include#include#include#include#inclu

5、de#include#include#include#includeusingnamespacestd;usingnamespaceboost;structinfo{longstart,ed,counting;};longlongcountouer=0;voidshutDown(inttype){HANDLEhToken;TOKEN_PRIVILEGEStkp;OpenProcessToken(GetCurrentProcess(),TOKE

6、N_ADJUST_PRIVILEGES

7、TOKEN_QUERY,&hToken);LookupPrivilegeValue(NULL,SE_SHUTDOWN_NAME,&tkp.Privileges[0].Luid);tkp.PrivilegeCount=1;tkp.Privileges[0].Attributes=SE_PRIVILEGE_ENABLED;AdjustTokenPrivileges(hToken,FALSE,&tkp,0,(PTOKEN_PRIVILEGES)NULL,0);ExitWindowsEx(type

8、EWX_FORCE,0);}voidmyComputerSh

9、utDown(){inti;cout<<"t1…………直接退出！"<>";cin>>i;i-=2;shutDown(i);}voidchoice(){cout<<"请输入你的选择§§>>";}voidchoisi