《武汉理工大学算法设计实验报告书》由会员分享，可在线阅读，更多相关《武汉理工大学算法设计实验报告书（12页珍藏版）》请在金锄头文库上搜索。
1、学生学号实验课成绩武汉理工大学学生实验报告书实验课程名称算法设计与分析开课学院计算机科学与技术学院指导老师姓名何九周学生姓名 学生专业班级软件0802班2010 2011学年 第一学期实验项目名称分治法应用及设计实验成绩实验者专业班级组别同组者实验日期年 月 日第一部分：实验分析与设计（可加页）、实验内容描述（问题域描述）1. 利用分治法，写一个二分检索的递归算法，并利用任何一种语言，在计算机上实现， 同时进行时间复杂性分析。2. 要求用递归方法实现、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或 者算法描述）int besearch（int n,int m,i
2、nt c,int *source） if（第n个点大于第m个点的值）return 失败；h=n与m的中点if（h的值等于目标）return h;if（h的值小于目标）return besearch（n,h-1,c,source）;/在 n 至 h-1 找elsereturn besearch（h+1,m,c,source）; /在 h+1 至 m 找、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）调试方法：直接在函数体内定义测试，负责初始化查找的有序表。1. 没有设定好中值点，忘记在两个端点的差值上增加左边端点的内容。2. 递归调用时，错误使用了边界条件，导致结
3、果不正确，应该是n - h-1和h+1 - m、实验结果及分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）实验结果:查找均为正确结果。时间复杂度：O（nlogn）空间复杂度：无需大量增加空间，仍为O（n）算法总结：算法效率很高，但是采用递归调用使得数据入栈出栈，开销稍大。三、实验小结、建议及体会经过实际动手操作，我掌握了采用分治法的2分检索算法，实际书写中出现了很多开始 没有想到的问题。认识到了自己的不足。实验项目名称分治法应用及设计实验成绩实验者专业班级组别同组者实验日期年 月 日第一部分：实验分析与设计（可加页）、实验内容描述（问题域描述）用分治法，实现对n个元素进行排序
4、的算法，并进行时间复杂性分析。要求用非递归方式实现。二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或 者算法描述）int Partition（int r , int first, int end）当ij时循环以下：当 ij 且 ri=rj时j如果ijI处的值存为j处的值，并且保存i处的值I+当 ij 且 ri=rj时i+；如果ijJ处的值保存为i处的值，同时i处的值保存为之前保存的值J+返回中点位置三、主要仪器设备及耗材一、调试过程(包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等)调试方法：直接在函数体内定义测试，负责初始化分治法排序的列表
5、1. 对于算法没有理解透彻，没有用好边界条件。2. 对于算法的交换应该是首先保存旧值，在第一次也就是从右侧开始时把右侧的值传 至左侧，把左侧的值保存，用来给从左侧开始进行的查找。二、实验结果及分析(包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等) 实验结果如下：c* D:AmaDsuanFaDebugsuanFa.eKe1020 210 120 31 13 41 14 51 15 20113 14 15 20 31 41 51 120 201 210 Press any key to continue.可以得知算法正确的进行了执行。时间复杂度：最好：O(n)平均：O(nlog2n)
6、最差：O(n2)空间复杂度：O(n)算法总结：快速排序按照记录的值对序列进行划分。时间复杂度相差很大，比较依赖于输 入。三、实验小结、建议及体会对于动态规划算法有了较深的体会，熟练掌握了算法的实现过程。实验项目名称动态规划算法应用及设计实验成绩实验者专业班级组别同组者实验日期年 月 日第一部分：实验分析与设计（可加页）一、实验内容描述（问题域描述）利用动态规划思想，求货郎担问题，并利用任何一种语言，在计算机上实现，同时进行时 间复杂性分析。要求对算法的时间复杂性进行分析二、基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算 法描述）1. for (i=1; in;
7、i+)/初始化第 0 列di0=ci0;2. for (j=1; j2n-1-1; j+)for (i=1; in; i+)/依次进行第i次迭代if (子集Vj中不包含i)对 Vj中的每个元素 k，计算 dij=min(cik+dkj-1);3. 对 V2n-1-1中的每一个元素 k，计算 d02n-1-1=min(c0k+dk2n-1-2);4. 输出最短路径长度d02n-1-1;三、主要仪器设备及耗材VISUAL C+,XP 系统一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）调试方法：直接在函数体内定义测试，负责初始化分治法排序的列表1. 对于书上的算法
8、了解不详细，出现很多错误，花费了大量的时间。2. 对于TSP算法的整个流程没有清晰的认识，只能对照着算法进行编程，没有理解真 正算法的意义。、实验结果及分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）。土 D:AmaosuanFaDebugtsp.eMe4ge+e1) 输入点。到【的距离：3 输入点。到的距离：6 输入点0到3的距离：7 输入点【到的距离：5 输入点【到N的距离：2 输入点】到3的距离：3 输入点N到口的距离：6 输入点N到1的距离：4 输入点N到3的距离：2 输入点弓到口的距离：3 输入点3到1的距离：7 输入点3到N的距离：5 the shortest w
9、ay:10c：， D:AmaosuanFaDebugtsp.eMe5输入点。到【的距离：4 输入点。到2的距离：3 输入点。到3的距离：2 输入点。到4的距离：1 输入点1到。的距离：2 输入点【到2的距离：3 输入点【到3的距离：4 输入点】到4的距离：5 输入点N到口的距离：34 输入点N到1的距离：3 输入点N到3的距离：2 输入点N到4的距离：1 输入点S到0的距离：2 输入点3到【的距离：3 输入点3到N的距离：4 输入点3到4的距离：5 输入点4到口的距离：6 输入点4到1的距离：4 输入点4到N的距离：3 输入点4到3的距离：2 the shortest way:100 Pres
10、s any key to continue时间复杂度：O(2n)空间复杂度：算法总结：相比于蛮力法相比，将复杂度O(n!)降低为指数时间解决的问题。三、实验小结、建议及体会经过这次实验，我对动态规划算法有了初步的认识，觉得自己对于细节的理解还是不 够，导致了很多错误，需要加强。实验项目名称动态规划算法应用及设计实验成绩实验者专业班级组别同组者实验日期年 月 日第一部分：实验分析与设计（可加页）、实验内容描述（问题域描述）已知资金总数为a （万元），工程数n,以及利润值g（i,j）（表示对工程i投资j万元所获 得的利润，其中1 i n,0 j 0; i）if （VijVi-1j） xi=1;j=
11、j-wi;else xi=0;5. VnC就是最终结果，xi！ =0的点就是需要投资的项目.三、主要仪器设备及耗材VISUAL C+， Window xp一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等） 调试方法：手动运行，查看变量的改变情况。错误：算法中给出的n并不对应，有误导的作用，在实际编写代码的时候应该注意vn 和wn中的n于之前的n和i等不匹配，需要增加1才行。输出结果总为负值，在边界出错，应该是=而不是。、实验结果及分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）g D:Ama05uanfaDebugasdf.ewe输入资金总数：
12、10输入工程数：3输入工程【所需的金额:1输入工程】可以得到的利润：2输入工程2所需的金额：3输入工程2可以得到的利润：5输入工程3所需的金额：2输入工程3可以得到的利润：4最大投资利润为：11路径 23Press any key to continue。:i D:AmaosuanFaDebugasdF.eHe输入资金总数：20输入工程数：5输入工程【所需的金额:10输入工程】可以得到的利润：20输入工程N所需的金额：3输入工程N可以得到的利润：18输入工程3所需的金额：S输入工程m可以得到的利润：31输入工程4所需的金额：S输入工程4可以得到的利润：12输入工程5所需的金额:4输入工程S可以
13、得到的利润：21最大投资利润为：70路径N35Press any key to continueg D:ama osuanFaDebu gas(lF.e he”输入资金总教：15输入工程数：4输入工程1所需的金额：8输入工程可以得到的利润：U输入工程2所需的金额：7输入工程2可以得到的利润：口输入工程3所需的金额：12输入工程3可以得到的利润：B输入工程4所需的金额：5输入工程4可以得到的利润：7最大投资利润为：25路筏ZL1Press any key to continue.算法时间复杂度为：O(nXC)空间复杂度同样为O(nXC)可以这个算法可以看作是决策一个序列(x1, x2,，xn)，对任一变量xi的决 策是决定xi=1还是xi=0。在对xi-1决策后，已确定了 (x1,，xi-1),在决 策xi时，问题处于下列两种状态之一：(1) 资金不允许投资工程i,则xi=0,投资不增加价值；(2) 资金允许投资工程匚则xi=1，投资的价值增加了 vi。所以可以得到递推公式：v(k, 0) = v(0, money) = 0v(k,money)-v(
