算法(Algorithm)有限性：每条指令的执行次数、时间有限；确定性：每条指令有确定的含义、无歧义；输入：0个或多个输入；输出：1个或多个输出；有效性。
程序：是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。
算法涵盖的主要元素：数据、运算设计算法的基本原则：自顶向下逐步求精。
设计算法的基本过程：分析问题域，确定数学模型；整理初始状态与结果状态之间的隐含关系，寻求从数学模型已知初始状态到达结果状态的运算步骤。
抽象数据类型（ADT）= 数学模型+运算ADT=(D,S,P)数据对象、数据关系、基本操作
算法复杂性是算法运行所需要的计算机资源量，时间资源量称为时间复杂性，空间资源量称为空间复杂性。这些量只依赖于算法所要求解问题的规模、算法的输入和算法本身。
空间复杂性的组成：指令空间(编译之后的程序指令)数据空间(常量、变量)栈空间(函数调用)
指令空间的大小对特定问题不敏感。算法分析方法：概率分析；分摊分析；实验分析
分治算法能解决问题特征：缩小问题规模可以降低解决问题的难度；可以将子问题的解合并为原问题解；问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
替换方法解递归方程步骤：猜测出递归解的形式；用数学归纳法找出使解真正有效的常数
递归树方法基本步骤：利用递归树推测出一个解；利用替换方法进行证明
分治算法的特征：将较大规模的问题分解为若干个较小规模的子问题，每个子问题的求解过程与原问题一样，并利用自底向上的求解策略得到最终的解。
直接或间接地调用自身的算法称为递归算法。在定义函数时调用到函数自身称为递归函数。
边界条件与递归方程是递归函数的二要素。递归优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
贪心算法设计思路：总是做出在当前看来最好的选择，即贪心算法并不是从整体最优考虑，它所做的选择只是在某种意义上的局部最优选择。前提：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
贪心算法与动态规划算法的差异：动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。背包、活动安排、最优装载、单源最短路径问题。
一、算法时间复杂性问题
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的定义，存在正常数C1，C2和自然数N1,N2，使得对所有的n>= N1，f（n）<=C1s(n)；对所有的n>= N2,g(n) <=C2r(n)
所以 f（n）+ g(n) <= C1s(n)+ C2r(n)，f（n）*g(n)<= C1C2s(n)r(n)；
令 C3=max（C1,C2），C4=C1*C2；
则：f（n）+ g(n) <= C3[s(n)+ r(n)]=O(s(n)+ r(n))
f（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)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即，零次多项式)来限Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n n)
界，而一个时间为Ο(n 2)的算法则由一个二次多项式来限界。以下六种计算时间的多项式时间算法是最为常见的，其关系为
指数时间算法一般有Ο(2n )、Ο(n!)和Ο(n n )等。其关系为： 其中，最常见的是时间为Ο(2n )的算法。当n 取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊因
为根本就找不到一个这样的m ，使得2n 囿界于n^m 。换言之，对于任意的m ≥0，总可以找到n 0，当n ≥n 0时，有2
n ＞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. “当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质”。问题的最优子结构性质是该问题可用动态规划算法求解的基本要素，试简要阐述“论证某一问题的最优子结构性质”时的一般方法；矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）例如：假设（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）是最优解，由此可知，
这说
Ο(2n )＜Ο(n!)＜Ο(n n )
明（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] 当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) = ? log 2 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 ，然后，依贪心选择策略，将尽可能多的单位重量价值最高∑=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),(从m(i,j)的递归式容易看出，算法需要O （nc ）计算时间。当背包容量c 很大时，算法需要的时间较多。例如，当c>2^n 时，算法需要欧米伽（n2^n ）计算时间。 的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 最优装载问题照着这个代码完全可以写出来！ 动态规划经典问题： 证明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 的新的特殊路径。 这条新的特殊路径由两种可能： 这条路径先由源点到达顶点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 = 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+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. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 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.以深度优先方式系统搜索问题解的算法称为_____________。 背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。? 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 算法设计与分析试卷(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 算法设计与分析实验报告 姓名：888 学号：129074999 老师：许精明 实验1：杨辉三角 解法思路： 根据杨辉三角中除最外层（不包括杨辉三角底边）的数为1外，其余的数都是它肩上两个数之和这一性质，用数组输出杨辉三角。 根据杨辉三角的第n行恰好是C(n,0)~C(n,n)，可以不用数组输出，而用动态规划。这里的C表示组合。 注：由于为了便于控制输出格式，程序中的最大输出行确定的较小，但程序本身并没有错误。若要输出更多行，需要增加控制输出格式的语句。 解法一：数组 #include 一 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、二分搜索算法是利用（ 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 ）。 算法分析与设计 学习总结 题目:算法分析与设计学习总结 学院信息科学与工程学院专业2013级计算机应用技术 届次 学生姓名 学号2０１31１0６57 二○一三年一月十五日 算法分析与设计学习总结 本学期通过学习算法分析与设计课程，了解到:算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。 设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。(2)确定性。算法的每一个步骤必须有确切的定义。(3)输入。一个算法有0个或多个输入,作为算法开始执行前的初始值，或初始状态。(4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 (5)可行性。在有限时间内完成计算过程。 算法设计的整个过程,可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。 经典的算法主要有: 1、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，bing从中找出那些符合要求的候选解作为问题的解。 穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举书来的情况数目会大得惊人，就是用高速计算机运行,其等待运行结果的时间也将使人无法忍受。我们在用穷举算法解决问题是，应尽可能将明显不符合条件的情况排除在外，以尽快取得问题的解。 2、迭代算法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或方程组)的过程，为实现这一过程所使用的方法统称为迭代法。迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为ｆ(ｘ)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0。 (2)将ｘ0的值保存于变量x1，然后计算g(x1),并将结果存于变量x0。 (3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（２）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。 3、递推算法 递推算法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系,从而达到目的。 4、递归算法 递归算法是一种直接或间接的调用自身的算法。 能采用递归描述的算法通常有这样的特征：为求解规模为ｎ的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型: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.1 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d 能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 算法设计技巧与分析 答案 算法设计技巧与分析 参考答案 第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 。 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： 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. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 算法设计与分析 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分） 一、填空题（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 《算法分析与设计》期末复习题 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座B 上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi 塔问题的移动规则。由此设计出解Hanoi 塔问题的递归算法正确的为：（B ） Hanoi 塔 A. void hanoi(int n, int A, int C, int B) { if (n > 0) { hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); } B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } 3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O表示（B），记号Ω表示（A），记号Θ表示（D）。 A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A） A.f(n)(g(n)),g(n)(h(n))f(n)(h(n)) =Θ=Θ?=Θ B. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n)) ==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f(n)O(g(n))g(n)O(f(n)) =?= 6.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 【题目1】N皇后问题(八皇后问题的扩展) 【题目2】排球队员站位问题 【题目3】把自然数Ｎ分解为若干个自然数之和 【题目4】把自然数Ｎ分解为若干个自然数之积 【题目5】马的遍历问题 【题目6】加法分式分解 【题目7】地图着色问题 【题目8】在n*n的正方形中放置长为2,宽为1的长条块 【题目9】找迷宫的最短路径。（广度优先搜索算法） 【题目10】火车调度问题 【题目11】农夫过河 【题目12】七段数码管问题。 【题目13】把1-8这8个数放入下图8个格中,要求相邻的格(横,竖,对角线)上填的数不连续 【题目14】在4×4的棋盘上放置8个棋,要求每一行,每一列上只能放置2个 【题目15】迷宫问题.求迷宫的路径.(深度优先搜索法) 【题目16】一笔画问题 【题目17】城市遍历问题 【题目18】棋子移动问题 【题目19】求集合元素问题（1,2x+1,3X+1类) 【题目1】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行，每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。 const max=8; var i,j:integer; a:array[1..max] of 0..max; {放皇后数组} b:array[2..2*max] of boolean;{/对角线标志数组} c:array[-(max-1)..max-1] of boolean; {\对角线标志数组} col:array[1..max] of boolean; {列标志数组} total:integer; {统计总数} procedure output; {输出} var i:integer; begin write('No.':4,'[',total+1:2,']'); for i:=1 to max do write(a[i]:3);write(' '); if (total+1) mod 2 =0 then writeln; inc(total); end; function ok(i,dep:integer):boolean; {判断第dep行第i列可放否} begin ok:=false; if ( b[i+dep]=true) and ( c[dep-i]=true) {and (a[dep]=0)} and (col[i]=true) then ok:=true算法设计及分析递归算法典型例题
算法设计与分析考试题及答案
中科院陈玉福计算机算法设计与分析期末简答题答案
算法设计与分析考试题及答案
算法设计与分析试卷(2010)
算法设计与分析
算法设计与分析复习资料1
算法设计与分析试卷(2010)
计算机算法设计与分析期末考试复习题
算法设计与分析学习总结
算法设计与分析试卷及答案
算法设计与分析基础习题参考答案
算法设计与分析期末试题答案解析
算法设计技巧与分析答案上课讲义
算法设计与分析试卷及答案.doc
算法设计与分析试卷及答案
算法设计与分析试题与答案
算法设计与分析考试题目及复习资料
算法设计与分析的经典问题
相关主题
文本预览