一、算法时间复杂性问题
1. 试证明下面的定理：
(1)如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n));(2)如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)*g(n)=O(s(n)*r(n))根据符号O 的定义，存在正常数C 1，C 2和自然数N 1,N 2，使得对所有的n>= N 1，f （n ）<=C 1s(n)；对所有的n>= N 2,g(n) <=C 2r(n)所以 f （n ）+ g(n) <= C 1s(n)+ C 2r(n)，f （n ）*g(n)<= C 1C 2s(n)r(n)；
令 C3=max （C1,C2），C4=C1*C2；则：f （n ）+ g(n) <= C3[s(n)+ r(n)]=O(s(n)+ r(n))
（n ）*g(n) <= C4*s(n)*r(n)=O(s(n)* r(n))
2. 假设某算法在输入规模为n 时的计算时间为：T （n ）=3*2n ，在A 型计算机上实现并完成该算法的时间为t 秒，现有更先
进的B 型计算机，其运算速度为A 型计算机的64倍。试求出若在先进的B 型机上运行同一算法在则T 秒内能求解输入规模为多大的问题？某台t 秒内完成的基本运算的次数=3*2^n 新机器t 秒内完成的基本运算的次数=64*3*2^n=2^6*3*2^n=3*2^(n+6)
设N 为B 型机上t 秒钟能求解的问题的规模所以T=T(N)=3*2^N=3*2^(n+6) 则：N=n+6
3. 试说明为什么“在现代计算机上运行指数（如2n ）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，
有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。
一个计算时间为Ο(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即，零次多项式)来限界，而
一个时间为Ο(n 2)的算法则由一个二次多项式来限界。以下六种计算时间的多项式时间算法是最为常见的，其关系为
指数时间算法一般有Ο(2n )、Ο(n!)和Ο(n n )
等。其关系为：
其中，最常见的是时间为Ο(2n )的算法。当n 取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊因为根本
就找不到一个这样的m ，使得2n 囿界于n^m 。换言之，对于任意的m ≥0，总可以找到n 0，当n ≥n 0时，有2n ＞n m 。因此，
只要有人能将现有指数时间算法中的任何一个算法简化为多项式时间算法，那就取得了一个伟大的成就。Ο(log 2n)、Ο(n)和Ο(nlog 2n)比另外三种时间函数的增长率慢得多。～ 由这些结果可看出，当数据集的规模(即n 的取值)很大时，要在现代计算机上运行具有比Ο(nlog 2n)复杂度还高的算法往往是很困难的。尤其是指数时间算法，它只有在n 值取得非常小时才实用。尽管通过提高计算机的速度比之前快1000倍，甚至10000倍，但当指数规模的n 足够大时，n 每增加1，1000倍的提速即可瞬间化为乌有，所以要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度的数量级，而不是提高计算机的速度。
二、简答
1.对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则，用以指导设计出更高效的算法。试用简短的语言说明“建立一个问题复杂性的下界要比确定它的上界困难得多！”其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立。寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下界的算法。显然，建立下界要比确定上界困难得多。
2.满足何种性质的问题被称为NP 完全问题？请简述研究NP 完全问题的意义；
（1）NP 即是多项式复杂程度的非确定性问题。 而如果任何一个NP 问题都能通过一个多项式时间算法转换为某个NP 问题，那么这个NP 问题就称为NP 完全问题。如果一个NP 完全问题能在多项式时间内得到解决，那么NP 中的每一个问题都可以在多项式时间内解决。
（2）NP 完全是指这样一类NP 问题,所有的NP 问题都可以用多项式时间划归到他们中的一个.所以显然NP 完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的NP －完全问题也可以在多项式时间内求解。这样一来,只要我们找到一个NPC 问题的多项式解,所有的NP 问题都可以多项式时间内划归成这个NPC 问题,再用多项式时间解决,这样NP 就等于P 了.NP 完全性理论的重要性:知道一个问题是NP 完全的就给我们提供了有价值的信息，告诉我们采用什么样的途径可以是最富有成效的。一定不要去优先寻找有效的、精确的算法。现在比较适当的途径是集中精力致力于其他较低目标的方法。例如，你可以寻找解决这个问题的各种特殊情况的有效算法。寻找在大多数情况下看来能快速运算的算法，虽然不能保证它在任何情况下都能快速地运算。或者你甚至可以放松问题的某些方面，寻找一个只能给出满足大部分要求的快速算法。简言之，NP 完全性理论的初步应用是帮助算法设计人员找到最有可能得到有用的算法的努力方向
3. “当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质”。问题的最优子结构性质是该问题可用动态规划算法求解的基本要素，试简要阐述“论证某一问题的最优子结构性质”时的一般方法；矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。 Ο(2n )＜Ο(n!)＜Ο(n n ) Ο(1)＜Ο(log 2n)＜Ο(n)＜Ο(nlog 2n)＜Ο(n 2)＜Ο(n n )
同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）例如：假设（y1,y2,…,yn ）是0-1背包问题的一个最优解，而（y2,…,yn ）是相应子问题的一个最优解，有2max n i i i v x =∑ 112n i i i w x
C w y =≤-∑ {0,1}2x i n ∈≤≤
假设（y2,…,yn ）不是一个最优解，而（z2,…,zn ）是最优解，由此可知，
这说明
（y1,z1,z2,…,zn ）是问题的整体最优解，与（y1,y2,…,yn ）是最优解矛盾，所以证明了最优子结构性质！
三、算法设计与分析问题1. 最大值和最小值问题的最优算法（18）
给定n 个实数存放于一维数组A 中，试设计一个算法在最坏情况下用3n/2-2次的比较找出A 中的最大值和最小值（为简化，可假设n 为偶数）。
2. 社会名流问题
在 n 个人中，一个被所有人知道但却不知道别人的人，被定义为社会名流。现在的问题是如果存在，试找出该社会名流。你可以使用的唯一方式是询问：“对不起，请问你知道那个人吗？”（假定所有回答都正确，甚至这位社会名流也将回答。）我们的最终目标是将询问的数目最小化。给定一个n ×n 邻接矩阵，确定是否存在一个i ，其满足在第i 列所有项（除了第ii 项）都为1，并且第i 行所有项（除了第ii 项）都为0。大致的算法思路：随便取一个非对角线元素比如Array[i][j]，如果Array[i][j]=0成立，则j 不是社会名流，于是删去第j 行和第j 列。
同样，如果Array[i][j]=1成立，则删去第i 行和第i 列；总之，无论对应项取何值，都可以删去一行和一列，因此整个操作只耗费O(n)的时间。重复此操作直至剩下最后一个元素。最后，检验该元素是否为社会名流即可。如果该元素不是，则该群人中不存在社会名流。
3.数列极差问题
在黑板上写了N 个正数组成的一个数列，进行如下的操作：每一次任选其中的两个数设为a 和b ，将其擦去，然后在数列中加入一个新的数a*b+1，如此下去直至黑板上只剩下一个数为止。在所有按这种操作方式最后得到的数中，最大的数记为Max ，最小的数记为Min ，则该数列的极差定义为M=Max-Min 。
贪心算法最重要的两个性质是：贪心选择性质和最优子结构性质。贪心选择性质是所求问题的整体最优解可以通过一系列局部最优的选择，也就是贪心选择来达到。而最优子结构性质是指一个问题的最优解包含其子问题的最优解。 问题的关键就是MAX MIN 值的求解问题，所以首先看下怎么样来求MAX MIN 值。
设有三个数x y z,且x
我们再看下用贪心策略求解的合理性：假设经（N －3）次运算后得到3个数：x y max （max>x>y ），其中max 是（N －2）个数经（N －3）次运算后所得的最大值，此时最大值m ＝（x*y ＋1）×max ＋1。若经（N －2）次变换后所得的3个数为：x y z （z>x>y ）且z 不为（N －2）次变换后的最大值，即z ＜max 则所求得的最大值为： m ’＝（x*y+1）*z+1， 此时m －m ’＝（1+x*y ）（max －z ）＞0 所以此时不为最优解。 所以若使第k （1≤k ≤N －1）次变换后所得值最大，必使（k －1）次变换后
所得值最大（符合贪心策略的最优子结构性质），在进行第k次变换时，只需取在进行（k－1）次变换后所得数列中的两最小数x，y进行运算，再把结果插入到数列即可。所以综上所述：该算法可以简单的描述为：MAX：不断地取当前黑板上的两个最小的数进行运算并且放回，会使最后的结果最大。MIN：不断地取当前黑板上的两个最大的数进行运算并且放回，会使最后的结果最小。数列极差就是：MAX-MIN！
算法设计：①先将数列a[n]按从小到大进行排列(快速排序)
②进行最大值的计算：选出a[n]中最小的两个数进行（a*b+1）运算，在把运算结果按从小到大插入到数列中。
一直这样运算，最后就可以得出MAX值。
③进行最小值的计算：选出a[n]中最大的两个数进行（a*b+1）运算，在把运算结果按从小到大插入到数列中。
一直这样运算，最后就可以得出MIN值。
④最后该数列的极差M =MAX-MIN
4. 试说明如何修改快速排序算法，使它在最坏情况下的计算时间为O(nlgn)。
可以通过减少递归栈的使用进行优化，快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。对系统栈的频繁存取会影响到排序的效率。在数据量较大时，快速排序的复杂度为O(nlgn)。当数据集较小时，快排的复杂度有向O(n^2)发展的趋势，此时不必继续递归调用快速排序算法，使用插入排序代替快速排序。STL中sort 就是用的快排+插入排序的，使得最坏情况下的时间复杂度也是O(nlgn)．这一改进被证明比持续使用快速排序算法要有效的多。
使用一个快速排序的迭代模型可以使原递归算法所需的栈空间总量减至O（logn）。试设计这一迭代模型（算法）。
struct node
{int low,high;}st[10000];
void quicksort2(int data[],int s,int t){
int top=-1,low,high; top++; st[top].low=s; st[top].high=t;
while(top>-1){ low=st[top].low; high=st[top].high;top--; int w;
if(low st[++top].low=low;st[top].high=w-1; st[++top].low=w+1;st[top].high=high; }} 5. 试设计一个构造连通图G生成树的算法，使得构造出的生成树的边的最大权值达到最小。 解答：可以证明，图G的最小生成树即为满足题意的生成树。假设T，T’分别为图G的最小生成树及边的最大权值达到最小值的生成树。v，v’分别为它们的最大权边。假如w(v)>w(v’),则将v从T删除之后，T变为两个连同的分支，此时，一定有T’的边v1连同这两个分支，否则T’将是不连通的。从而将v1加入到T中构成一新的生成树T’’=T-v+v1。且有w(v1) Prim算法 O(n2) 首先置 S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中。 这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 在上述Prim算法中，还应当考虑如何有效地找出满足条件i∈S, j∈V-S，且权c[i][j]最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closest[j])，最后将j添加到S中，并对closest和lowcost作必要的修改。 Kruskal算法 O(eloge) 首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w 在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。 6. 试设计在O(n)时间内求得数组A[1..n]的中位数的算法。 将n个输入元素划分成n/5(上取整)个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5(上取整) 个。找出这n/5(上取整)个元素的中位数。如果n/5(上取整)是偶数，就找它的2个中位数中较大的一个。 7. 两个数组找第k小元素 事件复杂度O(log(k) )在网上看的，和同学商讨过，可行，认为此方法比上个log（m）+log（n）的方法要好第一个数组m 个元素第二个数组n个元素分别从两个数组找第k/2个数，a[k/2],b[k/2];假设a[k/2] 后时也排在第k-1个位置，都小于第k个元素，所以可删去。其他情况同理； 当m或n小于k/2时，假设m 【例题3】聪明的学生(题目来源：CTSC 2001 Clever 命题人：张力) 一个教授逻辑学的教授有三名非常善长推理且精于心算的学生A,B和C。有一天，教授给他们三人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。 这时，教授先对学生A发问了：“你能猜出自己的数吗？”A回答：“不能。”教授又转身问学生B：“你能猜出自己的数吗？”B想了想，也回答：“不能。”教授再问学生C同样的问题，C思考了片刻后，摇了摇头：“不能。”接着，教授又重新问A同样的问题，再问B和C，……经过若干轮的提问之后，当教授再次询问某个人时，此人突然露出了得意个笑容，在把自己头上的那个数准确无误的报了出来。 现在，如果告诉你：教授在第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M，你能推断出另外两个学生的头上贴的是什么数吗？ 提示：总是头上贴着最大的那个数的人最先猜出自己头上的数。 由题意可知，每个人推断的依据仅仅是另外两个人的头上数，以及大家对教授提问所做出的否定回答，因此，找出他们推理的过程就成为解决本题的关键。 由于三个正整数中，一定有某个数是另外两个数的和，因此，当一个学生看到另两个学生头上的数时，他就知道自己的数只有两种可能，另两个数的和或差；而要猜出自己头上的数，只需否定两种可能中的一种，那另一种就是答案了。 因为三个数都是正整数，所以，若某个学生看到另两个学生的数相等，那他立刻就可以判断自己的数是另外两个数的和（因为不可能是0），相反，若他猜不出来，则给了另两个人一个信息——自己的数和第三个人的数不同，而这可以成为做出推理的一个重要条件。 为了把问题说得更加清楚，不妨举个例子来说：当N=5，M=8 时，有一个可能的情况是A、B、C三个人头上贴的数分别为2,8,6。 B 为什么能在第5次提问——即第2次问到他时——猜出自己的数呢？他是这样想的： “我看到的是A的2和C的6，因此，我头上的数只可能是4（=6-2）或8（=2+6）。但假如我的数是4，那在教授的第3次提问时，C 就能猜出自己的数来！——因为那时他看到的是A的2和我的4，C就面临着2（=4-2）和6（=2+4）的选择，但假如他是2，那在教授第2 次提问时，我就能猜出来，因为我看到的是两个2！因此他能肯定自己不是2，而是6。——而实际上C并未猜出，因此，我头上的数必定是8！” B的推理过程实际上是一个“假设——排除”的过程，即使设自己的数为两个数可能数中一个，如果另两个人中有人可以在自己之前猜出，那么被假设的那种情况就可以排除，从而也就猜出了自己的数。而原题中又给我们提示：“总是头上贴着最大的那个数的人最先猜出自己头上的数”，因此只需要排除另两个数的差的那种情况就可以了。 现在，实际上已经可以解决这样一个问题： 已知A，B，C三人头上贴的数为X1，X2，X3，求教授至少需要提问多少次，轮到回答问题的那个人才能猜出自己的数。再来分析一下这个问题。由原题提示中的结论“总是头上贴着最大的那个数的人最先猜出自己头上的数”，于当X1，X2，X3给出之后，谁最先猜出就已经确定了。不妨设最终猜出的人是B，那么既有X1+X3=X2，而B做出判断的依据即是排除了X2=│X1-X3│的可能，而他能够排除这种可能的依据则是X1=X3，假设X2=│X1-X3│的前提下，在前两个提问时，A或C必定能够猜出自己的数，而实际上他们没有猜出——即当前教授提问的次数，已经大于当三个人头上的数分别为X1,│X1-X3│,X3时，直到某人猜出自己的数为止教授需要提问的次数，这样B就能确定自己的数。而对于X1，│X1-X3│,X3时求提问次数，就又变成了一个子问题，在这个情况下，最先猜出自己的数的人即为A或C（这取决与X1与X3）的大小，若X1>X3，则A先猜出，否则就是C先猜出），这样就又安装上面的思路求解。这显然就是一个递归求解的过程。 设函数Times(i,j,t1,t2,t3)表示编号为t1①的人头上的数为i，编号为t2的人的数为j，编号为t3的人的数为i+j（即由t3最先猜出自己的数）时，教授需要提问的次数；P（t1,t2）表示教授按照1-2-3的顺序，从t1问到t2，最少需要提问的次数②，则根据上面的分析，有如下关系： t3, i=j times(i,j,t1,t2,t3)=< times(j,i-j,t2,t3,t1)+P(t1,t3), i>j times(i,j-i,t1,t3,t2)+P(t2,t3), i 于是，根据这一递归函数即可解决上面提出的问题。当然，前面解决的问题和原题还有不同，原题已知N,M要求三人头上的数，而刚解决的问题是已知三人头上的数，要求N,M——恰好将问题与条件互换了。那么如何利用已有的结论来解决原来的问题呢？很简单——用枚举法（还记得前面强调过的么？枚举可以为其他算法创造条件）! 由于M是三个数中最大的，则另两数只能在区间[1,M-1]内，又因为有这两数之和等于M，因此，只需枚举其中一个i，另一个就可以由M-i求出。对于枚举的每一种情况，判断其相应的Times函数值是否等于N，若等于，则为问题的一个解。至此，本题已经获圆满解决。①为了叙述方便，特将A,B,C三人编号为1,2,3，下同 ②实际上，当t2>t1时，P(t1,t2)=t2-t1,否则，P(t1,t2)=t2+3-t1 寻找丢失的数！ 类C语言：用一个二维数组保存数组中的数的二进制位，然后从右往左按列扫描，然后确定之后删除被排除的行和，然后扫描第二次。 特殊的整理： 桶排序：桶排序工作的原理是：将阵列分到有限数量的桶子里。每个桶子再个别排序。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。 要对大小为[1..1000]范围内的n个整数A[1..n]排序，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储(10..20]的整数，……集合B[i]存储((i-1)*10, i*10]的整数，i = 1,2,..100。总共有100个桶。然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。 假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果对每个桶中的数字采用快速排序，那么整个算法的复杂度是O(n+m*n/m*log(n/m))=O(n+nlogn-nlogm) 从上式看出，当m接近n的时候，桶排序复杂度接近O(n)。 简答题：贪心和动态规划的区别！主要理解贪心的思想局部！ 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。 雏形整理第一章和第二章： 算法特性：有穷，可行，确定，输入，输出四元组（Q，I，，f）时间复杂性的定义掌握，理解上界，下界和精确界的证明过程，已经背下来了，分为多项式时间算法和指数时间算法； O(1) < O(log n) < O(n) < O(n log n ) < O(n2) < O(2n) < O(n!) < O(n n) 买鸡问题：void chicken_problem(int n,int &k,int g[],int m[],int s[]){int i,j,a,b,c; k=0; i=n/5; j=n/3;for(a=0;a<=i;a++){for(b=0;b<=j;b++){c=n-a-b;if((5*a+3*b+c/3==n)&&(c%3==0)){g[k]=a;m[k]=b;s[k]=c;k++}}} } 货郎担问题：void salesman_problem(int n,float &min,int t[],float c[][]){int p[n],i=1;float cost;min=MAx_FLoat_NUM; while(i<=n!){产生n个城市的第i个排列于p;cost=路线p的费用；if(cost 选择排序及时间复杂度分析：代码简单自己看一下！时间复杂度1/2*n(n-1) 顺序查找最坏特性：失败查找最坏特性W Au(n) = n + 1；二分查找思想： 淘汰法找最大和次大元，没明白再看看找最大元开销：T1(n) = n - 1 次 大元开销：T2(n) = ? log2 n? - 1 整体的时间复杂度：n + ? log2 n? - 2 递归与分治经典问题 递归删除链表当中的某个元素：void delete_L(LinkList &L, ElemType x) {// 删除以L为头指针的带头结点的单链表中// 所有值为x的数据元素if (L->next) {if (L->next->data==x) {p=L->next; L->next=p->next;delete(p); delete_L(L, x);}else delete_L(L->next, x);}} // delete 汉诺塔：void hanoi(int n,char x,char y,char z){//将塔座x上按直径有小到大且至上而下编号为1-n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。if (n==1)move(x,1,z);//将编号为1的圆盘从x移到z else{hanoi（n-1,x,z,y）;//将编号为1至n-1的圆盘移动到y，z作辅助塔Move(x,n,z);//将编号为n的圆盘从x移到zHanoi （n-1,y,x,z）;//将y上编号为1至n-1的圆盘移到z，x作辅助}} （1）合并排序：合并排序时间复杂度的计算： ： 第k小元素 快速排序：主要思想：template 最坏时间复杂度 O （n 2） 平均时间复杂度O （nlogn ） 辅助空间：O(n)或O （logn ） 时间复杂度分析：快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程产生的两个区域分别包含n-1个元素和n 个元素。由于算法Partition(a,p,r)的计算时间为O （n ）,所以如果Partition(a,p,r)的每一步都出现这种部队成划分，则其计算时间复杂性T(n)满足： 解得 在最好的情况下，每次划分所取得基准都恰好为中值，即每次划分都产生两个大小为n/2的区域，此时有： (1)1(n)2(/2)()1O n T T n O n n ??≤=??+>?? 解得：()(log )T n O n n = 快排在平均情况下的时间复杂性也是这个值。通过修改算法，可以设计出采用随机选择策略的快速排序算法。在快排的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选择一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是比较对称的 template { int i = Random(p,r); Swap(a[i], a[p]);return Partition (a, p, r);} 1、 0-1背包问题 设所给0-1背包问题的子问题 的最优值为m （i,j ）,即m(i,j)是背包容量为j ，可选物品为i ，i+1，…,n 时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下 背包问题：首先计算每种物品单位重量的价值Vi/Wi 背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C ，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 最优装载问题照着这个代码完全可以写出来！ ∑=n i k k k x v max ?????≤≤∈≤∑ =n k i x j x w k n i k k k },1,0{i i i i w j w j j i m v w j i m j i m j i m <≤≥???++-++=0),1(}),1(),,1(max{),(n n n w j w j v j n m <≤≥???=00),( 动态规划经典问题： 证明0-1背包问题具有最优子结构性质 如果（x1,x2,...,xn）是所给0-1背包问题的最优解，则(x1,x2,...,xn-1)是下列子问题的最优解。 利用反证法证明。 证明：假设(x1,x2,...,xn-1)不是最优解，而(y1,y2,...,yn-1)是最优解。 由此可知: 因此: 上述结果说明： (y1,y2,...,yn-1,xn)是所给0-1背包问题的更优解。与前提矛盾。 矩阵连乘问题：时间复杂度：O(n3)，空间复杂度; O(n2)平方最长公共子序列： 分治与递归 1、两路归并排序【2-waysort MergeSort】 T(n)=nlogn-n+1=O(nlogn) 最坏时间复杂度，平均时间复杂度。 2、找最大元 T(n)=n-1 3、大整数的乘法把大整数分成两段，减少乘法次数，T(n)=O(n^(log3))=O(n^1.59) 3 T(n/2) + k n ( n > 1 ) 递归T(n) = k ( n = 1) k是整数 4、矩阵 1）普通算法 T(n)=O(n^3) 2）Strassen算法 T(n)=O(n^log7)=O(n^2.81) 5、Hanoi塔算法 T(n)=O(2^n) void hanoi(n,x,y,z) x源；z目的；y辅助；n盘子个数 6、二分搜索（已排好顺序） T(n)=O(logn) 7、棋盘覆盖chessBoard 2^k*2^k的棋盘，用到的L形骨牌个数恰为(4^ k-1)/3。T(k)=O(4^k) 8、快速排序QuikSort(a[],p,r) p上界，r下界。最坏时间复杂度O(n^2);平均时间复杂度O(nlogn); 9、最接近点对问题 T(n)=O(nlogn) 贪心算法 1、活动安排问题1）活动已按结束时间的非递减顺序排列 O(n); 2）没排序 O(nlogn) 2、贪心算法的基本要素两性质 1）贪心选择性2）最优子结构性质 贪心选择性：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是利用贪心算法求解最优解的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题：贪心算法；0-1背包问题：动态规划（0-1背包问题不具有贪心选择性质。原因是无法保证能够将背 包装满，而所剩空间将会降低总价值。） 3、最优装载 T(n)=O(nlogn) 4、哈夫曼编码O(nlogn) 5、单源最短路径O(n^2) 6、用贪心算法解背包问题的基本步骤： 1.计算每种物品单位重量的价值 Vi/Wi； 3.依据贪心选择策略，按照单位价值从高到低的顺序，依次将尽可能多的物品装入背包中。直到背包装满为止。是否可以将物品装入背包的条件是：有空间 动态规划 2、矩阵连乘问题时间上界O(n^3) 占用空间O(n^2) 3、设计动态规划算法的步骤 1）找出最优解的性质，并刻画其结构特征；2）递归地定义最优值；3）以自底向上的方式计 算出最优值；4）根据计算最优值时得到的信息构造最优解 4、动态规划算法的基本要素 1）最优子结构；2）子问题重叠 3）备忘录法 5、最长公共子序列 T(n)=O(mn)+O(m+n) 6、多段图问题向前递推 0-1背包与背包问题都具有最优子结构 已知背包最大承载重量为C，共有n个物品，每个物品的重量分别为Wi(i=1,2,...,n)，价值为 Vi(i=1,2,...n)。证明： 假设第k个物品是最优解中的一个物品，则从中拿出Wk对应的物品后所对应的解一定是其余n-1个物品，装入背包最大承载重量为C-Wk的最优解，否则与假设矛盾。 Dijkstra算法 1、Dijkstra算法具有最优子结构性质 证明算法中每步确定的dist[i]是当前从源点到顶点i的最短特殊路径长度。 证明：采用数学归纳法。 当|S|=1时，显然成立。假设在第k次贪心选择之前dist[i]存放着从源点到顶点i的最短特殊路径长度。 需要证明（第k+1次贪心选择）：根据贪心选择策略，将顶点u添加到S之后，dist[i]仍然是当前从源点到顶点i的最短特殊路径长度。 假设根据贪心选择策略，第k+1选择将顶点u添加到S中，对于顶点i 可能会增加一条从源点到达顶点i 的新的特殊路径。 这条新的特殊路径由两种可能： 情况1： 这条路径先由源点到达顶点u，再由顶点u直接到达i，则这条特殊路径的长度为： dist[u]+a[u][i] 如果这条路径更短，替换dist[i]；否则不变。 情况2： 如果新增加的特殊路径先由源点到达顶点u，再由顶点u途径另一顶点x到达i。由于x早于u进入S中，所以 dist[x]≤dist[u], 即dist[x]+a[x][i]≤dist[u]+a[u][x]+a[x][i]，故：这条新特殊路径不会影响dist[i]，因此不需要考虑。 结论：在任何时候，dist[i]都存放着当前从源点到i点的最短特殊路径长度。 2、Dijkstra算法具有贪心选择性质 按照贪心选择方式得到的dist[u]一定是从源点s到顶点u的最短路径长。 证明：假设存在一条从源点s到u的更短路径 d(s,x) 是从s 到x的路径长度，d(s,u) 是从s 到u的路径长度，d(x,u) 是从x 到u的路径长度 则dist[x] ≤d(s,x)， d(s,x)+d(x,u)=d(s,u) 由于d(x,u) ≥0，所以dist[x] 算法：是满足下述性质的指令序列。 有限性：每条指令的执行次数、时间有限 确定性：每条指令有确定的含义、无歧义 输入：0个或多个输入 输出：1个或多个输出 程序：是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。 设计算法的基本过程 分析问题域，确定数学模型 首先整理初始状态与结果状态之间的隐含关系，然后寻求从数学模型已知初始状态到达结果状态的运算步骤，即算法 算法复杂性是算法运行所需要的计算机资源量，需要的时间资源量称为时间复杂性，需要的空间资源量称为空间复杂性。这 些量只依赖于算法所要求解问题的规模、算法的输入和算法本身。 O的定义：如果存在正常数c和自然数n0，使得当n≥n0时，有f(n) ≤cg(n)，则称函数f(n)当n充分大时有上界，且g(n)是它的一个上界，记f(n)= O(g(n))。即f(n)的阶不高于g(n)的阶。 Ω的定义：如果存在正的常数c和自然数n0 ，使得当n ≥ n0时有f(n) ≥ cg(n)，则称函数 f(n)当n充分大时有下界，且g(n)是它的一个下界，记为f(n)=Ω(g(n))。即f(n)的阶不低于g(n)的阶。 f(n) = Ω(g(n)) θ的定义：如果存在三个正常数c1,c2和n0，使得当n ≥ n0时， c1g(n) ≤f(n) ≤c2g(n) 则记f(n)= θ(g(n))。即f(n)与g(n)同阶 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索 回溯法的求解过程 由于问题的解向量X=(x1, x2, …, xn)中的每个分量xi(1≤i≤n) 都属于一个有限集合Si={ai1, ai2, …, airi}，因此，回溯法可以按某种顺序（例如字典序）依次考察笛卡儿积S1×S2×…×Sn中的元素。 初始时，令解向量X为空，然后，从根结点出发，选择S1的第一个元素作为解向量X的第一个分量，即x1= a11，如果X=(x1)是问题的部分解，则继续扩展解向量X，选择S2的第一个元素作为解向量X的第2个分量，否则，选择S1的下一个元素作为解向量X的第一个分量，即x1= a12。依此类推，一般情况下，如果X=(x1, x2, …, xi)是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况： 1、如果X=(x1, x2, …, xi＋1)是问题的最终解，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解； 2、如果X=(x1, x2, …, xi＋1)是问题的部分解，则继续构造解向量的下一个分量； 3、如果X=(x1, x2, …, xi＋1)既不是问题的部分解也是问题的最终解，则存在下面两种情况： （1）如果xi+1= ai＋1k不是集合Si＋1的最后一个元素，则令xi+1= ai＋1k＋1，即选择Si+1的下一个元素作为解向量X的第i+1个分量； （2）如果xi+1= ai＋1k是集合Si＋1的最后一个元素，就回溯到X=(x1,x2, …, xi)，选择Si的下一个元素作为解向量X的第i 个分量，假设xi= aik，如果aik不是集合Si的最后一个元素，则令xi= aik＋1；否则，就继续回溯到X=(x1, x2, …, xi－1)； 棋盘覆盖 放置一个三格板后，棋盘中间区域已经放置好。如果把这个三格板看成三个残缺格，原来的残缺棋盘就可以分成4个残缺棋盘。虽然这个三个棋盘与原来棋盘不相似，但是通过放置一个三格板，可以将原来不相似的三个棋盘构造成残缺棋盘，这样这三个棋盘的放置方法可以采用类似原来残缺棋盘的放置方法。 当残缺棋盘的规模降为2*2时，这时棋盘不再分解，递归终止，因为这时残缺棋盘只要放置一个三格板就可以铺满。 当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘。特殊方格必位于4个较小子棋盘之一中，其余3个 子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘,即k=0,1×1。 棋盘覆盖分治算法伪语言 void chessBoard(int tr, int tc,int dr, int dc,int size) { if(size==0)return ; // 覆盖左上角子棋盘// 覆盖左下角子棋盘 if ( 特殊方块在左上角) if ( 特殊方块在左下角) 覆盖左上角; 覆盖左下角; else { else { 在右下角放一小方块; 在右上角放一小方块; 覆盖左上角; 覆盖左下角; } } // 覆盖右上角子棋盘// 覆盖右下角子棋盘 if ( 特殊方块在右上角) if ( 特殊方块在右下角) 覆盖右上角; 覆盖右下角; else { else { 在左下角放一小方块; 在左上角放一小方块; 覆盖右上角; 覆盖右下角; } } } 计算最优解的动态规划算法 假设Ai的维数为pi-1×pi，则输入序列为{ p0, p1, p2, ... ,pn } p[n+1] 记录每个矩阵的维数; m[i,j]记录AiAi+1...Aj相乘的代价（乘法次数）; s[i,j]记录取得最优代价所断开的点k 具有自底向上的计算特征： 如果计算m[i,j]，仅需要计算小于j-i+1个的矩阵乘积。 即计算长度为L的矩阵相乘代价仅依赖于小于L长度的矩阵相乘代价。 算法思路： 按照长度递增(1,2, ... n) 计算m[i,j]代价。 算法matrixChain，首先计算出m[i,i]=0,i=1,2,…,n。然后，根据递归式，按矩阵链长递增的方式依次计算： m[i,i+1],i=1,2,…,n-1,(矩阵链长度为2）； m[i,i+2],i=1,2,…,n-2, (矩阵链长度为3）…； 在计算m[i,j]时，只用到已计算的m[i,k]和m[k+1,j]; 动态规划算法的基本要素 （1）最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 （2）重叠子结构 在利用递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质 分支限界法的基本思想 分支限界法采用广度优先或最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次成为扩展结点的机会。活结点一旦成为扩展结点，就一次性产生所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被剪掉，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到满足约束条件的解或活结点表为空时为止。 分支限界法与回溯法的不同 （1）求解策略：回溯法的求解过程属于盲目搜索，而分支限界法的求解过程是有选择地朝有利于获得问题解或最优解的方向搜索。 （2）适用场合：回溯法适用于寻找满足约束条件的所有解，而分支界限法适用于寻找满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （3）搜索方式：回溯法以深度优先的方式搜索解空间树；分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。 常见的两种分支限界法 （1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个结点成为扩展结点。（队列） （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。（利用堆排序） 优先队列式分支限界法 算法从图G的源顶点s和空优先队列开始。 结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。 如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 这个结点的扩展过程一直继续到活结点优先队列为空时为止。 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。 0-1背包问题汇总 优先队列式分支限界法 算法的思想： 首先，对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在优先队列分支限界法中，结点的优先级为：由已装入的物品价值+剩余的最大单位重量价值的物品装满剩余容量的价值和。 算法处理过程： 首先检查当前扩展结点的左儿子结点是否可行。如果左儿子是可行结点，将其加入到活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入到活结点优先队列。当扩展到叶结点时得到问题的最优值。 货郎担问题 回溯法 货郎担问题的解空间是一棵排列树 令到第i层为止所构早路径的权和为：cw(i): 假设已经知道部分解（x1,x2,….,xi-1）,则从第i-1层节点选择顶点x[i]往下走的限界函数为： B(i) = cw(i-1)+w[x[i-1],x[i]] 若 B(i) ≥bestw，则停止搜索x[i]分枝及其下面 void backtrack(int i) { 1 if (i == n) { 2 if (a[x[n - 1]][x[n]] < MAX_VALUE && a[x[n]][1] < MAX_VALUE && 3 (bestc == MAX_VALUE || cc+a[x[n - 1]][x[n]]+a[x[n]][1] 4 for (int j = 1; j <= n; j++) bestx[j] = x[j]; 5 bestc = cc+a[x[n - 1]][x[n]]+a[x[n]][1]; 6 } 7 } else { for (int j = i; j <= n; j++) 8 if (a[x[i - 1]][x[j]] < MAX_VALUE && (bestc == MAX_VALUE || cc+a[x[i - 1]][x[j]] 9 swap(x, i, j); 10 cc+=a[x[i - 1]][x[i]]; 11 backtrack(i + 1); 12 cc-=a[x[i - 1]][x[i]]; 13 swap(x, i, j); } } } 算法描述： 第1行测试：如果i=n ，表示已经搜索到了叶节点。 如果从x[n-1]到x[n]以及从x[n]到起点x[1]有一条边，则找到了一条回路。 此时，第3行需要判断该回路是否是目前发现的最优回路。如果是，第4行-6行则更新回路的权和bestw 以及最优回路。 第7-13行继续回溯，在第8行，如果从x[i-1]到x[j]有一条边，且B(i)小于当前最优解的值bestw ，则表示可以继续往下搜索，同时更新目前所构造路径的权值cw 。 分支界限法 货郎担问题的解空间可以组织成一棵排列树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。 算法描述 首先，创建一个最小堆，用于表示活结点优先队列。堆中每个结点存储从根结点到该活结点的相应路径长度。 堆结点中包括： int[] x:用于记录当前解 s:结点在排序树中的层次， 从0到s 的路径为x[0:s] cc:表示当前费用 lcost ：子树费用的下界,是队列的优先级 rcost ：是x[s:n-1]中最小出边费用和 在实现过程中，用邻接矩阵表示给的图G 。每个结点的lcost 作为优先队列的优先级。 基本处理过程为： 计算图中每个顶点的最小费用出边并用minout 记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法结束，否则继续后续的处理。 分支界限法伪码 //第一个扩展结点是B while(没有到叶子结点）{ //完成对排列树内部结点的扩展。 if(扩展结点是叶子结点的父结点（n-2)){ if(有回路且更优) { 记录最优值，并将该叶结点插入到优先队列中 } } else { 依次产生当前扩展结点的所有儿子结点。 由于当前扩展结点所相应的路径是x[0:s]，其可行儿子结点从 剩余顶点x[s+1:n-1]中选取x[i]，且(x[s]，x[i])是所给有向图G 中的一条边。对于当前扩展结点的每一个可行儿子结点，如 果有可能产生更优解，将其插入优先队列中。 } 从优先队列中取下一个结点作为新的扩展结点 } Ω ()()m A n O n =(1)1(n)(1)()1O n T T n O n n ??≤=??-+>??2()()T n O n = 什么是计算机科学中所说的“算法（algorithm ）”？ 算法定义： 一个算法是一个有穷规则的集合。这些规则规定了解决某一问题的一个运算序列。同时，一个算法应该具有五个特性：有穷性、可行性、确定性、输入、输出。 1. 有穷性：规则的有限性。或者说，求解问题的运算序列，必须在有限的计算步后停止。 2. 可行性：每一计算步都是基本的、可实现的 3. 确定性：每一条规则都是明确、无二义的。 4. 0）：算法开始执行之前指定初始值。 5. 1）：算法产生与输入相关的量。二、算法的又一描述方式设：四元组（Q, I, , f ). 其中：Q:状态集合； I, Q的子集，分别代表输入和输出 f: 定义在Q之上的一个映射。且有：若q 则：f(q) = q 算法设计与分析考试题 及答案 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、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。 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算法的思想。 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(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)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性 3、算法的描述方法有几种 答：自然语言、图形、伪代码、计算机程序设计语言 4、衡量算法的优劣从哪几个方面 答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。 5、时间复杂度、空间复杂度定义 答：指的是算法在运行过程中所需要的资源（时间、空间）多少。 6、时间复杂度计算： {i=1； while（i<=n） i=i*2； } 答：语句①执行次数1次， 语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ； 7.递归算法的特点 答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件） ②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式） 8、算法设计中常用的算法设计策略 答：①蛮力法；②倒推法；③循环与递归；④分治法； ⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法 9、设计算法： 递归法：汉诺塔问题兔子序列（上楼梯问题） 整数划分问题 蛮力法：百鸡百钱问题 倒推法：穿越沙漠问题 答：算法如下： （1） 递归法 汉诺塔问题 void hanoi(int n, int a, int b, int c) {if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } } 兔子序列（fibonaci 数列 ） 递归实现： Int F(int n) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题 Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题 问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+… 将最大加数不大于m 的划分个数，记作q(n,m)。正整数n 的划分数 p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系： 递归算法： Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n 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、硬币面值组合 描述 使用1角、2角、5角硬币组成n 角钱。 设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。 输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。 输入 一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。 输出 输出有若干行，每行的形式为： i a b c 第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。 源代码： #include E说：D应该是第1名。 比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。 请编程判断5位选手各是第几名。 输入 无 输出 输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。 样例输入 样例输出 源代码： #include 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型: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 填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进 计算机算法设计与分析习 题及答案 Prepared on 24 November 2020 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 《算法设计与分析实用教程》参考解答 1-1 加减得1的数学游戏 西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。 例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。 （1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。 设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2）算法描述 // 两数若干次加减结果为1的数学游戏 #include 第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答： 因此，Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 一、填空题（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.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai算法设计与分析考试题及答案
《计算机算法设计与分析》习题及答案
中科院陈玉福计算机算法设计与分析期末简答题答案
算法设计与分析考试题及答案
算法设计与分析课后部分习题答案
算法设计与分析试卷(2010)
算法设计与分析试卷(2010)
算法设计与分析习题
计算机算法设计与分析期末考试复习题
OpenJudge算法设计与分析习题解答
算法设计与分析试卷及答案
《算法设计与分析》复习题(汇编)
计算机算法设计与分析习题及答案
算法设计与分析期末试题答案解析
《算法设计与分析实用教程》习题参考解答
算法设计与分析课后习题
算法设计与分析试卷及答案.doc
算法设计与分析试题与答案
相关主题
文本预览