算法分析与设计大作业

算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。

2.程序：程序是算法⽤某种程序设计语⾔的具体实现。

⼆、简答题：1.算法需要满⾜哪些性质？简述之。

答：算法是若⼲指令的有穷序列，满⾜性质：（1）输⼊：有零个或多个外部量作为算法的输⼊。

（2）输出：算法产⽣⾄少⼀个量作为输出。

（3）确定性：组成算法的每条指令清晰、⽆歧义。

（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。

2.简要分析分治法能解决的问题具有的特征。

答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质；（3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。

3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。

答：将递归算法转化为⾮递归算法的⽅法主要有：（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。

该⽅法通⽤性强，但本质上还是递归，只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。

（2）⽤递推来实现递归函数。

（3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。

后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。

三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]交换a[j]、a[j+1]；分析该算法的时间复杂性。

答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。

（1）设⽐较⼀次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。

算法分析与设计大作业班级： 12信科姓名：郭倩南学号： 1242155105完成日期： 2015-6-4指导教师：陈平序号选定题目所用算法设计技术1数字三角形问题动态规划2集合划分问题分治法回溯法3求子集问题评分：大作业报告1、数字三角形问题一、问题描述对于给定的由n行数字组成的数字三角形，计算从三角形的底至顶的路径经过的数字和的最大值。

如：73 88 1 02 7 4 44 5 2 6 5二、实验内容与实验步骤实验内容:输入数据的第1 行是数字三角形的行数n，1<=n<=100。

接下来n行是数字三角形各行中的数字。

所有数字在0..99之间实验步骤:1、首先证明该问题满足最优化原理最优化原理：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。

简而言之，一个最优化策略的子策略总是最优的。

2、建立动态规划函数3、填表三、实验环境Window7系统，vc++6.0软件四、问题分析由观察数字三角形可知，从数字三角形的顶层出发，下一层选择向左还是向右取决于两个4层数字三角形的最大数字和，而对于第四层的决定取决于第三层的最大数字和，依次类推，可知该问题是多阶段决策最优化问题，并且划分出来的子问题是相互重叠的，所以该问题采用动态规划法解决动态规划：与分治法相似，把问题分解按层次分成子问题，直到可以直接求解的子问题，然后一级一级地向上求解。

与分治法的出别在于：动态规划适用有许多重复子问题出现的问题，它保存已求出问题的解。

73 8 3 88 1 0 8 1 1 02 7 4 4 2 7 4 7 4 4 4 5 2 6 5 4 5 2 6 5 2 6 5一个五层数字三角形子问题〔1〕子问题〔2〕五、问题解决〔1〕根据对问题的分析，写出解决方法。

1、证明：S,S1,S2,..Sn,t是从S到t的一条数字和最大的路径，从源点S开始，设从S到下一段的顶点S1已经求出，如此问题转化为求从S1到t的数字和最大的路径，显然S1，S2，...Sn,t一定构成一条从S1到t的数字和最大值的路径，如假如不然，设S1，r1,r2,....rq,t是一条数字和最大的路径，如此S,S1，r1,r2,....rq,t的路径经过数字和的最大值比S,S1，S2，...Sn,t的路径数字和更大，从而导致矛盾，所以数字三角形问题满足最优性原理。

课号：____CK5J08A ___ 课名：_____算法设计与分析______教师: ________________期末大作业要求：在以下几种方式中任选一种一．算法实际应用题任务要求：1．完成一个有一定实用性的程序，其中包含稍复杂的算法模块，算法输入和输出必须显示在图形界面上，最好能把算法运行过程展现在图形界面上。

2．撰写算法设计报告，描述算法设计流程，分析算法效率。

3．进行答辩。

评分标准：1．图形界面的操作方便性与对算法的展现程度(30分)2．算法的复杂程度和算法效率和实用性(30分)3．算法设计流程的解释的清晰度和算法效率分析的准确度(30分)4．答辩10分，采用教师提问学生回答和解释的形式，学生若不能自圆其说、对自己设计的算法流程也讲不清楚，则判定为抄袭，整个大作业为0分。

参考题目：1．算242．倒油3．趣味算式4．马步问题5．单源最短路径6．最小生成树7．工作分配8．2*2*2魔方9．长江游艇10．推箱子11．华容道12．文件搜索13．………..二．ACM算法设计题任务要求：1.完成2道及2道以上ACM算法设计题，题目由教师给定并公布在OJ系统中，学生限定时间内(2个小时)，在其中选做2题以上，正确性也由OJ系统判定，并参照OJ系统的标准，形成排名。

完成数量不到2题的，不管排名如何，整个大作业都判定为不及格。

2.为所完成的每道题目撰写解题报告，描述设计思路与流程，分析课号：____CK5J08A ___ 课名：_____算法设计与分析______教师: ________________程序的时空效率。

评分标准：1.算法设计能力(60分)，主要根据OJ系统中的排名来评定，部分提交的题目有抄袭嫌疑的学生，教师对其进行质询答辩，采用问答形式，学生若对其提交正确的任何题目，无法通过质询答辩，则判定为抄袭，整个大作业为0分。

