算法期末作业题精炼版

1、填空题动态规划算法的基本要素为：最优子结构性质与重叠子问题性质1）算法分析中，记号 O 表示渐进上界，记号 表示渐进下界， 记号 表示紧渐进界。2）回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。3）分支限界法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间树。 所谓贪心选择性质是指 （ 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到 ）。所谓最优子结构性质是指（ 问题的最优解包含了其子问题的最优解 ）。 回溯法是指（ 具有限界函数的深度优先生成法 ）。回溯法的算法框架按照问题的解空间一般分为（ 子集树 ）算法框架与（ 排列树 ）算法框 架。4

2、）二分搜索算法是利用分治策略实现的算法。5）衡量一个算法好坏的标准是时间复杂度低6）最长公共子序列算法利用的算法是动态规划法7）Strassen 矩阵乘法是利用分治策略实现的算法8）回溯法搜索状态空间树是按照深度优先遍历的顺序。9）算法中通常以自底向下的方式求解最优解的是动态规划法10）背包问题的贪心算法所需的计算时间为O（ nlogn ）11）0-1 背包问题的回溯算法所需的计算时间为 O（ n2n）12）用动态规划算法解决最大字段和问题，其时间复杂性为 n13） 一个算法就是一个有穷规则的集合， 其中之规则规定了解决某一特殊类型问 题的一系列运算， 此外，算法还应具有以下五个重要特性 :_

3、 有穷性，确定性， 可行性，输入，输出 。 矚慫润厲钐瘗睞枥庑赖。1. 算法的复杂性有 时间 复杂性和 空间 复杂性之分。 聞創 沟燴鐺險爱氇谴净。2、程序是算法 用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条指令 是清晰的，无歧义的。4. 矩阵连乘问题的算法可由 动态规划 设计实现。6、算法是指解决问题的一种方法 或 一个过程 。7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。8、问题的最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。9、以深度优先方式系统搜索问题解的算法称为回溯法 。10、数值概率算法常用于数值问题 的求解。15

4、、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和 0/1 背包问题正好是两种不同的类型， 其中同时使用约束条件和目标函数的界进1 / 13行裁剪的是 0/1 背包问题，只使用约束条件进行裁剪的是N皇后问题。 残骛楼諍锩瀨濟溆塹籟。16、贪心选择性质 是贪心算法可行的第一个基本要素， 也是贪心算法与动态规划算法的 主要区别。17、矩阵连乘问题的算法可由动态规划 设计实现。19. 贪心算法的基本要素是贪心选择 质和 最优子结构 性质 。酽锕极額閉镇桧猪訣锥。21. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子 问题 ，然后从这些 子问

5、题 的解得到原问题的解。 彈贸摄尔霁毙攬砖卤庑。 23、大整数乘积算法是用分治法 来设计的。26、 贪心选择性质 是贪心算法可行的第一个基本要素， 也是贪心算法与动态规划算法的 主要区别。的一种排序算法。又带有 跳跃性 的搜索算法。约束函数 和 限界函规模 有关。27. 快速排序算法是基于 分治策略30. 回溯法是一种既带有 系统性 謀荞抟箧飆鐸怼类蒋薔。33回溯法搜索解空间树时，常用的两种剪枝函数为 数。厦礴恳蹒骈時盡继價骚。34. 任何可用计算机求解的问题所需的时间都与其35. 快速排序算法的性能取决于划分的对称性 。37. 图的 m 着色问题可用 回溯 法求解，其解空间树中叶子结点个数是

6、mn，解空间树中每个内结点的孩子数是 m。 茕桢广鳓鯡选块网羈泪。简答题1. 用计算机求解问题的步骤：1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析6、算法实现 7、程序调试 8、结果整理文档编制 鹅娅尽損鹌惨歷茏鴛賴。2. 最优二叉搜索树问题的动态规划算法void binarysearchtree(int a,int b,int n,int *m,int *s,int *w)籟丛妈羥为贍偾蛏练淨。int i,j,k,t,l;for(i=1;i=n+1;i+)2 / 13wii-1=ai-1;mii-1=0;for(l=0;l=n-1;l+)/l 是下标 j-i

