算法复杂性分析期末复习答案1

《算法复杂性分析期末复习答案1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、填空题(本题15分，每小题1分)1.规则一系列运算2.随机存取机RAM(RandomAccessMachine)；随机存取存储程序机RASP(RandomAccessStoredProgramMachine)；图灵机(TuringMachine)3.算法效率4.时间、空间、时间复杂度、空间复杂度5.2n6.最好局部最优选择7.贪心选择最优子结构二、简答题(本题25分，每小题5分)1、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互和独立「LL原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够

2、小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，白底向上逐步求出原來问题的解。2、“最优化原理”用数学化的语言來描述：假设为了解决某一优化问题，需要依次作出n个决策DI,D2,Dn,如若这个决策序列是最优的，对于任何一个整数k,1

3、基本思想是在一棵含有问题全部nJ能解的状态空问树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树屮不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续卜•一步深度优先搜索过程。在冋溯法小，并不是先构造出整棵状态空问树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。5^P(Polynomial问题):也即是多项式复杂程度的问题。NP就是Non-deterministicPolynomial的问题，也即是多项式复杂程度的非确定性问题。N

4、PC(NPComplete)问题，这种问题只有把解域里面的所有可能都穷举了Z后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。三、算法填空(本题20分，每小题5分)1、n后问题回溯算法(1)!M[j]&&!L[i+j]&&!R[i-j+N](2)M[j]=L[i+j]=R[i-j+N]=l;(3)try(i+l,M,UR,A)⑷A[i][j]二0(5)M[j]二L[i+j]二R[i-j+N]二02、数塔问题。(1)c<=r(1)t[r][c]+=t[r+l][c](1)t[r][c]+=t[r+1][c+1]3^

5、Hanoi算法(1)move(a,c)(2)Hanoi(n-1,a,c,b)(3)Move(a,c)4、(1)p[v]=NIL(2)p[v]=u(3)v^adjEu](4)Relax(u,v,w)四、算法理解题(本题10分)五、(1)8天(2分)；(2)当n=23=8吋，循环赛tl程表(3分)。六、算法设计题(本题15分)(1)贪心算法O(nlog(n))1234567821436587341278564321876556781234658721437856341287654321>首先计算每种物品单位重量的价值Vi/Wi,然后，依贪

6、心选择策略，将尽可能多的单位重量价值最髙的物品装入背包。若将这种物甜全部装入背包后，背包内的物胡总重虽未超过C,则选择单位重屋价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。>具体算法可描述如下：voidKnapsack(intn,floatM,floatv[J,floatw[J,floatx

7、J){Sort(n,v,w);inti;for(i=l;i<=n;i++)x[i]=0;floatc=M;for(i=l;i<=n;i++){if(w[i]>c)break;x[i]=l；c-=w[i];if(i<

8、=n)x[i]=c/w[i];}(2)动态规划法O(nc)m(i,j)是背包容量为j,可选择物品为i,i+1,…，n时()・1背包问题的最优值。由()・1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下。[max{m(z+1,+1J—叱)+v,}j>w,加a刀=1ia』・M+l,丿)0

9、j=w[n]y<=c;j++)/*m(n,j)=v[n]j>=w[n]*/m[n][j]=v[n];for(i=n-l;i>l;i—){intjMax=min(w[i]-1,c);for(j二();jv二jMax;j++