2.算法表述与分析能力(40分)，根据提交的解题报告中，对算法流程的描述的清晰程度，对算法时空效率的分析的准确程度，进行评定。

《算法分析与设计》作业( 一)本课程作业由两部分组成。

第一部分为”客观题部分”, 由15个选择题组成, 每题1分, 共15分。

第二部分为”主观题部分”,由简答题和论述题组成, 共15分。

作业总分30分, 将作为平时成绩记入课程总成绩。

客观题部分:一、选择题( 每题1分, 共15题)1、递归算法: ( C )A、直接调用自身B、间接调用自身C、直接或间接调用自身 D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题, 这些子问题: ( D )A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是:( C )A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的:( A )A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是: ( A )A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是: ( B)A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是: ( A)A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序能够不满足如下性质: ( D )A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是: ( A )A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题:( C )A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是: ( A )A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法: ( C )A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到: ( C )A、全局最优解B、 0-1背包问题的解C、背包问题的解 D、无解14、能求解单源最短路径问题的算法是: ( A )A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是:( A )A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分:二、写出下列程序的答案( 每题2.5分, 共2题)1、请写出批处理作业调度的回溯算法。

《算法分析与设计》各章课后作业第一章 课后作业1. 设某算法在输入规模为n 时的计算时间为T(n)=10*2n。

若在甲台计算机上实现并完成该算法的时间为t 秒，现有一台运行速度是甲的64倍的另一台计算机乙，问在乙计算机上用同一算法在t 秒内能解决的问题的规模是多大？2.按照渐近阶从低到高的顺序排列以下表达式：4n 2，logn ，3n，20n ，2，n 2/3。

