《算法设计与分析》由会员分享，可在线阅读，更多相关《算法设计与分析（10页珍藏版）》请在金锄头文库上搜索。
1、、名词解释1. 算法评价的主要标准算法的时间复杂度：针对问题指定基本运算，计数算法所做的基本运算次数2. 时间和空间复杂度算法复杂度分为时间复杂度和空间复杂度。其作用:时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）3. P和NP类问题所有多项式时间可解的判定问题组成的问题类称作p类.由所有多项式时间可验证的判定问题组成的问题类称作NP类4. 数学建模当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究
2、、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语 言，把它表述为数学式子，也就是数学模型，然后用通过计算得到的模型结果来 解释实际问题，并接受实际的检验。这个建立数学模型的全过程就称为数学建模。5. 分而治之算法分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法（divide-and-conquer ）的基本思想：分治法的求解过程由以下三个阶段组成：（1） 划分：把规模为n的原问题划分为k个规模较小的子问题， 并尽量使这k个子问题 的规模大致相同。（2） 求解子问题：各子问题的解法与原问题的解法通常是相同的，可
3、以用递归的方法求 解各个子问题，有时递归处理也可以用循环来实现。（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。6. 贪婪算法贪心算法又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，以逐步的局部最 优，达到最终的全局最优。7. 动态规划设计动态规划算法的步骤 （1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解8. 蛮力算法利用枚举所有的情况，或者其它大量运算又不用技巧的方式，来求解问题的方法。9. 回溯法它是一种系统地搜索问
4、题的解的方法回溯法的基本思想：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间 结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。10. 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩 展结点，就一次性产生其所有儿子结点。 在这些儿子结点中，导致不可行解或导 致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。常见的两种分支限界
5、法(1) 队列式(FIFO)分支限界法按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。(2) 优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。11. 概率算法算法在执行的过程中随机选择下一个计算步骤，概率算法大致分为四类 ：数值概 率算法，蒙特卡罗(Monte Carlo )算法，拉斯维加斯(Las Vegas)算法和舍伍 德(Sherwood)算法。二、计算时间复杂度(以下T(1)=1)1.有语句：for(i=1 ; i=n ; i+)for(j=1; jv=n ; j+)for(k=1; k0。根据递归树计算方式, 有：kT(n)= aT(n/
6、b)+n k 。T(n/b)= aT(n/b 2)+(n/b) k 。T(n/b 2)= aT(n/b 3)+( n/b 2) k 。于是得到：T(n)= nk (1+ a/ b k + (a/ b k)2 + (a/ b k)3 + + (a/ b k)h), h=log bn。1 ： log ba=k这种情况下 a/ bk= 1，显然 T(n)= O(nk log bn)。2: log bak此时等比数列公比不是 1 ，根据等比数列求和公式化简得到：kxkT(n)=( n n )/(1-a/b) , x=log ba。如果 log bak，则 T(n)= O(nx)。 x=log ba。解
7、答 ：由题 k=1, a=1 b=2 x=log ba=0。由上可得 T(n)=2n = O(n)4 T(n)=T(n/3)+T(2n/3) 求 T(n)使用递归树求n2n33/n2n2n4n999910(n)层数 k:n (2/3) k = 1 = (3/2) k=nk=log3/2 nT(n)=C(log n)5. T(n)=2T(n/2)+2求 T(n)川- (以下的W为T)W(n) = 2W(2t1) + 2= 22FF(2A 2) + 2 + 2= 22FF(2i) + 22+2=22炉(27) + 2 + 24=2*FK(1) +(X + 2t_1 + 2*-2 + + 2)6.
8、i=1;while(i n)i=i*2;T( n)=n/2二、计算与写结果1. 有1000个苹果，10个箱子,怎么个放法，不 管想拿多少个苹果，都能成箱成箱地拿？按照2的k次方来放 箱子中分别放1 2 4 8 16 32 64 128 256 4892 .有512个数，要找最大和最小数，至少要比 较多少次？参考：1 .将n个元素两两一组分成 _n/2组2 .每组比较，得到一n/2 个较小和lln/2 个较大3 .在 n/2 个(n为奇数，是ILn/2 +1)较小中找最小min4 .在 n/2 个(n为奇数，是ILn/2 +1)较大中找最大 max复杂性：行2比较一n/2 次，行3-4比较至多2
9、 n/2 -2次，vyn) = 一n/2 +2 n/2 -2 二 n + n/2 -2 = 3n/2 -23. 核反应堆中有a和B两种粒子，每秒钟内一 个a粒子可以反应产生3个3粒子，而一个3粒 子可以反应产生1个a粒子和4个3粒子。若在 t=0时刻的反应堆中只有一个a粒子，求在t时 刻的反应堆中a粒子和3粒子数。参考：4. 给定关键字序列(8 , 2, 16, 30, 8, 28, 4, 10, 20, 6, 18)，分别写出用以下排序方法进行 排序后的第一趟排序的比较次数。(1)插入排序希尔排序冒泡排序快速 排序(5)归并排序5. 楼梯上有n阶台阶，上楼时可以一步上一阶， 也可以一步上两阶
10、，也可以一步上三阶，请分析 共有多少种不同的上楼梯方法。抽象 f(n)=f(n-3)+f(n-2)+f(n-1) f(1)=1 f(2)=2 f(3)=46. 汉诺塔问题(1) 递归思想(2) 移动次数算法1.3 Hanoi( A C n)/将A的n个盘子按要求移到C1. if n =1 then move (AC) / 将 A 的 1 个盘子移到 C2. else Hanoi( A B n-1)3. move( A C)4. Hanoi( B, C n-1)T(n) = 2T(n-1) + 1 , T(1) = 1，迭代解得T(n) = 2 n -17. FFD装箱问题降序首次适应算法 (F
11、FD) ：先对物品按降序排序，再按照首次适应算法进行装箱四、写出算法1对于给定的 n 个元素的数组 a0:n-1 ，要求 从中找出第 k 小的元素。2. 54 张扑克牌，两个人轮流拿牌，每人每次最 少取 1 张，最多取 4张，谁拿最后一张谁输。编 写模拟计算机先拿牌且必胜的算法。3用一辆吉普车穿越 1000 公里的沙漠。吉普车 的总装油量为 500加仑，耗油率为 1 加仑/公里。 由于沙漠中没有油库， 必须先用这辆车在沙漠中 建立临时油库。 该吉普车以最少的耗油量穿越沙 漠，应在什么地方建油库，以及各处的贮油量。4狼找兔子问题：一座山周围有n 个洞，顺时针编号为0,1,2,3,4,。，n-1。
12、一只狼从0号洞开始，顺时针方向计数，每当经过第 m个洞时，就进洞找兔子。例如：n=5,m=3,狼经过胡洞依此 为 0,3,1,4,2,0.5 .递归求n个元素(n=2k)最大和最小元素6 矩阵 A30*1*A1*40*A40*10*A10*25m11=0m12=m13=m14=m22=0m23=m24=m33=0m34=m44=07.用分治法实现大整数相乘的算法思想与T(n)五、编写程序1 数组中有n个数据，要将它们顺序循环向后 移或向前k位，即前面的元素向后移或向前k位, 后面的元素则循环向前移 k 位或向前移 k 位，例： 1、2、3、4、5 循环移 3 位后为： 3、4、5、1、2 请编程实现。2用递归实现整数的划分问题：对于一个正整数n的划分，就是把n表示成一系列正整数之和的表达式。例：对于正整数n=5,可以划分为：54 13 2,3 1 12 21,2 1111 1 1 1 1(1)请写出对正整数n=6的划分情况(2) 利用公式Q(n,n)=1+Q(n,n-1);Q(n,m)=Q(n,m-1)+Q(n-m,m) (mn); Q(n,1)=1; Q(1,m)=1 。编写递归程序计算正整数 n 的划分数 ( 其中 Q(n,m) 表示整数 n 的“任何加数都不超过 m” 的划分数目， n 的划分数目表示为 Q(n,n)
