算法设计与分析实验报告

本科实验报告课程名称：算法设计与分析实验项目：递归与分治算法实验地点：计算机系实验楼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位是01。两位是00011110。三位是000001011010110111101100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。3．代码设计：#includecstdio#includeiostream#includecstring#includevectorusingnamespacestd;//求格雷码递推式子：G(n-1)=B(n-1)G(i)=B(i+1)异或B(i)(0in-2)//输出n位GRad码---普通方法vectorstringMy_grad;voidget_grad(intn){//cout1endl;My_grad.push_back(0);My_grad.push_back(1);//前面两位if(n1){//cout1endl;for(inti=2;i=n;i++){vectorstringtmp;for(intj=0;jMy_grad.size();j++){tmp.push_back(My_grad[j]);strings=0;s+=tmp[j];My_grad[j]=s;//}//翻转for(intj=tmp.size()-1;j=0;j--){strings=1;s+=tmp[j];My_grad.push_back(s);}}}}intmain(){intn;while(cinn){get_grad(n);for(inti=0;iMy_grad.size();i++)coutMy_grad[i]endl;My_grad.clear();}return0;}运行结果：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）贪心算法（GreedyApproach）能得到问题的最优解，要证明我们所做的第一步选择一定包含着一个最优解，即存在一个最优解的第一步是从我们的贪心选择开始。（2）在做出第一步贪心选择后，剩下的子问题应该是和原问题类似的规模较小的子问题，为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。2.4实验题目1．上机题目：最小延迟调度问题给定等待服务的客户集合A={1,2,…,n}，预计对客户i的服务时长为ti0，T=(t1,t2,…,tn)，客户i希望的服务完成时刻为di0，D=(d1,d2,…,dn)；一个调度f:A→N，f(i)为客户i的开始时刻。如果对客户i的服务在di之前结束，那么对客户i的服务没有延迟，即如果在di之后结束，那么这个服务就被延迟了，延迟的时间等于该服务的实际完成时刻f(i)+ti减去预期结束时刻di。一个调度f的最大延迟是所有客户延迟时长的最大值maxi∈A{f(i)+tidi}。附图2所示是不同调度下的最大延迟。使用贪心策略找出一个调度使得最大延迟达到最小。2．设计思想：贪心思想，按照他们的截止时间从小到大排序，如果截止时间相同按照花费时间从小到大排序。然后按照f_min（所有客户延迟时长的最大值）=max(works[i].cost+time-works[i].deadline,f_min);寻找最所有客户延迟时长的最大值。3．代码设计：//最小延迟调度问题//输入包含：任务，任务完成需要的时间，完成改任务的截止时间#includeiostream#includecstdio#includecmath#includealgorithmusingnamespacestd;constintmaxn=1000+10;intn;structnode{intid;intcost;intdeadline;}works[maxn];boolcmp(nodea,nodeb){if(a.deadline!=b.deadline)returna.deadlineb.deadline;elsereturna.costb.cost;}intdp[maxn][maxn];intmain(){while(scanf(%d,&n)!=EOF){for(inti=0;in;i++)scanf(%d,&works[i].cost);for(inti=0;in;i++)scanf(%d,&works[i].deadline),works[i].id=i+1;sort(works,works+n,cmp);intf_min=0;inttime=0;for(inti=0;in;i++){//if(works[i].cost+timeworks[i].deadline)f_min=max(works[i].cost+time-works[i].deadline,f_min);//coutf_minendl;time+=works[i].cost;}printf(Maximumdelay:\n);printf(%d\n,f_min);printf(Completetheorderoftasks:\n);for(inti=0;in;i++)coutworks[i].id;coutendl;}return0;}/*样例输入：55841031012151120*/运行结果：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实验原理动态规划（DynamicProgramming）算法思想：把待求解问题分解成若干个子问题，先求解子问题，然后由这些子问题的解得到原问题的解。动态规划求解过的子问题的结果会被保留下来，不像递归那样每个子问题的求解都要从头开始反复求解。动态规划求解问题的关键在于获得各个阶段子问题的递推关系式：（1）分析原问题的最优解性质，刻画其结构特征；（2）递归定义最优值；（3）自底向上（由后向前）的方式计算最优值；（4）根据计算最优值时得到的信息，构造一个最优解。3.4实验题目1．上机题目：最大子段和问题给定n个整数（可以为负数）组成的序列(a1,a2,…,an)，使用动态规划思想求该序列的子段和的最大值。注：当所有整数均为负整数时，其最大子段和为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．代码设计#includeiostream#includecstdio#includecmath#includecstringusingnamespacestd;constintmaxn=1000+10;intdp[maxn];inta[maxn];//动态规划思想：dp[i],表示到当前i的最大字段和为多少，而他的字段和时要不就是前面的最大字段和加上本身的数值要不就是自身的数值//dp[i]=max(dp[i],dp[i-1]+a[