又n!应该排在哪一位？第二章 课后作业1. 用展开法求解下列递推关系：T(n)=⎩⎨⎧>+=1n )()2/(20n )1(n O n T O，写出T(n)的大O 记号表示。

2. 下面是实现在a[0]<=a[1]<=…<=a[n-1]中搜索x 的二分搜索算法，请根据二分 搜索技术在下划线处填充语句。

算法描述如下： template<class Type>public static int BinarySearch(int []a, int x, int n) { //在a[0]<=a[1]<=…<=a[n-1]中搜索 x // 找到x 时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while ( ) {int middle = ;if(x == a[middle]) return ; if(x > a[middle]) left = middle + 1; else right= ; }return -1; // 未找到x}第三章课后作业1、选择题。

（1）下列算法中通常以自底向上的方式求解最优解的是（）。

A、备忘录法B、动态规划法C、贪心法D、回溯法（2）备忘录方法是那种算法的变形。

（）A、分治法B、动态规划法C、贪心法D、回溯法（3）矩阵连乘问题的算法可由（）设计实现。

A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法2．计算题。

算法设计与分析作业姓名：学号：专业：习题一1-1函数的渐进表达式3n2+10n=O(n2);n2/10+2n=O(2n);21+1/n=O(1);logn3=O(logn);10log3n=O(n)1-2O(1)和O(2)的区别分析与解答：根据符号O的定义可知O（1）=O（2）.用O（1）和O（2）表示同一个函数时，差别仅在于其中的常数因子。

1-3按渐进阶排列表达式分析与解答：按渐进阶从低到高，函数排列顺序如下：O(2)<O(logn)<O(n2/3)<O(20n)<O(4n2)<O(3n)<O(n!)习题二算法分析题2-2 7个二分搜索算法分析与解答：（1）与主教材中的算法BinarySearch相比，数组段左、右游标left和right的调整不正确，导致陷入死循环。

（2）数组段左、右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。

（3）数组段左、右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。

（4）数组段左、右游标left和right的调整不正确，导致陷入死循环。

（5）算法正确，且当数组中有重复元素时，返回满足条件的最右元素。

（6）数组段左、右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。

（7）数组段左、右游标left和right的调整不正确，导致当x=a[0]时陷入死循环。

2-26修改快速排序算法，使它在最坏情况下的计算时间为O（nlogn）.分析与解答：从一个无序的序列中随机取出一个值q做为支点,然后把大于q的放到一边，小于q的放到q的另一边,然后再以q为分界点，分别对q的两边进行排序（快排时直接再对q两边重新取支点，整理，再取支点，...直到支点两旁都有序。

也就是支点两旁只有一个数时）#include <stdio.h>#include <stdlib.h>int Qsort(int p[],int beg,int end){if(beg+1>=end)return 0;//退出递归int low,hight,q;low=beg;hight=end;q=p[low];//q为支点，其实q可以为随机数。

算法理论、教改类题目学习大量相关算法（程序），总结出对应方法的一些特点，将其写成论文形式，并以足够的例子作为佐证。

24.论分治法、动态规划、贪心法的区别 25.论递归程序向非递归程序的转换 26.论应用型本科院校算法课程的教学目标和教学方法 27.论二叉树在计算机科学与技术中的应用 28.数据库索引的算法解释 29.论贪心法的适用范围 30.解空间搜索方法的选择依据 31.分治法算法分析综述
算法应用、算法研究类题目查阅大量相关资料，对相关内容给出初步的结果。

31.基于UCCI的中国象棋对弈引擎开发技术研究 32.五子棋对弈关键技术研究33.黑白棋对弈关键技术研究 34.数独初始局面生成算法研究 35.支持按文件名搜索的索引构造技术研究 36.通用回溯算法演示系统设计 37.通用分支限界算法演示系统设计 38.通用排序算法演示系统设计 39.通用动态规划算法演示系统设计
40.论文阅读和翻译类题目• 给出一个英文文献，用准确的语言将其翻译为中文，不需要逐字逐句翻译，但主要观点、算法思想和算法过程表述清楚、准确、充分。

格式要求• 论文正文中不得出现大段代码（超过10行）• 标题样式需规范• 参考文献不低于10篇，参考文献格式和标注位置须规范。

最接近点对问题问题此问题分为一维，二维，三维的情况1. 一维: 给定直线上n 个点，找其中一对点，使得在n 个点组成的所有点对中，该点对间的距离最小，这个问题比较简单，是引出二维解法的一个引子，因为一维的直线上的点，相邻点的距离肯定小于相隔的点的距离，只需要考虑相邻点即可。

2. 二维：给定平面上n 个点，找其中一对点，使得在n 个点组成的所有点对中，该点对间的距离最小，这是我们这一问题的重点3. 三维：给定空间上n 个点，找其中一对点，使得在n 个点组成的所有点对中，该点对间的距离最小，此问题是二维的解法的复杂化，具体可以在飞机航线等问题上运用，但在此不多做介绍。

基本思想由于该问题的基本解法是去考察每个点和其他所有点的距离。

因此它的时间复杂度是2()O n ,这样做的效率太低，我们就要去寻找一个更高效的办法：分治法。

1. 因二维的情况太过复杂，先考虑一维的情况中，可以用分治法对其进行分部计算： 把直线分成两部分, 1s 2s ,分别求出其最接近点的距离1d 2d 。

但分割开的地方的两点距离可能小于这两个值，这三个值进行比较之后，得到最后结果。

2. 鉴于此，二维的也可以用此方法进行计算：把待计算的点s 分成两部分1s 2s ，分别求出其最接近点的距离1d 2d 。

但1d 2d 最小的未必是s 中的最小距离d ，它有可能是1s 中的一个点和2s 中的一个点组成的最接近点对。

所以还要考虑1s 中的所有点到2s 中的每一个点的距离，一一比较之后得出一个最小值，再和1d 2d 比较，这就得出了最后结果。

3. 接下来是具体算法实现的步骤：1. 把待计算的点s 分成两部分1s 2s :重要的如何去划分，这里采用在二维平面上的中线（用横坐标的最小值加上最大值的平均数）来划分。

2. 分别求出其最接近点的距离1d 2d :这可以用一个递归来完成。

3. 计算1s 中的所有点到2s 中的每一个点的距离：这个问题是此问题的关键。

2010/2011第二学期计算机科学与技术专业2009级《算法分析与设计》课程大型作业班级：3110902学号：2009214390姓名：王真旎遗传算法一、算法背景遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。

其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。

遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

它是现代有关智能计算中的关键技术。

进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。

尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。

此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。

遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。

二、算法内容1.算法的简单描述遗传操作是模拟生物基因遗传的做法。

在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。

从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最优解。

1.1创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。

1.2.评估适应度对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。

不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。

算法设计与分析大作业目录《算法设计与分析》课程大作业.............................................. 错误！未定义书签。

一．动态规划算法解决流水作业调度 (2)1、问题描述 (2)2、算法分析 (2)3. 算法的描述 (2)4、部分算法实现 (3)5. 运行结果 (4)6、时空效率分析 (4)二．贪心算法解多机调度问题 (4)1、问题描述 (4)2、算法分析 (4)3.部分算法实现 (5)4.计算复杂性分析 (6)5. 运行结果 (6)三．回溯法解决批作业调度问题 (6)1.问题描述 (6)2.算法思想 (6)3. 部分算法实现 (7)4.运行结果 (8)5.时间复杂性分析 (8)四．作业调度算法比较 (8)五．课程学习总结 (9)摘要：在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。

把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。

关键词：作业调度；动态规划；贪心算法；回溯法；一．动态规划算法解决流水作业调度1、问题描述给定n 个作业，每个作业有两道工序，分别在两台机器上处理。

一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。

一个作业只有在机器1上的处理完成以后才能由机器2处理。

假设已知作业i 在机器j 上需要的处理时间为t[i,j]。

流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。

2、算法分析直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。

在一般情况下，机器M2上会有机器空闲和作业积压2种情况。

在一般情况下，机器M1开始加工S 中作业时，机器M2还在加工其他作业，要等时间t 后才可利用。