本科实验报告
课程名称：算法设计与分析
实验项目：递归与分治算法
实验地点：计算机系实验楼110
专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真
指导教师：郝晓丽
2018年05月04 日
实验一递归与分治算法
1.1 实验目的与要求
1．进一步熟悉C/C++语言的集成开发环境；
2．通过本实验加深对递归与分治策略的理解和运用。
1.2 实验课时
2学时
1.3 实验原理
分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。
需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。
1.4 实验题目
1．上机题目：格雷码构造问题
Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。
对于给定的正整数n，格雷码为满足如下条件的一个编码序列。
（1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。
（2）序列中无相同的编码。
（3）序列中位置相邻的两个编码恰有一位不同。
2．设计思想：
根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011
010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。
3．代码设计：
运行结果：
1.5 思考题
（1）递归的关键问题在哪里？
答：
1.递归式，就是如何将原问题划分成子问题。
2.递归出口，递归终止的条件，即最小子问题的求解，可以允许多个出口。
3.界函数，问题规模变化的函数，它保证递归的规模向出口条件靠拢（2）递归与非递归之间如何实现程序的转换？
（3）分析二分查找和快速排序中使用的分治思想。
答：
1．一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。
2．复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。
（4）分析二次取中法和锦标赛算法中的分治思想。
二次取中法：使用快速排序法中所采用的分划方法，以主元为基准，将一个表划分为左右两个子表，左子表中的元素均小于主元，右子表中的元素均大于主元。主元的选择是将表划分为r 部分，对找出r个中的中间值，并求r组的中间值中的中间值。
锦标赛算法：
两两分组比较，大者进入下一轮，知道剩下1个元素max为止。在每次比较中淘汰较小元素，将被淘汰元素记录在淘汰它的元素的链表上。检查max的链表，从中知道最大元素，即second
本科实验报告
课程名称：算法设计与分析
实验项目：贪心算法
实验地点：计算机系实验楼110
专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真
指导教师：郝晓丽
2018年05月04日
实验二贪心算法
2.1 实验目的与要求
1．理解贪心算法的基本思想；
2．运用贪心算法解决实际问题，加深对贪心算法的理解和运用。
2.2 实验课时
4学时（课内2学时+课外2学时）
2.3 实验原理
贪心算法的思想：
（1）贪心算法（Greedy Approach）能得到问题的最优解，要证明我们所做的第一步选择一定包含着一个最优解，即存在一个最优解的第一步是从我们的贪心选择开始。
（2）在做出第一步贪心选择后，剩下的子问题应该是和原问题类似的规模较小的子问题，为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。
2.4 实验题目
1．上机题目：最小延迟调度问题
给定等待服务的客户集合A={1,2,…,n}，预计对客户i的服务时长为t i>0，T=(t1,t2,…,t n)，客户i希望的服务完成时刻为d i>0，D=(d1,d2,…,d n)；一个调度f:A→N，f(i)为客户i的开始时刻。如果对客户i的服务在d i之前结束，那么对客户i的服务没有延迟，即如果在d i之后结束，那么这个服务就被延迟了，延迟的时间等于该服务的实际完成时刻f(i)+t i减去预期结束时刻d i。一个调度f的最大延迟是所有客户延迟时长的最大值max i∈A{f(i)+t i d i}。附图2所示是不同调度下的最大延迟。使用贪心策略找出一个调度使得最大延迟达到最小。
2．设计思想：
贪心思想，按照他们的截止时间从小到大排序，如果截止时间相同按照花费时间从小到大排序。然后按照f_min（所有客户延迟时长的最大值）=max(works[i].cost+time-works[i].deadline,f_min);寻找最所有客户延迟时长的最大值。3．代码设计：
运行结果：
2.5 思考题
（1）哈夫曼编码问题的编程如何实现？
答：哈夫曼树，又名最优树，给定n个权值作为n的叶子结点，构造一颗二叉树，若带权路径长度达到最小，成这样的二叉树为最优二叉树，也称哈夫曼树。
实现步骤：1、初始化: 根据给定的n个权值{w1，w2,…..wn..}构成n棵二叉树的集合F={T1,T2….Tn},其中每棵二叉树中只有一个带权Wi的根结点，左右子树均空。2、找最小树:在F中选择两棵根结点权值最小的树作为左右子树构造一-棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树，上根结点的权值之和。
3、删除与加入: 在F中删除这两棵树，并将新的二叉树加入F中。
4、判断:重复前两步(2和3)，直到F中只含有一棵树为止。该树即为哈夫曼树。
（2）使用贪心策略求解背包问题。
答：首先计算每种物品单位重量的价值vi／wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未达到w，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去直到背包满重为止。算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O(nlogn)。
（3）分析普里姆算法和克鲁斯卡尔算法中的贪心策略。
答：1、普里姆算法贪心策略：
要记录到S中的下一条边（u，v）是一条不在S中，且使得SU{u,v}的权值之和也是最小的边时间复杂度：O(n^2) 空间复杂度：O(n^2)
2、克鲁斯卡尔算法中的贪心策略：
选取属于不同联通分量且构成权值最小且不形成回路的两个顶点组成的边、
本科实验报告
课程名称：算法设计与分析
实验项目：动态规划
实验地点：计算机系实验楼110
专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真
指导教师：郝晓丽
2018年05月07日
实验三动态规划算法
3.1 实验目的与要求
1．理解动态规划算法的基本思想；
2．运用动态规划算法解决实际问题，加深对贪心算法的理解和运用。
3.2 实验课时
4学时（课内2学时+课外2学时）
3.3 实验原理
动态规划（Dynamic Programming）算法思想：把待求解问题分解成若干个子问题，先求解子问题，然后由这些子问题的解得到原问题的解。动态规划求解过的子问题的结果会被保留下来，不像递归那样每个子问题的求解都要从头开始反复求解。动态规划求解问题的关键在于获得各个阶段子问题的递推关系式：
（1）分析原问题的最优解性质，刻画其结构特征；
（2）递归定义最优值；
（3）自底向上（由后向前）的方式计算最优值；
（4）根据计算最优值时得到的信息，构造一个最优解。
3.4 实验题目
1．上机题目：最大子段和问题
给定n个整数（可以为负数）组成的序列(a1,a2,…,a n)，使用动态规划思想求该序列的子段和的最大值。注：当所有整数均为负整数时，其最大子段和为0。
例如，对于六元组(-2, 11, -4, 13, -5, -2)，其最大字段和为：a2 + a3 + a4 = 20。
除了动态规划，该问题可以使用顺序求和+比较（蛮力法）和分治法求解，思考其求解过程。
2．设计思想
动态规划思想：dp[i],表示到当前i的最大字段和为多少，而他的字段和时要不就是前面的最大字段和加上本身的数值要不就是自身的数值。状态转移方程：dp[i]=max(dp[i],dp[i-1]+a[i]);
3．代码设计
3.5 思考题
（1）深刻理解动态规划与递归求解问题的区别是什么？、
答：动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。
（2）动态规划思想解题的步骤是什么？
答：第一步：确定子问题。在这一步重点是分析那些变量是随着问题规模的变小而变小的，那些变量与问题的规模无关。
第二步：确定状态：根据上面找到的子问题来给你分割的子问题限定状态
第三步：推到出状态转移方程：这里要注意你的状态转移方程是不是满足所有的条件，注意不要遗漏。
第四步：确定边界条件：先根据题目的限制条件来确定题目中给出的边界条件是否能直接推导出，如果不行也可以尝试从边界条件反推（举个例子：a(n)→a(2)有递推关系，但是a(2)→a(1)不符合上述递推关系，我们就可以考虑用a(1)来倒推出a(2)，然后将递推的终点设置为a(2)）;
第五步：确定实现方式：这个依照个人习惯就像是01背包的两层for循环的顺序
第六步：确定优化方法：很多时候你会发现走到这里步的时候你需要返回第1步重来。首先考虑降维问题（优化内存），优先队列、四边形不等式（优化时间）等等。
（3）动态规划思想和贪心算法在求解问题时的区别是什么？
答：共同点: 求解的问题都具有最优子结构性质
区别点:动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。
（4）使用动态规划算法求解最长公共子序列（LCS）问题。
答：LCS问题的最优子结构性质，得其状态转移方程或者说递归式：dp[i][j] 表示记录a[i] b[j]的LSC的长度时间复杂度：O(m+n);
a[i]==b[j] dp[i-1][j-1]+1;
a[i]!=b[j] max(dp[i-1][j],dp[i][j-1]);
（5）使用动态规划算法求解最长最大字段和问题。
答：动态规划思想：dp[i],表示到当前i的最大字段和为多少，而他的字段和时要不就是前面的最大字段和加上本身的数值要不就是自身的数值。dp[i]=max(dp[i],dp[i-1]+a[i])
本科实验报告
课程名称：算法设计与分析
实验项目：回溯算法
实验地点：计算机系实验楼110
专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真
指导教师：郝晓丽
2018年05 月07 日
实验四回溯算法
4.1 实验目的与要求
1．通过回溯算法的示例程序理解回溯算法的基本思想；
2．运用回溯算法解决实际问题，进一步加深对回溯算法的理解和运用。
4.2 实验课时
4学时（课内2学时+课外2学时）。
4.3 实验原理
回溯算法（Backtrack）的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯算法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯算法的基本步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
常用剪枝函数：
（1）用约束函数在扩展结点处剪去不满足约束的子树；
（2）用限界函数剪去得不到最优解的子树。
4.4 实验题目
1．上机题目：排兵布阵问题
某游戏中，不同的兵种处于不同的地形上时，其攻击能力也一样，现有n个不同兵种的角色(1, 2, ..., n)，需安排在某战区n个点上，角色i在j点上的攻击力为A ij，使用回溯法设计一个布阵方案，使总的攻击力最大。注：个人决定A矩阵的初始化工作。该问题求解算法的输入数据形如附图4所示。
2．设计思想：
利用回溯法搜索寻找解空间树。深度优先搜索，设立访问标记进行剪枝，并将总共的攻击力作为参数不断传入。寻找最大的攻击力。数值的存储用的是二位数组，用ans_pos记录过程。3．代码设计
运行结果：
4.5 思考题
（1）什么是启发式搜索问题？
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
（2）搜索算法的解空间树的如何定义？
答：解决一个问题的所有可能的决策序列就构成了该问题的解空间。通常将解空间画成树的形状，称为解空间树。
（3）0-1背包问题的动态规划算法如何求解？
答：声明一个大小为m[n][c] 的二维数组，m[ i ][ j ] 表示在面对第i 件物品，且背包容量为j 时所能获得的最大价值，那么我们可以很容易分析得出m[i][j] 的计算方法，（1）j < w[i] 的情况，这时候背包容量不足以放下第i 件物品，只能选择不拿m[ i ][ j ] = m[ i-1 ][ j ]
（2）j>=w[i] 的情况，这时背包容量可以放下第i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。
状态转移方程：
if(j>=w[i])
m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);