湖南中医药大学 2009—2010 学年第一学期
《算法设计与分析》期末考试试卷
班级姓名学号
一、选择题（10题*2分=20分）
1.我们常用算法的最坏时间来估计算法的时间复杂性，下面（）不是这样做的原因：
A、在实际问题中，算法的运行时间常常达到这个上界。
B、平均运行时间难以计算。
C、假设每一个输入具有相同的概率有时没有意义。
D、平均运行时间与最坏运行时间有相同的数量级。
2.合并排序算法是利用（）实现的算法。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
3.下列是动态规划算法基本要素的是（）。
A、最优子结构
B、构造最优解
C、算出最优解
D、定义最优解
4.下列算法中通常以自顶向下的方式求解最优解的是（）。
A、分治法
B、动态规划法
C、贪心法
D、回溯法
5.广度优先是（）的一搜索方式。
A、分支界限法
B、动态规划法
C、贪心法
D、回溯法
6.设q（n，m）是将正整数n划分成最大加数不大于m的若干不同正整数之和的划分数，则q（n，m）为（）。
A、
1 （n=1 || m=1）
q(n, n) （n < m）
q（n，m）= 1 + q(n, n-1) （n = m）
q(n, m-2) + q(n-m,m)（n > m > 1）
B、
1 （n=1 || m=1）
q(n, n) （n < m）
q（n，m）= 1 + q(n, n-1) （n = m）
q(n, m-1) + q(n-m,m)（n > m > 1）
C、
1 （n=1 || m=1）
q(n, n) （n < m）
q（n，m）= 1 + q(n, n-1) （n = m）
q(n, m-1) + q(n-m,m-1)（n > m > 1）
D、
0 （n > 1 && m = 1）
1 （n=1）
q（n，m）= q(n, n) （n < m）
1 + q(n, n-1) （n = m）
q(n, m-1) + q(n-m,m-1)（n > m > 1）
7.计算机算法指的是解决问题的步骤序列，它必须具备（）这三个主要特性。
A、可行性、正确性、可读性
B、可行性、确定性、有穷性
C、确定性、有穷性、稳定性
D、易读性、健壮性、安全性
8.当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用（）来消除或减少问题的好坏实例间的这种差别。
A、数值概率算法
B、舍伍德算法
C、蒙特卡罗算法
D、拉斯维加斯算法
9.对于0-1背包问题和背包问题的解法，下面答案解释正确的是（）。
A 、0-1背包问题和背包问题都可以用贪心算法求解
B 、0-1背包问题可以用贪心算法求解，但背包问题则不能用贪心算法求解。
C 、0-1背包问题问题不能用贪心算法求解，但可以用动态规划和回溯法求解，而背包问题可以用贪心算法求解。
D 、因为0-1背包问题不具有最优子结构性质，所以不能用贪心算法求解。
10. 在分支限界算法中，根据从活结点表中选择下一扩展点的不同方式可以有几种常用的分类，以下描述最准确的是（ ）。
A 、 采用FIFO 队列的队列式分支限界法。
B 、 采用最小堆的优先队列式分支限界法。
C 、 采用最大堆的优先队列式分支限界法。
D 、 以上都常用，针对具体问题可以选择其中某种更为合适的方式。
二、 填空题(10题×2分=20分)
1. 算法运行所需要的计算机资源的量，称为算法复杂性，主要包括 和 。
2. f(n)=O(g(n))表示当且仅当存在正的常数C 和N 0，使得对于所有的n ， 有f(n) 。
3. 对于函数()T N ，如果存在
()T
N ，使得当N →∞时有
(()())/()0
T N T N T N -→
，就说
()T
N 是()T N 当N →∞时的 。
4. 多项式
10
()m
m A n a n a n a =+++ 的上界为 。
5. 直接或间接地调用自身的算法称为 ，用函数自身给出定义的函数称为 。
6. 动态规划算法的子问题重叠性质是指：每次产生的子问题并不是 ，有些子问题会被 。
7.贪心算法的两个基本要素是和。
8.按照活结点表的组织方式的不同，分支限界法包括和两种形式。
9.回溯法中的解空间树结构通常有两种，分别是、。
10.用分支限界法解旅行售货员问题时，对空间树搜索结束的标志是。
三、判断题(10题×2分=20分)
1.如果g(N)=O(f(N))，则O(f)+O(g)=O(f)。（）
2.所有的递归函数都能找到对应的非递归定义。（）
3.动态规划算法中，通常不同子问题的个数随问题规模呈指数级增长。（）
4.备忘录方法求解时采用与递归定义一致的自上而下的方式。（）
5.用贪心算法解0-1背包问题时，总能得到整体最优解。（）
6.利用贪心算法求解问题时，往往需要事先把问题集合按照一定原则进行排序，而活动安排问题即按活动结束时间的非减序进行排列的。（）
7.使用回溯法搜索问题的解空间树时，按照深度优先方式进行搜索，其间不受其他条件限制。（）
8.动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，二者采用的都是自底向上的计算方式（）
9.每个优化问题都是由目标函数和约束条件组成。（）
10.解空间树中，只有展开了所有子结点的结点才称为死结点。（）
四、简答题（4题×5分=20分）
1.按渐进阶从低到高的顺序排列以下表达式：n!，4n2，logn，3n，20n，2，n2/3。
2.已知矩阵A1，A2，A3，A4，A5，A6的维数分别是：5×10，10×3，3×12，12×5，5×50，50×6，求矩阵连乘A1×A2×A3×A4×A5×A6的最佳求积顺序。
3.写出贪心算法的基本设计思想。
4.分析说明分治法与动态规划法的联系与区别。
五、算法分析与设计题（2题*10分=20分）
1.对于下图使用Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对之间的最短路径的算法思想。（12分）
2.对于如下图所示的旅行售货员问题，使用优先队列式分支限界法进行求解，试构造出描述其搜索过程的状态空间树，并说明活结点表的变化情况。
习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现 在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。 #include
for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"<
习题 1 1.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707— 1783） 提出并解决了该问题。七桥问题是这样描述的：北区 一个人是否能在一次步行中穿越哥尼斯堡（现 东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区 的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草南区 图。请将该问题的数据模型抽象出来，并判断图七桥问题 此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1，一次步行 2，经过七座桥，且每次只经历过一次 3，回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个 奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到 r=0 m=n n=r r=m-n 3输出 m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代 码和 C++描述。 编写程序，求 n 至少为多大时， n 个“1”组成的整数能被2013 整除。 #include
for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n 至少为 :"<
一 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．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采
HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日
一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。
《计算机算法设计与分析》习题及答案 一．选择题 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卷） 2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120 分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log2n C．2n2 D．3nlog3n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨牌 的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法 对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同
6. 有9个村庄，其坐标位置如下表所示： 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。 A ．（4.5，0） B ．（4.5，4.5） C ．（5，5） D ．（5，0） 7. n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下 说法不正确？ A ．让水桶大的人先打水，可以使得每个人排队时间之和最小 B ．让水桶小的人先打水，可以使得每个人排队时间之和最小 C ．让水桶小的人先打水，在某个确定的时间t 内，可以让尽可能多的人打上水 D ．若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样 8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分 别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 A ．问题规模相同，问题性质相同 B ．问题规模相同，问题性质不同 C ．问题规模不同，问题性质相同 D ．问题规模不同，问题性质不同 9. 对布线问题，以下 是不正确描述。 A ．布线问题的解空间是一个图 B ．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定 C ．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的 D ．采用先入先出的队列作为活结点表，以终点b 为扩展结点或活结点队列为空作为算法结束条件 10. 对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。 A ．n! B ．2n C ．2n+1 -1 D ．∑=n i i n 1 !/! 答案：DACAD CACCB
第一章 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)). 第二章 算法分析题
算法设计与分析的复习要点 第一章：算法问题求解基础 算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 一．算法的五个特征： 1．输入：算法有零个或多个输入量； 2．输出：算法至少产生一个输出量； 3．确定性：算法的每一条指令都有确切的定义，没有二义性； 4．可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现； 5．有穷性：算法必须总能在执行有限步之后终止。 二．什么是算法？程序与算法的区别 1．笼统地说，算法是求解一类问题的任意一种特殊的方法；较严格地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 2．程序是算法用某种程序设计语言的具体实现；算法必须可终止，程序却没有这一限制；即：程序可以不满足算法的第5个性质“有穷性”。 三．一个问题求解过程包括：理解问题、设计方案、实现方案、回顾复查。 四．系统生命周期或软件生命周期分为： 开发期：分析、设计、编码、测试；运行期：维护。 五．算法描述方法：自然语言、流程图、伪代码、程序设计语言等。 六．算法分析：是指对算法的执行时间和所需空间的估算。算法的效率通过算法分析来确定。 七．递归定义：是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分：基础情况和递归部分； 基础情况：以直接形式明确列举新事物的若干简单对象； 递归部分：有简单或较简单对象定义新对象的条件和方法 八．常见的程序正确性证明方法： 1.归纳法：由基础情况和归纳步骤组成。归纳法是证明递归算法正确性和进行算法分析的强有力工具； 2.反证法。 第二章：算法分析基础 一．会计算程序步的执行次数（如书中例题程序2-1,2-2,2-3的总程序步数的计算）。二．会证明5个渐近记法。（如书中P22-25例2-1至例2-9） 三．会计算递推式的显式。（迭代法、代换法，主方法） 四．会用主定理求T(n)=aT(n/b)+f(n)。（主定理见P29，如例2-15至例2-18）五．一个好的算法应具备的4个重要特征： 1.正确性：算法的执行结果应当满足预先规定的功能和性能要求； 2.简明性：算法应思路清晰、层次分明、容易理解、利于编码和调试； 3.效率：算法应有效使用存储空间，并具有高的时间效率； 4.最优性：算法的执行时间已达到求解该类问题所需时间的下界。 六．影响程序运行时间的主要因素： 1.程序所依赖的算法； 2.问题规模和输入数据规模； 3.计算机系统性能。 七．1.算法的时间复杂度：是指算法运行所需的时间；
Ex.1(p20)若将y ← uniform(0, 1) 改为 y ← x, 则上述的算法估计的值是什么？ 解：若将y ←uniform(0, 1) 改为 y ←x，此时有 ，则k++，即 ，此时k++，由于此时x ← uniform(0, 1)，所以k/n=，则此时4k/n=2。所以上述算法估计的值为2。 Ex.2(p23) 在机器上用 估计π值，给出不同的n值及精度。 解：由ppt上p21可知，的大小 ，其中k为落入圆内的数目，n为总数，且π=，即需要计算4k/n。我们先令x ← uniform(0, 1)，y ← uniform(0, 1)。 计算的值，如果小于等于1，那么此时k++。最后计算4k/n的值即可估计此时的π值。代码的主要部分为： 执行结果为：
结果分析：随着N的取值不断地增加，得到的π值也就越来越精确。 Ex.3(p23) 设a, b, c和d是实数，且a ≤ b, c ≤ d, f:[a, b] → [c, d]是一个连续函数，写一概率算法计算积分： 注意，函数的参数是a, b, c, d, n和f, 其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。 解：的值为y=，y=0，x=a，x=b围成的面积。根据之前的例子我们可以知道= k(b-a)d/n。其中k是落在函数y=，x=a，x=b以及y=0所包围区间内的个数。 代码的主要部分为： 运行结果为：
结果分析： 随着N的取值不断地增加，得到的积分值越来越精确。 Ex4(p24). 设ε,δ是(0,1)之间的常数，证明：若I是的正确值，h是由HitorMiss算法返回的值，则当n ≥ I(1-I)/ε2δ时有： Prob[|h-I| < ε] ≥ 1 –δ 上述的意义告诉我们：Prob[|h-I| ≥ε] ≤δ, 即：当n ≥ I(1-I)/ ε2δ时，算法的计算结果的绝对误差超过ε的概率不超过δ，因此我们根据给定ε和δ可以确定算法迭代的次数 () 解此问题时可用切比雪夫不等式，将I看作是数学期望。 证明：由切比雪夫不等式可知： P( | X - E(X) | < ε ) ≥ 1 - D(X) / ε2 由题目知，E(X)=I。且根据题意，我们可知，在HotorMiss算法中，若随机选取n个点，其中k个点在积分范围内，则 。且k的分布为二项分布B(n，I)（在积分范围内或者不在 积分范围内），则 。又因为k=x*n，所以D(X)=I(1-I)/n。再将E(X)和D(X)带入切比雪夫不等式中即可得到 Ex5(p36). 用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。 解：由题知，集合的大小，通过计算新生成的集合中元素的个数来估计原集合的大小，代码的主体部分如下：
1.15练习 1.1（a） 1)A[1…60] = A[(1+60)/2]=A[30]=40 由于33<40，舍弃A[30…60]; 2)A[1…29] = A[(1+29)/2]=A[15]=25 由于33>25，舍弃A[1…15]; 3) A[16…29]= A[(16+29)/2]=A[22]=32 由于33>32，舍弃A[16…22]; 4) A[23…29] = A[(23+29)/2]=A[26]=36 由于33<36，舍弃A[26…29]; 5) A[23…25] = A[(23+25)/2]=A[24]=34; 由于33<34，舍弃A[24, 25]; 6) A[23] = 11 12 13 … 68 69 70 11 12 13 … 37 38 39 26 27 28 … 37 38 39 33 34 35 36 37 38 39 33 34 35 33
由于33=33，搜索完毕。 综上，搜索33共执行了6次比较。 同理可得（b ）搜索7共执行了5次比较。 （c ）搜索70共执行了6次比较。 （d ）搜索77共执行了6次比较。 1.10 对11 12 1 5 15 3 4 10 7 2 16 9 8 14 13 6用bottomupsort 算法，按非降序排列。 解：用图示，如下进行。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 3 4 5 10 11 12 15 1 5 11 1 2 1.15用Θ表示函数。 (b) 2 6 7 8 9 1 3 1 4 16 3 4 10 1 5 2 7 9 1 6 6 8 13 14 11 12 1 5 15 3 4 10 2 7 9 16 8 14 6 13
第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环） 若考虑其他语句，则没有这么多，可能就601倍。 第二章 32P 2-8.（1）画线语句的执行次数为log n ??? ?。(log )n O 。划线语句的执行次数应该理解为一格整体。 （2）画线语句的执行次数为 111 (1)(2)16 j n i i j k n n n ===++= ∑∑∑。3 ()n O 。 （3）画线语句的执行次数为 。O 。 （4）当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++， 当n 为偶数时画线语句的执行次数为 2(2)4 n +。2 ()n O 。 2-10.（1） 当 1n ≥ 时，225825n n n -+≤，所以，可选 5c =，01n =。对于0n n ≥， 22()5825f n n n n =-+≤，所以，22582()n n n -+=O 。 （2） 当 8n ≥ 时，2222582524n n n n n -+≥-+≥，所以，可选 4c =，08n =。对于0n n ≥， 22()5824f n n n n =-+≥，所以，22582()n n n -+=Ω。 （3） 由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以2 2 582()n n n -+=Θ。 2-11. (1) 当3n ≥时，3 log log n n n <<，所以()20log 21f n n n n =+<，3 ()log 2g n n n n =+>。可 选 21 2 c = ，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。
算法设计与分析教师讲稿
第1章
教学重点 教学难点 计算机学科的符号化特征 知识点 教学内容 和 教学目标 算法及其重要特性 算法的描述方法 算法设计的一般过程 问题求解的一般过程 计算机学科的符号化特征 重要的问题类型
算法设计基础
算法及其重要特性；伪代码；算法设计的一般过程 教学要求 了解 理解 √ √ √ √ √ 掌握 熟练掌握 √
1.1
1.1.1 算法及其重要特性
算法的基本概念
算法是计算机科学的基石。其定义为： 算法是对特定问题求解步骤的一种描述，是指令的有限序列。 算法五个重要特性： （1）输入：一个算法有零个或多个输入（即算法可以没有输入），这些 输入通常取自于某个特定的对象集合。 （2）输出：一个算法有一个或多个输出（即算法必须要有输出），通常 输出与输入之间有着某种特定的关系。 （3）有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之 后结束，且每一步都在有穷时间内完成。 （4）确定性：算法中的每一条指令必须有确切的含义，不存在二义性。 并且，在任何条件下，对于相同的输入只能得到相同的输出。 （5）可行性：算法描述的操作可以通过已经实现的基本操作执行有限次 来实现。
输入 算法：操作步骤 满足确定性、有穷性、可行性 图 1.1 算法的概念 .1 算法的概念 输出
算法的中文名称出自周髀 算 经 , 英 文 (algorithm) 则 来自于波斯数学家阿勒·霍 瓦里松(Al·Khowarizmi)在 公元 825 年写的经典著作 《代数对话录》。 算法中有穷的概念不是纯 数学的， 而是指在实际应用 中是合理的、可接受的。 算法的确定性限制了它所 能够解决的问题种类。
例 1.1 设计算法求两个自然数的最大公约数。 解：设两个自然数是 m 和 n，求解过程如下：
1
实验内容 一、实验内容 1)狼找兔子问题：一座山周围有n个洞，顺时针的编号为0,1,2,3,4，...，n-1,。 一只狼从0号洞开始，顺时针方向计数，每当经第m个洞时，就进洞找兔子。例如n=5，m=3，狼经过的洞依次为0, 3, 1, 4, 2, 0。输入m，n。试问兔子有没有幸存的机会？如果有应该藏在哪儿？ 问题分析：设置两个数组，一个数组用于循环，演示狼每次经过的洞，如果每个洞都被经过，则兔子没有幸存的机会。如果最后经过的洞的数目小于总的数目，则比较两个数组，数组中不同的值代表被狼经过的洞，相同的值代表兔子可以藏身的洞。本题使用C++编写。 实验代码：
运行结果：
2)有52张牌，使它们全部正面朝上。第一轮是从第2张开始，凡是2的倍数 位置上的牌翻成正面朝下，第二轮从第3张牌开始，凡是3的倍数的牌，正面朝上的翻成正面朝下，正面朝下的牌翻成正面朝上。第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同的规则反转，以此类推，直到翻过的牌超过104张为止。统计最后有几张牌正面朝上，以及它们的位置号。 问题分析：设置一个数组，数组中每一个数的初始值都为1，当某张牌被翻转的时候，用0表示。每翻转一次，用一个变量count累计加1，然后检查变量的值，当count超过104的时候，跳出循环体。本题使用Java编写。 实验代码：
运行结果： 3)A,B,C,D,E5人为某次竞赛的前五名，他们在名次公布前猜名次。A说：B得第三名，C得第五名。 B说：D得第二名，E得第四名。 C说：B得第一名，E得第四名。
D说：C得第一名，B得第二名。 E说：D得第二名，A得第三名。 结果每个人都猜对了一般，实际名次是什么呢？ 问题分析：本题使用多重嵌套循环，ABCDE每个人可能获得的名次分别是1,2,3,4,5，分别使ABCDE遍历每一种可能，当每个人的两个预言只有一个为真时，循环结束。本题使用C++编写。 实验代码： 运行结果：
《算法设计与分析》习题 第一章引论 习题1-1 写一个通用方法用于判定给定数组是否已排好序。 解答： Algorithm compare(a,n) Begin J=1; While (j
习题2-1 求下列函数的渐进表达式： 3n 2+10n ; n 2/10+2n ; 21+1/n ; log n 3; 10 log3n 。 解答： 3n 2+10n=O （n 2）， n 2/10+2n =O （2n ）， 21+1/n=O （1）， log n 3=O （log n ），10 log3n =O （n ）。 习题2-2 说明O (1)和 O (2)的区别。 习题2-3 照渐进阶从低到高的顺序排列以下表达式：!n ， 3/22,2,20,3,log ,4n n n n n 。 解答：照渐进阶从低到高的顺序为：!n 、 3n 、 2 4n 、23 n 、20n 、log n 、2 习题2-4 （1） 假设某算法在输入规模为n 时的计算时间为n n T 23)(?=。在某台计算机 上实现并完成该算法的时间为t 秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t 秒内能解输入规模为多大的问题？ （2） 若上述算法的计算时间改进为2)(n n T =，其余条件不变，则在新机器上用 t 秒时间能解输入规模多大的问题？ （3） 若上述算法的计算时间进一步改进为8)(=n T ,其余条件不变，那么在新机 器上用t 秒时间能解输入规模多大的问题？ 解答： （1） 设新机器用同一算法在t 秒内能解输入规模为1n 的问题。因此有 64/23231n n t ?=?=，解得61+=n n 。 （2） n n n n 8641221==>=。 （3） 由于=)(n T 常数，因此算法可解任意规模的问题。 习题2-5 XYZ 公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC 公司同类产品的100倍。对于计算复杂性分别为n ，2n ，3n 和!n 的各算法，若用ABC 公司的计算机能在1小时内能解输入规模为n 的问题，那么用XYZ 公司的计算机在1小时内分别能解输入规模为多大的问题？
常用算法设计方法 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0； （2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)；/*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)； printf(“方程的近似根是%f\n”，x0)； } 迭代算法也常用于求方程组的根，令 X=（x0，x1，…，x n-1） 设方程组为：
算法分析与设计（2003秋） 宋斌恒?本课程的教学目的： 1．理论分析目标：通过本课程的学习，使学生掌握算法分析与设计的基本理论和内容，了解和掌握一定数量的基本算法，具有设计新算法和分析复杂性的能力 2．实践目标：学会用这些算法解决实际问题，并能实际编程实现。 3．团队合作能力培养：通过团队完成作业来培养大家的团队合作能力 4．交流能力的培养：通过本课程学习和实践，培养大家的交流能力和表达能力 5．自学能力：知识的自我更新能力和阅读理解能力6．独立研究能力：能够独立研究问题的能力：即发现问题、分析问题、解决问题的能力。 ?预修课程： –1.数据结构（没修过的请修过后再选） 2.掌握一门对面向对象编程语言（C＋＋或Java） 关于自主完成作业： ? 要独立完成。可以参考各种文献、著作、教材和其它同学的作业，但必须指明出处。文献、著作、教材类公开出版的参考资料，按照文献索引方式引用。网络资料，除指出网络路径URL，还应当提供资料拷贝。参考同学作业应当指出作业编号和提供原作业拷贝。多人讨论的成果，应当在作业中反映。凡是引用他人成果而没有指出出处的以抄袭论处，一旦发现抄袭，该课程以0分记，并在此网络上公布。 教学网站?清华大学网络学堂 主要参考书 –Introduction to algorithms, Thomas H. Cormen, etc., second edition, The MIT Press. –The Art of Computer Programming, Donald E. Knuth. Volume 1-3, Second Edition. –Data Structures, Algorithms, and Applications in C++(Part 3) Sartaj Sahni, China Machine Press –算法设计与分析，王晓东，清华大学出版社
第一章算法概述 1、算法的五个性质：有穷性、确定性、能行性、输入、输出。 2、算法的复杂性取决于：（1）求解问题的规模（N）,（2）具体的输入数据（I），（3）算法本身的设计（A），C=F(N,I,A)。 3、算法的时间复杂度的上界记号O， 下界记号Ω(记为f(N) = Ω(g(N))。即算法的实际运行时间至少需要g(n)的某个常数倍时间)， 同阶记号Θ：f(N)= Θ(g(N))表示f(N)和g(N)同阶。 即算法的实际运行时间大约为g(n)的某个常数倍时间。 低阶记号o：f(N)=o(g(N))表示f(N)比g(N)低阶。 多项式算法时间： O(1) 湖南中医药大学 2009—2010 学年第一学期 《算法设计与分析》期末考试试卷 班级姓名学号 一、选择题（10题*2分=20分） 1.我们常用算法的最坏时间来估计算法的时间复杂性，下面（）不是这样做的原因： A、在实际问题中，算法的运行时间常常达到这个上界。 B、平均运行时间难以计算。 C、假设每一个输入具有相同的概率有时没有意义。 D、平均运行时间与最坏运行时间有相同的数量级。 2.合并排序算法是利用（）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 3.下列是动态规划算法基本要素的是（）。 A、最优子结构 B、构造最优解 C、算出最优解 D、定义最优解 4.下列算法中通常以自顶向下的方式求解最优解的是（）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 5.广度优先是（）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 6.设q（n，m）是将正整数n划分成最大加数不大于m的若干不同正整数之和的划分数，则q（n，m）为（）。 A、 1 （n=1 || m=1） q(n, n) （n < m） q（n，m）= 1 + q(n, n-1) （n = m） q(n, m-2) + q(n-m,m)（n > m > 1） B、 1 （n=1 || m=1） q(n, n) （n < m） q（n，m）= 1 + q(n, n-1) （n = m） q(n, m-1) + q(n-m,m)（n > m > 1） C、 1 （n=1 || m=1） q(n, n) （n < m） q（n，m）= 1 + q(n, n-1) （n = m） q(n, m-1) + q(n-m,m-1)（n > m > 1） D、 0 （n > 1 && m = 1） 1 （n=1） q（n，m）= q(n, n) （n < m） 1 + q(n, n-1) （n = m） q(n, m-1) + q(n-m,m-1)（n > m > 1） 7.计算机算法指的是解决问题的步骤序列，它必须具备（）这三个主要特性。 A、可行性、正确性、可读性 B、可行性、确定性、有穷性 C、确定性、有穷性、稳定性 D、易读性、健壮性、安全性 8.当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用（）来消除或减少问题的好坏实例间的这种差别。 A、数值概率算法 B、舍伍德算法 C、蒙特卡罗算法 D、拉斯维加斯算法 9.对于0-1背包问题和背包问题的解法，下面答案解释正确的是（）。算法设计与分析(1)
相关主题
文本预览