7、 的差for(i=1;i=n-l;i+)j=i+l;wij=wij-1+aj+bj;mij=mii-1+mi+1j+wij;sij=i;for(k=i+1;k=j;k+)t=mik-1+mk+1j+wij;if(t1 时)。写成递归函数有：int fib(int n) if (n=0) return 0;if (n=1) return 1;if (n1) return fib(n-1)+fib(n-2);3 / 132. 算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过 程3. 算法的三要素1、操作 2、控制结构 3、数据结构4. 算法具有以下 5 个属性 ： 有穷

8、性：一个算法必须总是在执行有穷步之后结束， 且每一步都在有穷时间 内完成。确定性： 算法中每一条指令必须有确切的含义。 不存在二义性。 只有一个入 口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本 运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出， 这些输出同输入有着某些特定关系的量。经常采用的算法主要有迭代法、分治法、贪婪法、动态规划法、回溯法、分支 限界法8. 分治法的基本思想是：将一个规模为 n的问题分解为 k 个规模较小的子问题，这些子问题互相独立 且与原问题相同。 递归地解这些子问

9、题， 然后将各个子问题的解合并得到原问题 的解。 預頌圣鉉儐歲龈讶骅籴。9. 分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不 包含公共的子子问题。4 / 1310、分治法的基本步骤分治法在每一层递归上都有三个步骤：（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题 形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地 解

10、各个子问题；（3）合并：将各个子问题的解合并为原问题的解。11. 动态规划的基本思想动态规划的实质是 分治思想 和解决冗余 ，因此，动态规划 是一种将问题实例 分解为更小的、 相似的子问题， 并存储子问题的解而避免计算重复的子问题， 以 解决最优化问题的算法策略。 渗釤呛俨匀谔鱉调硯錦。13. 分治法与动态规划法的相同点是： 将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的 解得到原问题的解。两者的不同点是 ：适合于用动态规划法求解的问题，经分解得到的子问题往 往不是互相独立的。 而用分治法求解的问题， 经分解得到的子问题往往是互相独 立的。 铙誅卧泻噦圣骋贶頂廡。14. 回

11、溯法 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将 问题的候选解按某种顺序逐一枚举和检验。 当发现当前候选解不可能是解时， 就 选择下一个候选解； 倘若当前候选解除了还不满足问题规模要求外， 满足所有其 他要求时，继续扩大当前候选解的规模， 并继续试探。 如果当前候选解满足包括 问题规模在内的所有要求时， 该候选解就是问题的一个解。 在回溯法中， 放弃当 前候选解， 寻找下一个候选解的过程称为回溯。 扩大当前候选解的规模， 以继续 试探的过程称为向前试探。 擁締凤袜备訊顎轮烂蔷。20. 回溯法中常见的两类典型的解空间树是子集树和排列树。当所给的问题是从 n 个元素的集合

12、S中找出满足某种性质的子集时， 相应 的解空间树称为子集树。这类子集树通常有 2n 个叶结点，遍历子集树需 O（2n）5 / 13计算时间贓熱俣阃歲匱阊邺镓騷。当所给的问题是确定 n 个元素满足某种性质的排列时， 相应的解空间树称 为排列树。这类排列树通常有 n!个叶结点。遍历排列树需要 O(n!)计算时间。 坛摶 乡囂忏蒌鍥铃氈淚。22. 请叙述动态规划算法与贪心算法的异同。共同点： 都需要最优子结构性质， 都用来求有优化问题。不同点： 动态规划：每一步作一个选择依赖于子问题的解。 贪心方法：每一步作一个选择不依赖于子问题的解 。 动态规划方法的条件：子问题的重叠性质。可用贪心方法的条件：最

13、优子结构性质；贪心选择性质。 动态规划：自底向上求解； 贪心方法： 自顶向下求解。可用贪心法时，动态规划方法可能不适用； 可用动态规划方法时，贪心法可能不适用。23. 请说明动态规划方法为什么需要最优子结构性质。答： 最优子结构性质是指大问题的最优解包含子问题的最优解。 动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优 解，然后再利用子问题的最优解构造大问题的最优解， 因此需要最优子结构 . 蜡變黲癟報伥铉锚鈰赘。26. 在算法复杂性分析中， O、 这三个记号的意义是什么？在忽略常数 因子的情况下，O、分别提供了算法运行时间的什么界？ 答： 如果存在两个正常数 c和 N0,对

