中国地质大学研究生课程论文封面
课程名称算法分析与设计
教师姓名
研究生姓名
研究生学号
研究生专业计算机技术
所在院系计算机学院
类别: B.硕士
日期: 2014 年 1 月8 日
评语
注：1、无评阅人签名成绩无效；
2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；
3、如有平时成绩，必须在上面评分表中标出，并计算入总成绩。
1.1算法
算法：用计算机求解问题的步骤、规则
内存空间——>初始状态—————>终止状态
有限状态机
算法的五个特性：
输出：一个算法产生一个或多个输出
从内存——>认识状态
输入：一个算法有0个输入或多个输入
input a，b
无二义性：算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的（人和计算机、智能、确定的、机器；人机象棋：搜索）。
能行性：
（1）人能做，机器没法做：能够形式化，没有办法写出算法
（2）股票预测、彩票：模型
有限性：可计算问题、有限的、可忍耐
算法设计：自动化、自动程序设计、公式发现、公式挖掘、知识发现
算法验证：设计—表示（语言）—确认—分析—测试程序
1.2算法分析
数学模型：
1.串行算法，冯诺依曼机
2.均匀存贮，存贮空间足够大
3.基本运算时间确定
基本概念：
1.问题规模：与参数有关
2.频率计数
不分析算法具体执行时间，分析问题复杂性：问题规模增大时的规律
根据复杂性，将算法分为两类：
1.多项式时间算法P：C，㏒n，n，n㏒n，n2（理论上可行，实际上也可行）
2.指数时间算法NP：2n，n！，n n（理论上可行，实际上不可行）
O(l) O(2n)< O(n!)< O(n n) 解决方法：降低算法设计复杂度 分析算法时间与问题规模： 确定f(n)=O(g(n))上界和f(n)=Ω(g(n))下界 1.3小结 老师首先带领我们回顾了本科阶段的算法基础相关知识，对于没有系统学习过算法知识的我来说，更是一种知识入门，使我对这门课程有一些初步的了解。然后在对算法进行分析时，不分析算法具体的执行时间，而是分析问题的复杂性（问题规模增大时的规律）。根据算法的特点可以将要求解的问题分为两类：离散型和连续型。离散型问题需要讨论问题的规模，如果是多项式时间复杂度则称为P问题；如果是指数时间复杂度则称为NP问题。对于连续型问题，需要讨论算法的收敛性。 2.1一般方法 在求解问题时，为了将问题简化，将实际问题转变为数学问题，将数学问题转变为代数问题，将代数问题转变为解方程问题，将解方程问题转变为解线性方程组问题。 求解问题的技术： 1.化难为易的校正技术：例如求f(x)=a-x 2=0； 2.化粗为精的松弛技术：直接法，间接法，例如求圆的面积（割圆法） 3.化大为小的缩减技术：f(n)=n*f(n-1)，f(1)=1问题性质不变 分治法的思想：将整个问题分为若干个小问题分而治之，问题的性质不变。它的求解可用一个递归过程来表示。 2.2二分检索 已知一个按非降次序排列的元素表a 1,a 2,…,a n ，要求判定某给定元素x 是否在该表中出现。问题规模O(㏒n) 2.3归并分类（排序） Procedure mergesort(low,high) if low then mid |(low+high)/2」 call mergesort(low,mid) call mergesort(mid+1,high) call mergesort(low,mid,high) end if 问题规模O(n ㏒n) 2.4快速分类 反复对产生的文件进行划分 2.5斯特拉森矩阵乘法 ***m l l n m n A B C 问题规模O(n 3) 2.6小结 分治法是一种用空间换时间的技术，通过将大规模的问题划分为小规模问题进行求解来降低求解难度，采用分治技术，问题首先必须能够分解，而且分解后，问题的性质并没有发生变化。采用分治技术的目的只是并行算法设计，降低算法时间复杂度。在本章老师主要讲解了分治法的基本递归求解，二分检索、归并分类、快速分类、斯特拉森矩阵乘法以及它们的时间复杂度的求解。 第三章 贪心法 3.1一般方法 概念：有n 个输入，问题的解是这n 个输入的一个子集，子集满足一组条件（约束条件），子集可能有很多，满足条件的子集叫做可行解，根据问题，人们设计一个函数，通过函数极值的计算，找到一个最优的可行解，叫做最优解。 离散优化问题 连续函数优化问题的分类： 1.函数优化问题：f(x)：高维、非线性、不连续、没有明确的解析式；这类问题的求解方法有：解方程法、迭代法（最速下降法、共轭方向法、牛顿迭代法等）、随机优化（演化计算）等。 2.模型参数优化：此类问题的求解方法一般是：根据所给问题或者曲线，然后预测方程，对预测方程中的参数进行优化求解。 3.模型发现问题：自动程序设计，一般是输入散点，要求给出拟合曲线。解决方法有基因表达式程序设计等。 优化问题分类： 1.有约束优化与无约束优化 2.线性优化与非线性优化 3.静态优化与动态优化（实时性） 4.确定性优化与随机优化 5.单目标优化与多目标优化（矛盾或不协调的） 贪心算法是一种分级处理方法，它根据问题性质找到一种度量标准 3.2背包问题 部分背包问题的数学模型为：假设背包容量为m ，有n 件物品，每种物品i 的重量为w i ，其效益值为p i ，问如何装包，在背包的容量范围内装出的值最多。 1 max n i i i x p =∑ 1 n i i i x w M =≤∑ x i ∈{0,1} 0/1背包问题 x i ∈[0,1] 部分背包问题 老师以书上的题目为例，根据按效益值由大到小的装、按质量由小到大的装和按单位质量效益值由大到小的装（p i /w i ）三种方法来寻找最优解。经过计算可知按单位质量效益值由大到小的装包获得的结果最好。 3.3最小生成树问题 设G=(V,E)是一个无向连通图，如果G 的生成子图T=(V,E ’)是一棵树，则称T 是G 的一棵生成树。根据边成本由小到大排序，找到最优的生成树。 3.4小结 贪心算法适用于求解从给定的n 个输入中找到一个满足约束条件的子集的问题。满足约束条件的子集称为可行解，满足目标函数的可行解称为最优解。用贪心算法求解问题的关键在于找出求解问题的量度标准。本章老师主要讲了贪心算法的适用领域，详细讲解了背包问题及最小生成树的算法及其时间复杂度的求解。为了便于学生理解，老师联系自己曾经做过的毕业设计的凸多边形问题，讲述了是如何对问题进行分析和寻找解决方案的，而且讲解了为何贪心算法无法用于求解凸多边形问题，使同学们更好的领悟和体会贪心法的应用范围。 第四章 动态规划 4.1一般方法 求解优化问题的方法： 1.多阶段决策：可以把问题分成若干阶段 2.最优性原理：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列（找到一个递推关系式）。 4.2多段图问题 多段图G=(V,E)，求源点s 到汇点t 的最短路径 设cost(i,j)表示从源点到第i 个阶段的j 点的最短路径： 1,(,)min {(1,)(,)}i l V l j E cost i j cost i l c l j -∈<>∈=-+ 设Bcost(i,j)表示从第i 个阶段的j 点到汇点的最短路径： 1,(,)min {(1,)(,)}i l V l j E Bcost i j bcost i l c l j +∈<>∈=++ 4.3每对结点之间的最短路径 单源最短路径问题O(n 2) 任意两点间最短路径问题O(n 3) 设A k 代表i ，j 两个结点间考虑了1-k 结点时最短路径，A 0(i,j)就是成本矩阵 A 0(i,j)=C(i,j) A n (i,j)=min{ A n-1(i,j), A n-1(i,n)+ A n-1(n,j)} A k (i,j)=min{ A k-1(i,j), A k-1(i,k)+ A k-1(k,j)} 4.4最优二分检索树 设a 1< a 2< a 3<…< a n ，n 个符号 a 1 a 2 a 3 … a n P(1) P(2) P(3) … P(n) E 0 E 1 E 2 E 3 E n-1 E n Q(0) Q(1) Q(2) Q(3) Q(n-1) Q(n) 1 ()()1n n i i P i Q i ==+=∑∑ 检索成本的计算方法： 1 ()*()()*(()1)n n i i i i P i level a Q i level E ==+-∑∑ a k L R 1 (,)()()j j k i k i w i j P k Q k =+== +∑∑表示的是单倍成本/单倍的概率之和 11 10 1 ()()*()()*(()1) ()()*()()*(()1) k k i i i i n n i i i k i k cost L P i level a Q i level E cost R P i level a Q i level E --===+==+-= +-∑∑∑∑ 总成本： ()()()(0,1)(,)()()(0,)P k cost L cost R w k w k n cost L cost R w n +++-+=++ 1(0,)min{(0,1)(,)()(0,1)(,)}k n C n C k C k n P k w k w k n ≤≤=-+++-+ 0(0,)min{(0,1)(,)}(0,)k n C n C k C k n w n <≤=-++ 比较运算n 次——耗时 (,)min{(,1)(,)()(,1)(,)}i k j C i j C i k C k j P k w i k w k j <≤=-+++-+ (,)min{(,1)(,)}(,)i k j C i j C i k C k j w i j <≤=-++ C(i,j)代表构造的二分检索树最优成本 ()(0,1)cost L C k =- ()(,)cost R C k n = 4.5矩阵连乘问题： [ ]123410*200M M M M =，假设r 0=10，r 1=30，r 2=70，r 3=1，r 4=200，求最小计算量。 矩阵连乘问题满足以下公式： ***m l l n m n A B C =，**1 l ij i k k j k C a b ==∑ 根据分析，得到递推公式： 1(,)min{(,)(1,)}i k j i k j D i j D i k D k j r r r -≤<=+++ D(i,j)表示1 2i i i j M M M M ++???最优的次数 01(1,)min{(1,)(1,)}k n k n D n D k D k n r r r ≤<=+++ 据此得到结果： 0 21000 2400 4400 1 0 2100 8100 1 2 0 14000 3 3 3 4.6 0/1背包问题 设f j (x)表示将第1至j 件物品装入容量为x 的包所获得的最大效益值。 1()max{(),()}j j j j j f x f x f x w P -=-+ f j-1(x)表示前面已装满的情况下的效益值，f j (x-w j )+P j 表示将第j 件物品装进去后的效益值，两者取最大者为最终结果。 11()(),0()()(),1j j j j j j j j j f x f x x f x f x f x w P x --==? ? =-+=? 老师以书上题目为例，为大家讲解整个求解过程，题目为：n=3，（w 1,w 2,w 3）=（2,3,4）， （p 1,p 2,p 3）=（1,2,5），M=6。 0,0 ()0,0 x f x x -∞ ≥? 部分背包问题 同样的n 件物品，x i ∈{x|0≤x ≤1}，部分背包情况下获得的效益值为P 1，0/1背包情况下获得的效益值为P 2，部分背包情况下减去小数部分的效益值为P 3，三者满足关系P 1≥P 2≥P 3。 4.7 TSP 问题 有n 个城市，城市之间距离用C(i,j)表示，从编号为1 的城市经过其他的n-1个城市一次且一次，回到城市1，路径最短。 图中任意两点间最短路径O(n 3) 静态TSP ：C(n,n)不变（O(n!)） 动态TSP ：C t (n,n)随时间变化，实时 （动态）多目标TSP ：C(n,n)，C ij ={a 1,a 2}，速度快、成本低 设g(i,S)代表从i 点出发经过S 中的（S 是城市编号的集合）所有城市后回到1的最大路径，最终求： 1(1,)min{(,{1})}(,)min{(,{})}i ij i S j S g S C g i S g i S C g j S j ∈∈=+-?=+- {2,3,4,,}S n =??? 老师以书上题目为例，利用上面给出公式，计算得出结果。 0101520509106130128890???????????? 4.8子集和数问题： 设有n 个正整数{a 1,a 2,…,a n }，求和为M 的一个子集。 4.9调度问题： 1.相同处理机的调度 设有{t 1,t 2,…,t n }有相同的设备两台，让你给出调度模式调度这n 个任务 2.流水线调度问题 两个设备的流水线调度问题：P 问题（排序问题） 三个设备的流水线调度问题：NP 问题 P1P2 S={t 1,t 2,…,t n }，g(S,0) 可得递推公式： (,0)min{({},)}i i i i t S g S a g S t b ∈=+-（a i ,t 都结束才可以调度b i ） 根据问题所要求的解的不同，可以将这些问题分为三类： 1.求解整数规划类问题。要求自变量为整数，即最终结果是要求给出整数解集合的一个选择。例如：多段图问题和0/1背包问题。 2.求解最优结构。要求最终结果是给出一棵最优二分树的结构。例如：最优二分检索树和矩阵连乘问题。 3.序列优化问题。要求最终结果是找出最优的一个排列。例如：TSP 问题和调度问题。 4.10小结 动态规划方法一般用来求解优化问题。使用该方法求解的问题主要有两个特点：多阶段决策，可以把问题分为若干个阶段；满足最优性原理，当前状态和决策只和它前一阶段的状态有关，和前一阶段的状态和决策如何得到无关。用动态规划求解问题，关键在于找到求解 问题的一个递推关系式。本章内容很多，同时又很重要，老师详细的为我们讲解了如何利用动态规划技术求解多段图问题、任意两点间最短路径问题、最优二分检索树、矩阵连乘问题、0/1背包问题、TSP问题和调度问题，并详细讲解了如何构造与使用递推关系式来解决这些问题。对于每一个问题，老师都通过讲解书上的实例来加深我们对算法理解和认识，也让我们更清楚如何利用算法解决相关问题。用动态规划技术解决矩阵连乘问题是老师课外拓展的内容。老师还向我们简单介绍了子集和数问题，它与0/1背包问题、TSP问题、3-Sat问题都属于NP问题，想要求解它们，就要找到合适的方法将它们化简为P问题。另外，对于本章用动态规划解决的几类问题，老师也带我们进行了归类总结，更加深了我们对动态规划技术的印象。 第五章基本检索与周游方法 5.1一般方法 1.树的检索 二叉树检索（先根、中根、后根） 以下图为例： 宽度优先：①②③④⑤⑥⑦⑧ 深度优先：①②④⑧⑤⑥③⑦ 5.2双连通分图和深度优先检索 双连通、单连通、关节点 识别关节点：根节点有几个儿子 叶子节点肯定不是关节点 中间节点：从它每个儿子出发往下走，能经过边到达它的祖先节点。 计算每一个节点的深度优先数DFN(x)，最低深度优先数L(x)。 5.3对策树（博弈树） 每个节点，状态评估函数E(x) max-min过程 max(f)→A；min(f)→B α截断：如果一个求最小值位置的值被判断为小于或等于它父亲的α值，那么可以停止生成这个求最小值位置的其余儿子的值。 β截断：如果一个求最大值位置的值被判断为大于或等于它父亲的β值，那么可以停止生成这个求最大值位置的其余儿子的值。 α-β截断：对于任一结点x，设B是该结点父亲的B值且D=-B，那么如果x的值判断为大于或等于D，则可以停止生成x的其他儿子。 老师以书上题目为例，通过一种假想的博弈游戏，为我们讲解了α-β截断的使用方法。 5.4小结 基本检索与周游方法一般是针对树、图这样的数据结构。对数据结构的操作即为算法的设计与分析。老师首先带领大家回顾了树的搜索策略和图的周游策略。老师通过一个实例详细讲解了如何将一个已有的图变为一个双连通图；详细讲解了决策树问题，决策树要求非常有限的结点和层数；对于有限次博弈游戏所有可能的实际战例或者有限步之内的战例可以用一颗决策树表示，每一个结点表示一种战例，而对于一些博弈游戏（例如：国际象棋）来说，构造的决策树相当大，因此我们只需要构造有限步骤的决策树，并且用一些剪枝策略减去对自己不利的部分，这里老师详细讲解了α-β剪枝算法。 第六章回溯法 6.1一般方法 在本章内容开始时，老师将问题的求解技术进行了总结： 对于连续问题，有连续性、容易判断大小，可以利用搜索技术、领域变换规则进行求解； 对于离散问题（子集和数），通过初始状态引导出最终状态，需要的方法更复杂。 离散问题连续问题 问题子集和数x2-2=0 问题状态(0,0,0,0) (1) 求解方法贪心算法（量度标准） 动态规划（递推关系式） 通过构造解空间树直接法（数学分析） 通过领域变换（迭代法） 根据问题的性质和规范函数要求，找出限界函数、问题的上下界深度优先+限界函数=回溯法 宽度优先+限界函数=分枝限界法 1.问题描述：求一个n元组(x1,x2,…,x n)，x i∈S i，||S i||= n i。 2.问题状态：一个元组，要求的参数的集合有两种表示方法： 元组长度固定：(0,0,0,0)； 元组长度不定：(a1),(a1,a4)； 3.解空间树（状态空间树）：用树的结构表示 4.解状态：与表示方法有关 5.答案状态 6.2 0/1背包问题 老师以书上题目为例，P=(11,21,31,33,43,53,55,65)，w=(1,11,21,23,33,43,45,55)。下图为回溯法求解0/1背包问题所生成的树： 6.3小结 回溯法一般用于求解n元组问题。求解方法有两种：部分解和完全解。所需要的求解结构为状态空间树结构，将回溯过程用树的形式表达。老师以0/1背包问题为例讲解了如何利用回溯法求解问题，并讲解了树结点的得出，以及剪枝（限界函数）的策略。在回溯状态空间树结构中加入限界函数，可以尽可能少的检索树结构结点，尽快找到解结点。 第七章分枝-限界法 7.1一般方法 (x1,x2,…,x n)，x i∈S i 状态及状态转移 深度优先 宽度优先 计算：基于规则的一组符号变换过程 7.2 LC分枝-限界求解 老师以书上题目为例，通过0/1背包问题和TSP问题，为我们讲解了LC分枝-限界方法： 对于0/1背包问题，我们利用两个函数来为成本函数c(x)限界，前者为将包装满时的成本估计函数，后者为舍弃分数尾时的上界函数，使它们对于每个结点x ，都满足以下式子： ()()()c x c x u x ∧ ≤≤ 利用这两个函数，可以获得最优的结果。 对于TSP 问题，同样是利用两个函数限界，结合成本矩阵和归约矩阵获得最终的结果。 搜索方法（状态转移方法） 确定性方法： 1.解析法：非线性方程组求解 直接法：基于梯度、grad 导数 间接法：变成线性方程组、迭代 2.规划：整数规划：0/1背包 动态规划：多段图 3.枚举法（遍历） 宽度优先 深度优先 4.剪枝法 基于状态树概念：α-β截断、限界函数 随机性方法： 盲目搜索：概率算法 导向搜索：演化算法、禁忌搜索 7.3小结 分枝-限界方法是利用广度优先的方法来构造状态空间树。老师首先以0/1背包问题为例讲解如何通过分枝-限界法构造一个状态空间树，计算每个结点的上界和下界，以及如何生成新结点。然后又以TSP 问题为例讲解了如何利用分枝-限界法，结合构造状态空间树、成本矩阵和归约矩阵，找到解决TSP 问题的一个最优组合排列。比较动态规划方法与分枝-限界法解决TSP 问题的效果，虽然两种方法计算复杂度的最坏情况是一样的，但是对于许多具体实例而言，分枝-限界算法要比动态规划技术所用的时间少得多。 第八章 程序设计 因为本人曾在完成毕业设计时了解过有关TSP 问题的求解方法，因此，当老师布置本课程的程序设计题目时，我选择了利用动态规划技术求解TSP 问题。 根据动态规划算法需要求g(i,S)。以4个城市为例，需要求出g(i,S)，i 取值从1到3，S 取值为{{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}},也就是集合{1,2,3}的所有子集合，而所有的子集合可以用二进制数表示。如果数在集合中，为二进制1，否则为0，数字大的在高位，如{1,2,3}表示成111，也就是7。{3}表示成100，也就是4。这样可以把集合映射成数组的下表，同时通过C 语言的位操作来完成判断元素是否在集合中等操作，所以算法的过程就是计算二维表（n * 2^(n-1)）的过程。源代码如下： #include #define MAXCOST 99999 int min(int first,int second) { return first < second? first:second; } int main(int argc,char *argv[]) { int nCity=0; printf("please enter the number of cities:\n"); scanf("%d",&nCity); int **cost = (int **)malloc( sizeof(int *) * nCity ) ; for(int i=0; i < nCity; i++){ cost[i]=(int *)malloc( sizeof(int) * ( (int)pow(2.0,nCity-1) ) ); memset(cost[i],0,sizeof(int) * ( (int)pow(2.0,nCity-1) )); } int **distance = (int **)malloc( sizeof(int *) * nCity) ; for(int i=0; i < nCity; i++){ distance[i]=(int *)malloc( sizeof(int) * nCity ); } printf("please enter the distance between cities:\n"); for(int i = 0; i < nCity; i++){ for(int j = 0; j < nCity; j++){ scanf("%d",&distance[i][j]); } } //初始化g(i,{}) for(int i = 1; i < nCity; i++){ cost[i][0] = distance[i][0]; } for(int i = 1; i < ( 1 << (nCity - 1)) - 1; i++){ for(int j = 1; j < nCity; j++){ if( ( ( 1 << ( j -1 ) & i ) >> (j -1) ) == 0 ){//判断i是否在S中，防止重复 //求出S中包含的元素和元素的个数 int counter = 0; int *set = (int *)malloc( sizeof(int) * nCity ); for(int k = 0 ; k < nCity - 1; k++){ if(( (i >> k) & 1) == 1){ set[counter] = k+1; counter++; } } int mincost = MAXCOST; for(int k = 0; k < counter; k++){ //求出除去i,j后集合中元素映射到数组的下标，根据g(i,S)=min( c(i,j) + g(j,{S-J}) int nCitytoSet = 0; for(int l = 0; l < counter; l++){ if(set[l] != set[k]){ nCitytoSet += (1<<(set[l]-1)); } } mincost = min( mincost , (distance [j][ set[k] ] + cost[ set[k] ][nCitytoSet]) ); } cost[j][i] = mincost; } } } //根据g(i,S)=min( c(i,j) + g(j,{S-J})，算出经过g(0,{1,2,3,...N-1}),也就是经过节点0返回节点0的最小代价 int mincost = MAXCOST; for(int i = 1; i < nCity ;i++){ int nCitytoSet = 0; for(int l = 1; l < nCity ; l++){ if(l != i){ nCitytoSet += (1<<(l-1)); } } mincost = min( mincost , (distance [0][ i ] + cost[i][nCitytoSet]) ); } cost[0][( 1 << (nCity -1)) - 1 ] = mincost; printf("the min cost is =%d\n",cost[0][( 1 <<(nCity -1) ) - 1 ]); return 0; } 实验截图： 第九章学习心得 时间飞逝，转眼之间，一学期的算法设计与分析的课程已经结束，回首12节课程所学，回忆很多，收获也很多。 首先要说的就是老师讲课的风格，在本科时代我没有学习过算法设计与分析这门课程，当看到这门课程的名称时，我觉得这门课上起来会很枯燥乏味，但是通过老师的悉心讲解，我并未感受到学习这门课程有很大困难，反而觉得听起来十分轻松。而且，老师上课从来不用PPT，整个学期全部是通过手写板书讲授课程，将算法的每一个细节，每一步的推导，算法的关键点在何处都认真的传授给我们，使我们能够紧跟老师的节奏，对每一个知识点都有深入的理解；另外，老师经常在每章课程结束时对一章所学算法知识进行总结，将前后知识联系到一起，既有助于加强巩固所学知识，又避免了学生因为总结不全面而对所学知识理解不够深入；此外，老师在讲到相关问题时，经常让学生回顾以往所学知识，进行联想记忆，让我们理解更深入，记忆更深刻。 其次要说的是我通过上课得到的一些收获与感悟，通过老师对七章内容的讲解，使我对算法设计与分析这门课程有了一个系统的了解，同时使我对算法的认识更加透彻。我也因此明白算法的时间复杂度的重要性，它是衡量一种方法的优劣的很有效的方法。老师在课堂上经常对所授知识进行总结，经常通过解决一些经典问题来引导我们学习不同的方法，例如求解0/1背包问题，可以用动态规划的方法，可以用分枝-限界的方法，还可以用回溯法进行解决，使我们求解问题的思路更加广阔，在求解问题时不必拘泥于一种方法。老师在讲每一个算法时，都是以书上题目为例，引导我们步步进行推导，让我们对算法的认识更加深刻，也让我们熟识了算法解决相关问题的过程。 最后，衷心感谢老师的谆谆教诲。 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 1.通过实验实践、巩固线性表的相关操作； 2.熟悉VC环境，加强编程、调试的练习； 3.用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作； 4.理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的 结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到 第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点 的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出 了这个环表的全部结点为止。 三、程序设计 1、概要设计 为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。 （1）、单向环表的抽象数据类型定义为： ADT Joseph{ 数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={ 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 12软件(2)班 学号: 0311232 成绩: 指导教师: 秦川 开课时间: 年一学期 一、问题描述 1．普通背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1≤i≤n。 2．0/1背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3．棋盘覆盖问题 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。 二、问题分析 1．普通背包问题 对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量Ｗ, 剩余的将是n-1个原重物品1, 2, ······, j-1, j+1, ·····, n以及重为Ｗi－Ｗ的物品j 中可装入容量为C－Ｗ的背包且具有最大价值的物品。 2．0/1背包问题 如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照物品的价值/物品的体积来从大到小排列, 然后最优解为( 1, 1, 1......., 1, t, 0, 0, ......) , 其中0<=t<=1; 因此, 我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下), 我们能够考虑我们能够达到的最大的价值, 即我们能够经过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。经过该条件, 能够减去很多的枝条, 大大节省运行时间。 3．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否 算法设计与分析实验报告 学院：信息学院 专业：物联网1101 姓名：黄振亮 学号：20113379 2013年11月 目录 作业1 0-1背包问题的动态规划算法 (7) 1.1算法应用背景 (3) 1.2算法原理 (3) 1.3算法描述 (4) 1.4程序实现及程序截图 (4) 1.4.1程序源码 (4) 1.4.2程序截图 (5) 1.5学习或程序调试心得 (6) 作业2 0-1背包问题的回溯算法 (7) 2.1算法应用背景 (3) 2.2算法原理 (3) 2.3算法描述 (4) 2.4程序实现及程序截图 (4) 2.4.1程序源码 (4) 2.4.2程序截图 (5) 2.5学习或程序调试心得 (6) 作业3循环赛日程表的分治算法 (7) 3.1算法应用背景 (3) 3.2算法原理 (3) 3.3算法描述 (4) 3.4程序实现及程序截图 (4) 3.4.1程序源码 (4) 3.4.2程序截图 (5) 3.5学习或程序调试心得 (6) 作业4活动安排的贪心算法 (7) 4.1算法应用背景 (3) 4.2算法原理 (3) 4.3算法描述 (4) 4.4程序实现及程序截图 (4) 4.4.1程序源码 (4) 4.4.2程序截图 (5) 4.5学习或程序调试心得 (6) 作业1 0-1背包问题的动态规划算法 1.1算法应用背景 从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。 1.2算法原理 1.2.1、问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ?∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 1.2.2、最优性原理： 设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有 ∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c 因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。 1.2.3、递推关系： 一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有？ 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题，贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有？ 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征，主要有？ 二 1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。 2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。 3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。 4．一个正在生成孩子的结点称为扩展结点。 5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。 7．一个自身已生成但其孩子还没有全部生成的结点称为活结点 8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间 9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。 10．分支限界法采用的是宽度优先搜索。 11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法 12．一个所有孩子已经生成的结点称做死结点 13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。 三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 银行家算法设计实验报告 银行家算法设计实验报告 一．题目分析 1.银行家算法： 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 2.基本要求： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。 （3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源， 但大于系统此时的可利用资源，提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源， 亦未大于系统此时的可利用资源，预 分配并进行安全性检查： a. 预分配后系统是安全的，将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 3.目的： 根据设计题目的要求，充分地分析和理解题 目，叙述系统的要求，明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 二、算法分析及思路： 对于该问题，我们做如下分析： （1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计；（2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计； （3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计； （4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计； （5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计； （6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题： 1.写一个对txt文件压缩和解压的程序，使用动态编码。 2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树； 3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图： 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 算法设计与分析课程报告 第一章 算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性：一个算法必须保证执行有限步之后结束; ② 确切性：算法的每一步骤必须有确切的定义; ③ 输入： 一个算法有 0 个或多个输入， 法 本身定除了初始条件; ④ 输出： 一个算法有一个或多个输出， 是毫无意义的; ⑤可行性：算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。 第二章 算法分析基础 1、算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响） 般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 以刻画运算对象的初始情况， 所谓 0 个输入是指算 以反映对输入数据加工后的结果。 没有输出的算法 位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F（N, I,A）。 第五章分治法 1、递归算法：直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注：边界条件与递归方程是递归函数的二个要素。 实例：①阶乘函数; ② Fibonacci 数列；③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题 优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解） 分治法所能解决的问题一般具有以下几个特征： ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 第六章贪心法 1、贪心算法的思想： 算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明 实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 一：实验目的 1：掌握动态规划算法的基本思想，学会用其解决实际问题。 2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。 二：实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 实验一：杨辉三角 问题分析： ①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 ②第n行数之和为2^n。 ③下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码： public void yanghui(int n) { int[] a = new int[n]; if(n==1){ System.out.println(1); }else if(n==2) { System.out.print(1 + " " +1); }else{ a[1]=1; System.out.println(a[1]); a[2]=1; System.out.println(a[1]+" "+a[2]); for(int i=3;i<=n;i++){ a[1]=a[i]=1; for(int j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(int j=1;j<=i;j++){ System.out.print(a[j]+" "); } System.out.println(); } } } 实验结果：n=10 实验二：0-1背包问题 问题分析：：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j 算法设计技巧与分析 答案 算法设计技巧与分析 参考答案 第1章算法分析基本概念 1.1 (a)6 (b)5 (c)6 (d)6 1.4 算法执行了7+6+5+4+3+2+1=28次比较 1.5 (a)算法MODSELECTIONSORT执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。 (b) 算法MODSELECTIONSORT 执行的元素赋值的最多次数是3(1)2 n n ,元素已按非升序排列的时候达到最小值。 1.7 由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。 1.11 由上图可以得出比较次数为5+6+6+9=26次。 1.13 FTF,TTT,FTF,TFF,FTF 1.16 (a) 执行该算法，元素比较的最少次数是n-1。元素已按非降序排列时候达到最小值。 (b) 执行该算法，元素比较的最多次数是(1)2 n n -。元素已 按非升序排列时候达到最大值。 (c) 执行该算法，元素赋值的最少次数是0。元素已按非降序排列时候达到最小值。 (d) 执行该算法，元素赋值的最多次数是3(1)2 n n -。元素已 按非升序排列时候达到最大值。 (e)n 用O 符号和Ω符号表示算法BUBBLESORT 的运行时间：2()t O n =，()t n =Ω (f)不可以用Θ符号来表示算法的运行时间：Θ是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。 1.27 不能用p 关系来比较2n 和2100n 增长的阶。 ∵221 lim 0100100 n n n →∞=≠ 2n ∴不是2(100)o n 的，即不能用p 关系来比较2n 和2100n 增长 的阶。 1.32 (a)当n 为2的幂时，第六步执行的最大次数是： 12,2k k n j -==时， 1 1 [log ]log n n i i k n n n ====∑∑ (b)由(a)可以得到：当每一次循环j 都为2的幂时，第六步执行的次数最大， 则当33,22k k m n j ===（其中 32 k 取整）时， 1 1 [log(3 1)]log(1)n n k i i i m n n ===-=-∑∑ (c)用O 符号表示的算法的时间复杂性是(log )O n n 已证明n=2k 的情况，下面证明n=2k +1的情况： 因为有?? ? ???+=??????21222k k 所以n=2k +1时，第六步执行的最大次数仍是n log n 。 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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．代码设计： 《算法设计》课程报告 课序号： 01 学号： 2012141461134 姓名：刘佳玉 任课教师：陈瑜 评阅成绩： 评阅意见： 提交报告时间：2014年 6 月 16 日 贪心算法 1、问题描述 （这是我在soj上找的一道题，以前没做出来，现在用贪心的思想做出来了） 约翰要去钓鱼。他有h小时可用（1≤h≤16），在这个地区有n个湖泊（2≤n≤25），所有的湖泊沿着一条单行道可到达。约翰从湖泊1开始，他可以在任何湖泊结束。他只能从一个湖，到下一个，但他没有必要停在任何湖除非他想停。对于每个i = 1，……，n-1，ti 表示从湖i到湖i+1的5分钟的时间间隔（0 < ti < = 192）。例如，t3 = 4意味着它从湖3湖4需要20分钟的时间。 为了帮助他们规划自己的钓鱼旅行，约翰已经收集了一些关于湖泊信息。对于每个湖泊的i，能钓到的鱼在最初的5分钟的数量，用fi表示（fi > = 0），是已知的。每钓5分钟的鱼，能钓到的鱼在接下来的5分钟的间隔降低一个恒定的数di（di＞＝0）。如果能钓到的鱼在一个时间区的数量小于或等于di，将不会有更多的鱼留在湖里在下一个时间间隔。为了简化规划，约翰认为没有人会在影响他期待钓到的鱼的数量的湖里钓鱼。 写一个程序来帮助约翰计划他的最大化期望钓到的鱼的数量的钓鱼之旅。在每个湖花费的时间数必须是5的倍数。 这个问题包含多个测试案例！ 一个多输入的第一行是一个整数N，然后一个空白行后的N个输入块。每个输入块由问题描述中的格式表示的。每个输入块之间有一个空行。 输出格式包含N个输出块。输出块之间要有一个空白行。 输入 在输入中，会给你一个案例输入的数量。每一种情况下，以n开始，其次是h，接下来有一行n个整数指定fi（1 < =i< = n），然后有一行n个整数di（1≤i＜＝n），最后，有一行n - 1的整数ti（1≤i＜＝n-1）。输入在n=0的情况下终止。 输出 算法设计与分析 1、(1) 证明：O(f)+O(g)=O(f+g)（7分） (2) 求下列函数的渐近表达式：（6分） ① 3n 2+10n; ② 21+1/n; 2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由。（15分） (1) ;5log )(;log )(2+==n n g n n f (2) ;)(;log )(2n n g n n f == (3) ;log )(;)(2n n g n n f == 3、试用分治法对数组A[n]实现快速排序。（13分） 4、试用动态规划算法实现最长公共子序列问题。（15分） 5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。（12分） 6、试用动态规划算法实现下列问题：设A 和B 是两个字符串。我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括： (1)删除一个字符。 (2)插入一个字符。 (3)将一个字符改为另一个字符。 将字符串A 变换为字符串B 所用的最少字符操作数称为字符串A 到B 的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A 和B ，计算出它们的编辑距离d(A,B)。 （16分） 7、试用回溯法解决下列整数变换问题：关于整数i 的变换f 和g 定义如下：??2/)(;3)(i i g i i f ==。对于给定的两个整数n 和m ，要求用最少的变换f 和g 变换次数将n 变为m 。（16分）算法设计与分析实验报告贪心算法
算法设计与分析考试题及答案
北京理工大学《数据结构与算法设计》实验报告实验一
算法设计与分析考试题及答案
算法设计与分析课程设计报告样本
算法设计与实验报告讲解
算法设计与分析复习资料1
算法设计与分析试卷(2010)
银行家算法设计实验报告
算法设计与分析试卷及答案
算法设计与分析课程设计报告
南京邮电大学算法设计实验报告——动态规划法
计算机算法设计与分析期末考试复习题
算法设计与分析课程报告
算法与设计实验报告
算法设计技巧与分析答案上课讲义
算法设计与分析实验报告
算法设计实验报告(川大陈瑜)
算法设计与分析试卷及答案
相关主题
文本预览