“算法分析和设计”的最终问题和参考答案“算法分析和设计”的最终问题和参考答案1.简要回答以下问题: 1.算法的重要特征是什么? 2.算法分析的目的是什么? 3.问题的哪些因素与算法的时间复杂度有关? 4.算法的渐进时间复杂度是什么意思? 5.最坏情况下的时间复杂度和平均时间复杂度有什么区别? 6.简要描述二进制搜索(半搜索)算法的基本过程. 7.背包问题的目标函数是否与贪婪算法的优化措施相同? 8.如何表达回溯解决的问题的解决方案?都有些什么样的规矩? 9.回溯的搜索特征是什么? 10.皇后回溯算法的判别函数位置的基本流程是什么? 11.为什么通过分治法设计的算法通常具有递归调用? 12.为什么分析最坏情况的算法时间复杂度? 13.简要描述渐进时间复杂度上限的定义. 14.二进制搜索算法有多少个比较? 15.在最坏的情况下,快速排序算法需要多少比较操作? 16.贪心算法的基本思想? 17.回溯解决方案(x1,x2,...,xn)的隐式约束通常意味着什么? 18.解释合并排序的分而治之思想. 19.快速排序的基本思想是什么?
20. 什么是直接递归和间接递归?通常使用什么数据结构来消除递归? 21.哈密顿环问题是什么? 22.用回溯法求解哈密顿量时如何定义决策函数? 23.请写出基本算法的基本思想. 2.复杂性分析1.如果低,则MERGESORT(低,高);高;然后中←(低,高)/ 2; MERGESORT(低,中); MERGESORT(中+ 1,高);合并(低,中),高); endif end MERGESORT 2,过程S1(P,W,M,X,n)i←1;如果W(i)>a≤0而i≤n则做. M然后返回endif a←a + ii←i + 1;重复end3.procedure分区(m,p)整数m,p,i;全局A(m: p-1)v←A(m); i←m循环i←i + 1直到A(i)≥v重复循环p←p-1直到A(p)≤v重复i< p然后调用INTERCHANGE(A(i),A(p))否则退出endif重复A(m)←A(p); A(p)←v结束PARTITION4. 如果n<则执行F1(n). 2然后返回(1),否则返回(F2(2,n,1,1))endif end F1过程F2(i,n,x,y)如果i≤n,则调用F2(i + 1,n,y, x + y)endif返回(y)结束F25. 过程MAX(A,n,j)xmax←A(1);如果A(i),则j←1对于i←2至n. xmax然后xmax←A(i); j←i; endifrepeat结束MAX6.procedure BINSRCH(A,n,x,j)整数low,high,mid,j,n;低←1;高←n而低≤高做中←| _(低+高)/ 2_ |情况: x< A(mid): 高←mid-1: x> A(mid): 低←中+ 1: else: j←中;返回尾号重复j←0结束BINSRCH III. 算法理解1.编写多段图的最短路径,并通过动态规划算法求解以下示例,找到最佳值.
每边的成本如下: C(1,2)= 3,C(1,3)= 5,C(1,4)= 2 C(2,6)= 8,C(2 ,7)= 4,C(3,5)= 5,C(3,6)= 4,C(4,5)= 2,C(4,6)= 1 C(5,8)= 4 C(6,8)= 5,C(7,8)= 62,在下面的示例中编写通过maxmin算法找到最大值和最小值的过程. 数组A =(48,12,61,3,5,19,32,7)3.给出5个数字(3,6,9,1,7),M = 13,使用递归树描述sumofsub算法来查找sum的过程= M的子集. 4.快速排序算法对以下示例进行排序. 在算法执行期间,写出第一次被分割的数组A的过程. A =(65,70,75,80,85,55,50,2)5.合并排序算法对以下示例进行排序,并编写算法执行过程. A =(48,12,61,3,5,19,32,7)6.通过图着色问题的回溯算法,写出判断X [k]是否合理的过程. 7.对于下图,编写绘图着色算法的过程以获得着色方案. 8.编写问题7的状态空间树. 9.编写通过合并排序算法对以下示例进行排序的过程. (6,2,9,3,5,1,8,7)10.用背包问题的贪婪算法编写以下示例的求解过程.
P =(18,12,4,1)W =(12,10,8,3)M = 25 11,这里有{1、3、9、12、32、41、45的有序列表,62,75,77,82,95,100},当使用二进制搜索值为82的节点时,经过几次比较后搜索成功并给出了过程. 12.使用prim算法构造最小生成树,如下图G所示. 距离(1,2)= 6; dist(2,5)= 3; dist(5,6)= 6; dist(6,4)= 2; dist(4,1)= 5; dist(1,3)= 1; dist(2,3)= 5; dist(3,4)= 5; dist(3,6)= 4; dist(5,3)= 6 13.下面描述了以下函数: int f(int x,int y){f = x Mod y +1;}如果a = 10,b = 4,c = 5,则执行k = f(f(a + c,b),f(b,c)),k的值是多少,并写出详细过程. 14.McCathy函数定义如下: 100,m(x)= x-10;当x< = 100,m(x)= m(m(x + 11));编写一个递归函数以计算给定的x M(x)值.
15. 设计一种算法,以找到向量A中的最大和最小元素. 4.设计算法1.有n个独立的作业{1,2,„,n},它们由m台相同的机器处理. 作业i所需的处理时间为ti. 约定: 可以在任何计算机上对任何一项作业进行处理,但是不允许在完成之前中断该处理. 任何工作都不能拆分成较小的子工作. 多机调度问题需要一种调度方案,以使给定的n个作业尽可能短. 该时间由m台机器处理. 设计算法,并讨论是否可以获得最佳解决方案. 2.有n个面值为d1≥d2≥„≥≥dn的,您需要找到零钱M,如何选择dk,Xk的个数满足d1×Xi +“ dn×Xn M,为了使Xi + n Xn最小,请选择一个贪心策略,然后设计一个贪心算法. 3.有n个项目,已知n = 7,利润P =(10,5,15,7,6,18,3),权重W =(2,3,5,7,1,4,1),背包体积M = 15,只能选择背包中的物品,或者不打包背包,设计贪婪算法,并讨论是否可以获得最佳解决方案.
4. 设计仅需要一个哈密顿环的回溯算法. 5.使用对称设计算法,找到n为偶数的皇后问题的所有解. 请参阅答案1. 简要回答以下问题: 1.确定性,可实现的,输入,输出和有限的. 2.分析算法占用计算机资源的情况,比较和评估算法,并设计更好的算法. 3.算法的时间复杂度与问题的大小有关,并且是问题的大小n的函数. 4.当问题n的尺度趋于无穷大时,影响算法效率的重要因素是T(n)的阶数,而其他因素只是时间复杂度的常数差,因此数量级T(n)的(阶数)可用于评估算法. 时间复杂度T(n)的顺序(渐进)称为渐近时间复杂度. 5.最坏情况下的时间复杂度和平均时间复杂度检查了固定n时在不同输入实例下算法消耗的时间. 最坏情况下的时间复杂度是输入实例的最大时间复杂度: W(n)= max {T(n,I)},I∈Dn平均时间复杂度是每个输入实例及其各自总和的处理时间的概率乘积: A(n)= ∑P(I)T(n,I)I∈Dn6. 令输入为元素表A [i: j],并且x以非降序排列,选择A [(i + j)/ 2]与x比较,如果A [(i + j)/ 2] = x,则返回(i + j)/ 2,如果A [(i + j)/ 2]&lt ; x,然后A [i: (i + j)/ 2-1]找到x,否则在A [(i + j)/ 2 + 1: j]中找到x.
以上过程被递归地反复调用. 回溯的搜索特征是什么? 7.不一样. 目标功能: 获得最大的利润. 最佳度量: 最大利润/权重比. 8.问题的解可以表示为n个元组: (x1,x2,... xn),xi∈Si,Si是一个有限集,xi∈Si,(x1,x2,... xn)是完全的,即(X1,x2,... xn)是合理的,则(x1,x2,... xi)(i< n)必须是合理的. 9.在解空间树上进行跳转深度深度优先搜索,即使用决策函数检查x [k]的值,如果x [k]合理,则搜索x [k]为根节点,如果x [k]取所有值后,它将返回到x [k-1]. 10.将第K行中的皇后与前k-1行中的皇后进行比较,以查看它们是否兼容. 如果它们不兼容,则返回false,然后在测试后返回true. 11.当子问题的规模仍然很大时,您必须继续使用分而治之的方法. 12最坏情况下的时间复杂度决定了算法的优缺点,最坏情况下的时间复杂度比平均时间复杂度更具可操作性. T(n)是算法的时间复杂度函数,f(n)是一个简单函数,有正整数No和C,n> No,有T(n)<. f(n),则此关系为T(n)= O(f(n)).
14. 二进制搜索算法的最大比较数为log n. 15. 在最坏的情况下,快速分类会退化为气泡分类,需要进行n次比较. 16.这是一种分层处理方法,根据最佳测量结果依次选择输入. 基本思想是: 首先根据问题的含义选择测量标准;然后根据此测量标准对n个输入进行排序,然后依次选择输入量以添加到部分解中. 如果当前输入的输入不满足约束,则该输入将不会添加到解决方案的这一部分. 17.回溯方法(x1,x2算法分析与设计,...,xn)解的隐式约束通常是指元素之间应满足的某种关系. 18.说到将数组分为两部分,分别对每个集合排序,然后将两个排序的序列合并为具有n个元素的排序序列. 如果拆分后子问题仍然很大,则继续拆分并征服直到一个元素. 19.快速排序的基本思想是将N个记录中的任何一个进行排序,并将记录放置在最终位置,该记录将数据序列分为两部分. 所有小于记录键的关键字都放在第一部分,所有较大的关键字都放在后一部分,而记录则放在两部分的中间. 此过程称为快速排序. 然后重复上述过程,直到时间的每个部分都是: O(1)而i≤n进行n次循环,因为i≤n递归调用F2,当n≤1 F1时,总共进行n-2次( n)当n> 1时,时间为O(1),F1(n)的时间复杂度与F2(2,n,1,1)的时间复杂度相同,即O(n)5,xmax ←A(1); j←1次: i(2)到n的O(1)循环最多进行n-1次,因此总时间为: T(n)= O(1)+(n-1)O(1)= O (n)6,log2n + 1 3.算法理解1.成本(4,8)= 0成本(3,7)= C(7,8)+ 0 = 6,D [5] = 8成本(3, 6)= C(6,8)+ 0 = 5,D [6] = 8成本(3,5)= C(5,8)+ 0 = 4 D [7] = 8成本(2,4)=分钟{C(4,6)+成本(3,6),C(4,5)+成本(3,5)} =最小值{1+ 5,2 + 4} = 6 D [4] = 6成本( 2,3)=最小{C(3,6)+成本(3,6)} =最小{4 + 5} = 9 D [3] = 5成本(2,2)=最小{C(2,6 )+成本(3,6),C(2,7)+成本(3,7)} =最小{8 + 5,4 + 6} = 10 D [2] = 7成本(1,1)=最小{ C(1,2)+成本(2,2),C(1,3)+成本(2,3),C(1,4)+成本(2,4)} =最小{3 + 10,5 + 9,2 + 6} = 8 D [1] = 4 1→4→6→8 2.在以下示例中,编写maxmin算法以找到最大和最小数字.
数组A =()1,48,12,61,3,5,19,32,7 2,48,12 61,3 5,1932,7 3,48〜61,12〜3 19〜32 ,5〜7 4,61〜32 3〜5 5,61 3 3.给出5个数字(3,6,9,1,7),M = 12,使用递归树描述sumofsub算法sum = M子集. 4.第一个拆分元素是65(1)(2)(3)(4)(5)(6)(7)(8)ip 65 25080 85 55 75 70 4 6 65 25055 85 80 75 704 6 55 70 7580 85 65 50 2 5,48,12,61,35,19,32,7 48,12 61,35,1932,7 12,48 3,615,197,32 3,12,48,615,7,19,32 3 ,5,7,12,19,32,48,61 6,i←0而i<如果G [k,i] = 1并且X [k] = X [i],则返回k,如果i = k,则返回false i←i +1,然后返回true 7,K←1 X [1]←1,返回true X [2]←1,返回false; X [2]←X [2] + 1 = 2,返回true X [3]←1,返回false; X [3]←X [3] + 1 = 2,返回false; X [3]←X [3] + 1 = 3,返回trueX [4]←1,返回false; X [4]←X [4] + 1 = 2,返回false; X [4]←X [4] + 1 = 3,返回true找到一个解决方案(1,2,3,3)8,9,将第一个级别划分为6,2,9,35,1,8,7分为两个子问题,称为第二级6,2 9,35,1 8,7分为四个子问题,称为第三级6 2 9 35 1 8 7分为八个子问题. 称为第四级. 只有一个元素返回到上一层. 第三层合并为2、6、3、9、1.5、8、8. 上一层返回到第二层. 合并2、3、6、91、5、7,8返回上一层,第一层合并1、2、3、5、6、7、8、9排序结束,返回到主函数10,实例符合P(i)/ W(i)≥P(i +1)/ W(i + 1)阶.
本文来自电脑杂谈,转载请注明本文网址:
http://www.pc-fly.com/a/jisuanjixue/article-229542-1.html
这生意多好做啊”
留言好多托