武汉理工大学算法设计实验报告书Word文档下载推荐.docx
《武汉理工大学算法设计实验报告书Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《武汉理工大学算法设计实验报告书Word文档下载推荐.docx（11页珍藏版）》请在冰点文库上搜索。
实验成绩
实验者
专业班级
组别
同组者
实验日期
年月日
第一部分：
实验分析与设计（可加页）
一、实验内容描述（问题域描述）
1.利用分治法，写一个二分检索的递归算法，并利用任何一种语言，在计算机上实现，同时进行时间复杂性分析。
2.要求用递归方法实现
二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）
intbesearch（intn,intm,intc,int*source）{
if（第n个点大于第m个点的值）
return失败;
h=n与m的中点
if（h的值等于目标）
returnh;
if（h的值小于目标）
returnbesearch（n,h-1,c,source）;
//在n至h-1找
else
returnbesearch（h+1,m,c,source）;
//在h+1至m找
}
三、主要仪器设备及耗材
VisualC++,WindowsXp
第二部分：
实验调试与结果分析（可加页）
一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）
调试方法：
直接在函数体内定义测试，负责初始化查找的有序表。
1.没有设定好中值点，忘记在两个端点的差值上增加左边端点的内容。
2.递归调用时，错误使用了边界条件，导致结果不正确，应该是n–h-1和h+1-m
二、实验结果及分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）
实验结果：
查找均为正确结果。
时间复杂度：
O（nlogn）
空间复杂度：
无需大量增加空间，仍为O（n）
算法总结：
算法效率很高，但是采用递归调用使得数据入栈出栈，开销稍大。
三、实验小结、建议及体会
经过实际动手操作，我掌握了采用分治法的2分检索算法，实际书写中出现了很多开始没有想到的问题。
认识到了自己的不足。
用分治法，实现对n个元素进行排序的算法，并进行时间复杂性分析。
要求用非递归方式实现。
intPartition（intr[],intfirst,intend）
{
当i<
j时循环以下：
当i<
j且r[i]<
=r[j]时{
j—
}
如果i<
j
I处的值存为j处的值，并且保存i处的值
I++
i++；
如果i<
J处的值保存为i处的值，同时i处的值保存为之前保存的值
J++
返回中点位置
VISUALC++6.0XP系统
直接在函数体内定义测试，负责初始化分治法排序的列表
1.对于算法没有理解透彻，没有用好边界条件。
2.对于算法的交换应该是首先保存旧值，在第一次也就是从右侧开始时把右侧的值传至左侧，把左侧的值保存，用来给从左侧开始进行的查找。
实验结果如下：
可以得知算法正确的进行了执行。
最好：
O（n）
平均：
O（nlog2n）
最差：
O（n2）
快速排序按照记录的值对序列进行划分。
时间复杂度相差很大，比较依赖于输入。
对于动态规划算法有了较深的体会，熟练掌握了算法的实现过程。
算法设计与分析_
动态规划算法应用及设计
一、实验内容描述（问题域描述）
利用动态规划思想，求货郎担问题，并利用任何一种语言，在计算机上实现，同时进行时间复杂性分析。
要求对算法的时间复杂性进行分析
二、基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）
1．for（i=1;
i<
n;
i++）//初始化第0列
d[i][0]=c[i][0];
2．for（j=1;
j<
2n-1-1;
j++）
for（i=1;
i++）//依次进行第i次迭代
if（子集V[j]中不包含i）
对V[j]中的每个元素k，计算d[i][j]=min（c[i][k]+d[k][j-1]）;
3．对V[2n-1-1]中的每一个元素k，计算d[0][2n-1-1]=min（c[0][k]+d[k][2n-1-2]）;
4．输出最短路径长度d[0][2n-1-1];
VISUALC++,XP系统
调试方法：
1.对于书上的算法了解不详细，出现很多错误，花费了大量的时间。
2.对于TSP算法的整个流程没有清晰的认识，只能对照着算法进行编程，没有理解真正算法的意义。
O（2n）
空间复杂度:
相比于蛮力法相比，将复杂度O（n!
）降低为指数时间解决的问题。
三、实验小结、建议及体会
经过这次实验，我对动态规划算法有了初步的认识，觉得自己对于细节的理解还是不够，导致了很多错误，需要加强。
已知资金总数为a（万元）,工程数n，以及利润值g（i,j）（表示对工程i投资j万元所获得的利润，其中
，且j只取整数），试用动态规划方法求出如何分配资金才能使获得的利润最大（资金的分配以万元为单位）。
二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）
1.初始化第0列
2.初始化第0行
3.计算第i行，进行第i次迭代
当j小于项目的投资时
V[i][j]=V[i-1][j];
否则
V[i][j]=为（V[i-1][j],V[i-1][j-w[i]]+v[i]）较大者
4.求装入背包的物品
for（i=n;
i>
0;
i--）
if（V[i][j]>
V[i-1][j]）{
x[i]=1;
j=j-w[i];
elsex[i]=0;
5.V[n][C]就是最终结果，x[i]！
=0的点就是需要投资的项目.
VISUALC++，Windowxp
手动运行，查看变量的改变情况。
错误：
算法中给出的n并不对应，有误导的作用，在实际编写代码的时候应该注意v[n]和w[n]中的n于之前的n和i等不匹配，需要增加1才行。
输出结果总为负值，在边界出错，应该是<
=而不是<
。
算法时间复杂度为：
O（n×
C）
空间复杂度同样为O（n×
可以这个算法可以看作是决策一个序列（x1,x2,…,xn），对任一变量xi的决策是决定xi=1还是xi=0。
在对xi-1决策后，已确定了（x1,…,xi-1），在决策xi时，问题处于下列两种状态之一：
（1）资金不允许投资工程i，则xi=0，投资不增加价值；
（2）资金允许投资工程i，则xi=1，投资的价值增加了vi。
所以可以得到递推公式:
经过此次实验，我手动编写了一个动态规划解决问题的小程序，虽然过程很艰辛，但是对于课本知识的理解和动手能力的提高都有很大的帮助。
掌握了利用动态规划的方法解决背包问题，并能灵活的运用。
升级会员 