算法设计与分析实验报告

本科生实验报告课程名称：算法设计与分析实验项目：递归和分治算法实验地点：计算机系实验楼110专业课：物联网1601学生。2016002105学生姓名：于指导员：郝晓丽2018年5月4日实验1递归和分治算法1.1实验目的和要求1.进一步熟悉C/C语言的集成开发环境；2.通过本实验加深对递归和分治策略的理解和应用。1.2实验课时2小时1.3实验原理分而治之的思想是将一个规模为n的复杂问题的解分成几个规模小于n的子问题，然后将子问题的解组合成原问题的解。应该注意的是分治法使用递归。分割后的每个子问题与原问题具有相同的性质，可以用相同的方法求解。最后，当子问题的规模足够小时，子问题可以直接求解，然后原问题可以反过来求解。1.4实验主题1.计算机主题：格雷码构造格雷码是长度为2n的序列。序列没有相同的元素，每个元素是一个长度为n的字符串，相邻的元素正好有一位不同。尝试设计一个算法来为任何n(分而治之，减少和改变)构造相应的格雷码。对于给定的正整数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位的两倍。N-1位前有0，N-2位反相后有1。3.代码设计：#包括#包括#包括#包括使用命名空间标准；/找到格雷码的递归公式：G(n-1)=B(n-1) G(i)=B(i 1)异或B(I)(0my _ gray；void get_grad(int n)/cout11)/cout 1 tmp；对于(int j=0；j=0；j -)字符串s= 1s=tmpj；我的毕业论文。int main()int n；同时(cinn)get _ grad(n)；对于(int I=0；I0，t=(t1，T2，TN)，客户I期望的服务完成时间是di0，d=(D2 D1，dn)；时间表f:AN，f(i)是客户I的开始时间。如果客户I的服务在di之前结束，则客户I的服务没有延迟，即如果在di之后结束，则服务延迟的时间等于实际完成时间f(i) ti减去服务的预期完成时间di。计划的最大延迟是所有客户延迟周期的最大值。图2显示了不同调度下的最大延迟。使用贪婪策略找到一个时间表，以最小化最大延迟。2.设计理念：贪婪的思想，按照自己的期限从小到大，如果期限是一样的，按照时间从小到大。然后，根据f_min(所有客户延迟时间的最大值)=max(工作1)。一世。截止日期，f _ min)；找出所有客户的最大延迟时间。3.代码设计：/最小延迟调度问题/输入内容包括：任务、完成任务所需时间、完成修改任务的截止时间#包括#包括#包括#包括使用命名空间标准；常量int maxn=1000 10int n；结构节点int id。内部成本；int截止日期；马克斯作品】；bool cmp(节点a，节点b)如果(a .截止日期！b .截