14、于所有的 NN0，有|f(N)|C|g(N)|，则记作：f(N)= O(g(N)。这时我们说 f(N)的阶不高于 g(N)的阶。 買鲷鴯譖昙膚遙闫撷凄。6 / 13若存在两个正常数 C 和自然数 N0，使得当 NN0 时有 |f(N)|C|g(N)|，记为 f(N)=?( g(N)。这时我们说 f(N)的阶不低于 g(N)的阶。 綾镝鯛駕櫬鹕踪韦辚糴。 如果存在正常数 c1，c2 和 n0，对于所有的 nn0，有 c1|g(N)| |f(N)| c2|g(N)| 驅踬髏彦浃绥譎饴憂锦。则记作 f(N)= (g,(N)O、分别提供了算法运行时间的上界、下界、平均1用动态规划策略求解最长公共子序列

15、问题：1)给出计算最优值的递归方程。2)给定两个序列 X=B,C,D,A ，Y=A,B,C,B ，请采用动态规划策略求出其最长公共子序列，要求给出过程。 猫虿驢绘燈鮒诛髅貺庑。答：(1)0ci, j ci 1,j 1 1max(ci, j 1, ci当i 0或j 0时当i, j 0且xi yi 时1,j ) 当i, j 0且xi yi 时(2)最长公共子序列：2对下列各组函数 f (n) 和 g (n)，确定 f (n) = O (g (n) 或 f (n) = (g (n)或 f(n) = (g(n)，并简要说明理由。 锹籁饗迳琐筆襖鸥娅薔。(1) f(n)=2n；g(n)=n!(2) f(

16、n)= n ；g (n)=log n2(3) f(n)=100 ；g(n)=log1007 / 13(4) f(n)=n 3； g(n)= 3n(5) f(n)=3 n；g(n)=2n 答：(1) f(n) = O(g(n)因为 g(n)的阶比 f(n) 的阶高。(2) f(n) = (g(n)因为 g(n)的阶比 f(n) 的阶低。(3) f(n) =(g(n)因为 g(n)与 f(n) 同阶。(4) f(n) = O(g(n)因为 g(n)的阶比 f(n) 的阶高。(5) f(n) = (g(n)因为 g(n)的阶比 f(n) 的阶低。3对下图所示的连通网络 G，用克鲁斯卡尔 (Krusk

17、al) 算法求 G 的最小生成树T, 请写出在算法执行过程中，依次加入 T 的边集 TE 中的边。 说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。 構氽頑黉碩饨荠龈话骛。答：TE=(3,4), (2,3),(1,5), (4,6 )(4,5 ) 贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。 基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不 同连通分量的边中选权值最小的边， 将其放入生成树中， 直到生成树中有 n-1 条边。 輒峄陽檉簖疖網儂號泶。时间复杂度为： O(eloge)4. 请用分治策略设计递归的归并排序算法，并分析其时间复杂性(要

18、求：分别 给出 divide、conquer、combine 这三个阶段所花的时间，并在此基础上列出递归 方程，最后用套用公式法求出其解的渐进阶) 。尧侧閆繭絳闕绚勵蜆贅。答 ： Template void MergeSort (Type a , int left, int right) if (left2)；T(2)=1。因为 n=2 k(k 为正整数)，所以，T(n)= T(2 k)= 2T(2 k-1)+2= 22T(2 k-2)+ 22+2?k-1 k-2 3 2= 2 T(2)+ 2 +?+2 +2 +2= 2k-1+?+23+22+2。因此， T(n)= (n)。8. 考虑使用动态规划方法求解下列问题： 01背包数据如下表，求：能够放入背包的最有价值的物品集合。物品i重量wi价值vi承重量W1w1=2v1=12W=52w2=1v2=103w3=3v3=204w