算法设计与分析1

算法设计与分析教师讲稿
第1章
教学重点 教学难点 计算机学科的符号化特征 知识点 教学内容 和 教学目标 算法及其重要特性 算法的描述方法 算法设计的一般过程 问题求解的一般过程 计算机学科的符号化特征 重要的问题类型
算法设计基础
算法及其重要特性；伪代码；算法设计的一般过程 教学要求 了解 理解 √ √ √ √ √ 掌握 熟练掌握 √
1.1
1.1.1 算法及其重要特性
算法的基本概念
算法是计算机科学的基石。其定义为： 算法是对特定问题求解步骤的一种描述，是指令的有限序列。 算法五个重要特性： （1）输入：一个算法有零个或多个输入（即算法可以没有输入），这些 输入通常取自于某个特定的对象集合。 （2）输出：一个算法有一个或多个输出（即算法必须要有输出），通常 输出与输入之间有着某种特定的关系。 （3）有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之 后结束，且每一步都在有穷时间内完成。 （4）确定性：算法中的每一条指令必须有确切的含义，不存在二义性。 并且，在任何条件下，对于相同的输入只能得到相同的输出。 （5）可行性：算法描述的操作可以通过已经实现的基本操作执行有限次 来实现。
输入 算法：操作步骤 满足确定性、有穷性、可行性 图 1.1 算法的概念 .1 算法的概念 输出
算法的中文名称出自周髀 算 经 , 英 文 (algorithm) 则 来自于波斯数学家阿勒·霍 瓦里松(Al·Khowarizmi)在 公元 825 年写的经典著作 《代数对话录》。 算法中有穷的概念不是纯 数学的， 而是指在实际应用 中是合理的、可接受的。 算法的确定性限制了它所 能够解决的问题种类。
例 1.1 设计算法求两个自然数的最大公约数。 解：设两个自然数是 m 和 n，求解过程如下：
1

算法设计与分析教师讲稿
第 1 步：找出 m 的所有质因子 第 2 步：找出 n 的所有质因子 第 3 步：从第 1 步和第 2 步得到的质因子中找出所有公因子 第 4 步：将找到的所有公因子相乘，结果即为 m 和 n 的最大公约数 存在的问题？ 1.第 1 步和第 2 步没有明确定义如何找出一个自然数的所有质因子，而且 分解质因数问题是一个 NP 完全问题，目前尚未找到有效的方法； 2.第 3 步也没有明确定义如何在两个长度不等的数列中找出所有相同的元 只要求算法能够得出合理 素。因此，这个求解过程不满足算法的确定性和可行性。
的结果，即结果与真实世界 相符合，因为有时无法得出 有时会放宽算法的正确性，
评价一个“好”算法首先要满足算法的五个重要特性，此外，还要具备下 完全正确的结果。例如，衡 量计算 π 的算法是否正确就 列特性： （1）正确性：算法能满足具体问题的需求，即对于任何合法的输入，算 不是一件容易的事，因为 π 的正确值由无限位构成，但 法都会得出正确的结果。显然，一个算法必须正确才有存在的意义。 （2）健壮性：算法对非法输入的抵抗能力，即对于错误的输入，算法应 计算无限位的算法不满足 能识别并做出处理，而不是产生错误动作或陷入瘫痪。一个没有良好健壮性的 有穷性。 算法（程序）就像一颗等待爆炸的炸弹，这决不是危然耸听，有大量这种引起 灾难性后果的案例。 （3）可理解性：算法容易理解和实现。算法首先是为了人的阅读和交流， 其次是为了程序实现，因此，算法要易于人的理解、易于转换为程序。晦涩难 懂的算法可能隐藏一些不易发现的逻辑错误。 著名心理学家米勒提出的 （4）抽象分级：算法是由人来阅读、理解、使用和修改的，必须用抽象 米勒原则：人类的短期记忆 分级来组织算法表达的思想。 能力一般限于一次记忆 5～ （5）高效性：算法的效率包括时间效率和空间效率，时间效率显示了算 9 个对象，例如几乎所有计 法运行得有多快；而空间效率则显示了算法需要多少额外的存储空间。 算机软件的顶层菜单一般
不超过 9 个。
1.1.2 算法的描述方法
常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等。 用自然语言描述算法： 优点是：容易书写、容易理解； 缺点是：⑴容易出现二义性，导致算法不满足确定性； ⑵自然语言的语句一般都比较长，导致算法通常都很冗长； ⑶抽象级别较高，不便转换为计算机程序。 用流程图描述算法是采用 自然语言通常用来粗略地描述算法的基本思想。 一组规定的图形符号来表 用流程图描述算法： 示算法的流程。 优点是：直观易懂、能够随意表示控制流程； 缺点是：严密性不如程序设计语言、灵活性不如自然语言。 实践证明，除了一些非常简单的算法以外，这种描述方法使用起来非常不
2

算法设计与分析教师讲稿
方便。目前，流程图一般用来描述程序设计语言的基本语法。
表 1.1 流程图的基本符号（美国国家标准化协会 ANSI 规定的流程图的基本符号） 名 称 含 义
图形符号
起止框 处理框 输入/输出框 判断框 控制流
开始或结束 处理或运算 输入/输出 根据判断结果，执行两条路径中的某一条路径 执行的路径，箭头代表方向
用程序设计语言描述的算法： 优点是能由计算机直接执行； 缺点是抽象性差， 使算法设计者拘泥于描述算法的具体细节， 忽略了 “好” 算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及编程 环境。 伪代码是介于自然语言和程序设计语言之间的方法， 它采用某一程序设计 计算机科学界从来没有对 伪代码的书写形式达成过 语言的基本语法，操作指令可以结合自然语言来设计。 一种共识（或制定一种标 伪代码不是一种实际的编程语言，但在表达能力上类似于编程语言，同时 准） ，只是要求了解任何一 极小化了描述算法的不必要的技术细节，是比较合适的描述算法的方法，被称 种现代程序设计语言的人 都能很好地理解。因此，在 为“算法语言”或“第一语言”。
1.1.3 算法设计的一般过程
1. 理解问题
不同的教材、书籍和学术文 献中，伪代码的形式都有很 大不同。
这个一般过程并不是一个
能够为任意的问 首先搞清楚求解的目标是什么，给出了哪些已知信息、显式条件或隐含条 通用规则， 件，应该用什么形式的数据表达计算结果。准确地理解算法的输入是什么，明 题设计算法。事实上，这样 可 确要求算法做的是什么，即明确算法的入口和出口，这是设计算法的切入点。 的通用规则是不存在的。
2. 选择算法设计技术
以这样理解算法设计过程： 是具有极度挑战性的智力
算法设计技术（也称算法设计策略）是设计算法的一般性方法，主要包括 活动， 同时又是具有极度趣 蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、近似 味性的思维体操。 算法、概率算法等，这些算法设计技术构成了一组强有力的工具，在为新问题 设计算法时，可以运用这些技术设计出新的算法。 3. 设计并描述算法 在构思和设计了一个算法之后， 必须清楚准确地将所设计的求解步骤记录 下来，即描述算法。 4. 手工运行算法 逻辑错误无法由计算机检测出来，因为计算机只会执行程序，而不会理解 动机。经验和研究都表明，发现算法（或程序）中的逻辑错误的重要方法就是 手工运行算法，即跟踪算法。跟踪者要像计算机一样，用一个具体的输入实例
3

算法设计与分析教师讲稿
手工执行算法，并且这个输入实例要最大可能地暴露算法中的错误。即使有几 十年经验的高级软件工程师，也经常利用此方法查找算法中的逻辑错误。 5. 分析算法的效率 算法效率体现在两个方面：时间效率 和空间效率，时间效率显示了算法运行得 有多快，空间效率则显示了算法需要多少 额外的存储空间，相比而言，我们更关注 算法的时间效率。事实上，计算机的所有 应用问题，包括计算机自身的发展，都是 围绕着“时间——速度”这样一个中心进 行的。一般来说，一个好的算法首先应该 是比同类算法的时间效率高，算法的时间 效率用时间复杂性来度量。 6. 实现算法 把算法转变为特定程序设计语言编写 的程序。 需要强调的是，一个好算法是反复努 力和重新修正的结果。
待求解的问题 分析问题 选择算法设计技术 设计并描述算法 手工运行算法 不满意
分析算法的效率 满意 根据算法编写代码 图 1.2
算法设计的一般过程
1.2
为什么要学习和研究算法
1.2.1 算法在问题求解中的地位
用计算机求解问题的一般过程如图 1.3 所示。
人（设计方案） 计算机（执行方案） Donald Knuth： 程序就是蓝 色的诗，如果真是这样， 那么，算法就是这首诗的 灵魂。 问 题 数据模型 基本思路 图 1.3 想 法 数据表示 数据处理 用计算机求解问题的一般过程 算 法 程序语言 编程环境 程 序
由问题到想法需要分析问题，抽象出具体的数据模型，形成问题求解的基 本思路； 由想法到算法需要完成数据表示 （将数据模型存储到计算机的内存中） 和数据处理（将问题求解的基本思路形成算法）；由算法到程序需要将算法的 操作步骤转换为某种程序设计语言对应的语句。 算法用来描述问题的解决方案，是形式化的、机械化的操作步骤。利用计 算机解决问题的最重要一步是将人的想法描述成算法， 也就是从计算机的角度
4

算法设计与分析教师讲稿
设想计算机是如何一步一步完成这个任务的，告诉计算机需要做哪些事，按什 么步骤去做。一般来说，对不同解决方案的抽象描述产生了相应的不同算法， 而不同的算法将设计出相应的不同程序，这些程序的解题思路不同，复杂程度 不同，解题效率也不相同。下面请看一个例子。 例 1.2 求两个自然数的最大公约数。 2 48 36 【想法 1】可以用短除法找出这两个自然 2 24 18 数的所有公因子，将这些公因子相乘，结果就 3 12 9 是这两个数的最大公约数。例如，48 和 36 的 4 3 公因子有 2、2、3，则 48 和 36 的最大公约数 图 1.4 短除法求最大公约数 是 2×2×3=12。短除法求最大公约数的过程 如图 1.4 所示。 【算法 1】找两个数的公因子目前只能用蛮力法逐个尝试，可以从 2 ~ min{m, n}进行枚举尝试。短除法求最大公约数的算法用伪代码描述如下： 算法 1.1：CommFactor1 输入：两个自然数 m 和 n 输出：m 和 n 的最大公约数 1. factor = 1; 2. 循环变量 i 从 2 ~ min{m, n}，执行下述操作： 2.1 如果 i 是 m 和 n 的公因子，则执行下述操作： 2.1.1 factor = factor * i; 2.1.2 m = m/i; n = n/i; 2.2 如果 i 不是 m 和 n 的公因子，则 i = i + 1; 3. 输出 factor; 【算法实现 1】程序由两层嵌套的循环组成，外层循环枚举所有可能的公 因子， 内层循环尝试 i 是否为 m 和 n 的公因子， 注意到可能会有重复的公因子， 因此，内层循环不能用 if 语句。算法用 C++语言描述如下： int CommFactor1(int m, int n) { int i, factor = 1; for (i = 2; i <= m && i <= n; i++) { while (m % i == 0 && n % i == 0) //此处不能用 if 语 句 { factor = factor * i; m = m / i; n = n / i; } } return factor; }
5

算法设计与分析教师讲稿
【想法 2】一种效率更高的方法是欧几里德算法，其基本思想是将两个数 辗转相除直到余数为 0。欧几里德算法求最大公约数的过程如图 1.5 所示。
被除数 48 36 图 1.5 除数 36 12 余数 12 0
欧几里德算法求最大公约数
【算法 2】欧几里德算法用伪代码描述如下：
算法 1.2：CommFactor2 输入：两个自然数 m 和 n 输出：m 和 n 的最大公约数 1. r = m % n; 2. 循环直到 r 等于 0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n; 【算法实现 2】欧几里德算法用 C++语言描述如下： int CommFactor2(int m, int n) { int r = m % n; while (r != 0) { m = n; n = r; r = m % n; } return n; } 【算法比较】算法 1 的时间主要耗费在求余操作（m % i == 0 && n % i == 0）上，算法 2 的时间主要也耗费在求余操作（r = m % n）上，以 48 和 36 为 例，算法 1 要进行 10 次求余操作，而算法 2 只需进行 2 次求余操作，显然， 算法 2 比算法 1 的时间效率高。 需要强调的是，有些问题比较简单，很容易就可以得到问题的解决方案， 如果问题比较复杂，就需要更多的思考才能得到问题的解决方案。对于许多实 际的问题，写出一个可以正确运行的算法还不够，如果这个算法在规模较大的 数据集上运行，那么运行效率就成为一个重要的问题。
6

算法设计与分析教师讲稿
1.2.2 算法训练能够提高计算思维能力
冯·诺伊曼计算机是按存储程序方式进行工作的，计算机的工作过程就是 运行程序的过程。但是计算机不能分析问题并产生问题的解决方案，必须由人 来分析问题，确定并描述问题的解决方案，因此，用计算机求解问题是建立在 高度抽象的级别上，表现为采用形式化的方式描述问题，问题的求解过程是建 立符号系统并对其实施变换的过程，并且变换过程是一个机械化、自动化的过 程。 在描述问题和求解问题的过程中， 主要采用抽象思维和逻辑思维， 如图 1.6 所示。
抽象思维 问 题
逻辑思维 求解问题 自动化运行 符号变换
描述问题 形式化描述 符 图1.6 号
计算机学科的符号化特征
在 ACM/IEEE-CS 提交的 CC2005 中，将计算机专业的基本学科能力归纳 为计算思维能力、算法设计与分析能力、程序设计与实现能力和系统能力，其 中计算思维（computational thinking）主要包括形式化、模型化、抽象思维与 逻辑思维。如前所述，在用计算机求解问题的过程中，最重要的环节就是将人 的想法抽象为算法。算法不是问题的答案，而是经过精确定义的、用来获得答 案的求解过程。算法设计过程是计算思维的具体运用，因此，算法训练就像一 种思维体操，能够锻炼我们的思维，使思维变得更清晰、更有逻辑。
1.2.3 算法研究是推动计算机技术发展的关键
算法研究的核心问题是时间（速度）问题。人们可能有这样的疑问：既然 计算机硬件技术的发展使得计算机的性能不断提高，算法的研究还有必要吗？ 计算机的功能越强大，人们就越想去尝试更复杂的问题，而更复杂的问题 需要更大的计算量。现代计算技术在计算能力和存储容量上的革命仅仅提供了 计算更复杂问题的有效工具，无论硬件性能如何提高，算法研究始终是推动计 算机技术发展的关键。实际上，我们不仅需要算法，而且需要“好”算法。可 以肯定的是，发明（或发现）算法是一个非常有创造性和值得付出的过程。下 面看几个例子。 1. 检索技术 20 世纪 50 ~ 60 年代，检索的对象是规模比较小的数据集合。
7

算法设计与分析教师讲稿
70 ~ 80 年代，数据管理采用数据库技术，数据库的规模在 K 级或 M 级， 检索算法的研究在这个时期取得了巨大的进展。 90 年代以来，Internet 引起计算机应用的急速发展，海量数据的处理技术 成为研究的热点，而且数据驻留的存储介质、数据的存储方法以及数据的传输 技术也发生了许多变化，这些变化使得检索算法的研究更为复杂也更为重要 了。 近年来，智能检索技术成为基于 Web 信息检索的研究热点。 2. 压缩与解压缩 随着多媒体技术的发展，计算机的处理对象由原来的字符发展到图像、图 形、音频、视频等多媒体数字化信息，这些信息数字化后，其特点就是数据量 非常庞大。 3. 信息安全与数据加密 在计算机应用迅猛发展的同时，也面临着各种各样的威胁。如在电子商务 中，信息安全是最关键的问题，保证信息安全的一个方法就是对需要保密的数 据进行加密。在这个领域，数据加密算法的研究是绝对必须的，其必要性与计 算机性能的提高无关。
1.3
1.3.1 查找问题 1.3.2 排序问题 1.3.3 图问题
重要的问题类型
算法中最古老也最令人感兴趣的领域是图问题， 很多纷乱复杂的现实问题 抽象出的数据模型都是图结构，例如，可以利用图研究化学领域的分子结构、 解决高校排课问题、解决任务分配问题和车间调度问题等等。
1.3.4 组合问题
组合问题一般都是最优化问题，即寻找一个组合对象，比如一个排列、一 个组合或一个子集，这个组合对象能够满足特定的约束条件并使得某个目标函 数取得极值：价值最大或成本最小。 无论从理论的观点还是实践的观点， 组合问题都是计算领域中最难解的问 题，其原因是：（1）随着问题规模的增大，组合对象的数量增长极快，即使
8

算法设计与分析教师讲稿
是中等大小的实例，其组合对象的数量也会达到不可思议的数量级，产生组合 爆炸；（2）对于绝大多数组合问题，尚未找到有效的算法能在可接受的时间 内实现正确求解。
1.3.5 几何问题
几何问题处理类似于点、线、面、体等几何对象。几何问题与其他问题的 不同之处在于， 哪怕最简单、 最初等的几何问题也难以用符号化的方法去处理。 尽管人类对几何问题的研究从古代起便没有中断过，但是发展到借助计算机来 解决几何问题的研究， 还只是停留在一个初级阶段。 随着计算机图形图像处理、 机器人和断层 X 摄像技术等方面应用的深入， 人们对几何算法产生了强烈的兴 趣。本书只讨论两个经典的计算几何问题：最近对问题和凸包问题。最近对问 题是在给定平面上的 n 个点中，求距离最近的两个点。凸包问题要求找出一个 能把给定集合中的所有点都包含在里面的最小凸边形。
9

算法设计与分析习题答案1-6章

习题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 using namespace std; int main() { double value=0; 图 七桥问题

for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< using namespace std; int main () { double a,b; double arctan(double x);圣经上说：神6天创造天地万有，第7日安歇。为什么是6天呢？任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此6是完美数。神6天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数 #include using namespace std; int main() { int value, k=1; cin>>value; for (int i = 2;i!=value;++i) { while (value % i == 0 ) { k+=i;有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？ 由于甲过桥时间最短，那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如： 第一趟：甲，乙过桥且甲回来

算法设计与分析(作业三)

算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月

实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为）（n 3 O 。 四、实验源代码

算法设计与分析考试题及答案

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算法的思想。

算法设计与分析实验报告贪心算法

算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include float small1,small2; int flag1,flag2,count; typedefstructHuffmanTree { float weight; intlchild,rchild,parent; }huffman; huffmanhuffmantree[100]; void CreatHuffmanTree(intn,int m) { inti; void select(); printf("请输入%d个节点的权值:",n); for(i=0;i

printf("\n"); for(i=0;i

算法设计与分析习题答案1-6章.docx

习题 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 using namespace std; int main() { double value=0;

for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n 至少为 :"< using namespace std; int main () { double a,b; double arctan(double x);圣经上说：神 6 天创造天地万有，第7 日安歇。为什么是6天呢？任何一个自然数的因数中都有 1 和它本身，所有小于它本身的因数称为这个数的真 因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如， 6=1+2+3，因此6 是完美数。神 6 天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数 #include using namespace std; int main() { int value, k=1; cin>>value; for (int i = 2;i!=value;++i) { while (value % i == 0 ) { k+=i;有 4 个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都 在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味 1着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用 分钟，乙过桥要用 2 分钟，丙过桥要用 5 分钟，丁过桥要用10 分钟，显然，两个人走路的 速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？ 由于甲过桥时间最短，那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如： 第一趟：甲，乙过桥且甲回来

算法分析与设计

专业： 班级： 学号： 姓名： 日期： 2014年 11月 10日

48476Λn n 111+++=。 2、q(n ，m)=q(n ，n)，m>=n 。 最大加数n1实际上不能大于n ，因此，q(1，m)=1。 3、q(n ，n)=1+q(n ，n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ，m)= q(n ，m-1)+q(n-m ，m)，n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 （2）、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n

算法设计与分析复习资料1

一 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、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x =

算法设计与分析课程设计报告样本

课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 12软件(2)班 学号: 0311232 成绩: 指导教师: 秦川 开课时间: 年一学期 一、问题描述 1．普通背包问题

给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1≤i≤n。 2．0/1背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3．棋盘覆盖问题 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。 二、问题分析

1．普通背包问题 对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量Ｗ, 剩余的将是n-1个原重物品1, 2, ······, j-1, j+1, ·····, n以及重为Ｗi－Ｗ的物品j 中可装入容量为C－Ｗ的背包且具有最大价值的物品。 2．0/1背包问题 如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照物品的价值/物品的体积来从大到小排列, 然后最优解为( 1, 1, 1......., 1, t, 0, 0, ......) , 其中0<=t<=1; 因此, 我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下), 我们能够考虑我们能够达到的最大的价值, 即我们能够经过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。经过该条件, 能够减去很多的枝条, 大大节省运行时间。 3．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否

算法设计与分析课程设计(完整版)

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 情况。

算法设计与分析C++语言描述(陈慧南版)课后答案

第一章 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 =-+≤，所以，22 582()n n n -+=O 。 （2）当8n ≥时，2222 582524n 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 ≤-+≤，所以 22582()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 )的关系。 （2）当4n ≥时，2 log log n n n <<，所以2 2 ()/log f n n n n =<，2 2 ()log g n n n n =≥。可选1c =，04n =。对于0n n ≥，2 ()()f n n cg n <≤，即()(())f n g n =O 。 （3）因为log log(log )()(log ) n n f n n n ==，()/log log 2n g n n n n ==。当4n ≥时，log(log )()n f n n n =≥，

算法设计与分析试卷(2010)

内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(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. 回溯法解旅行售货员问题时的解空间树是（ 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 ）是贪心算法与动态规划算法的共同点。

算法设计与分析试卷及答案

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型: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

算法设计与分析课程设计报告

压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 二、算法分析及思路： 对于该问题，我们做如下分析： （1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计；（2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计； （3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计； （4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计； （5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计； （6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题： 1.写一个对txt文件压缩和解压的程序，使用动态编码。 2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树； 3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图：

2009.1算法设计与分析报告课程期末试卷-A卷(自测 )

华南农业大学期末考试试卷（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

算法设计与分析考试重点归纳

算法设计考试重点整理 题型： 一选择题（10*2=20 分） 二简答题（4*5=20 分） 三应用题（3*10=30 分） 四算法题（3*10=30 分） 第一、二章 算法的定义：解某一特定问题的一组有穷规则的集合（对特定问题求解步骤的一种描述，是指令的有限序列） 算法的特征：1）有限性 2）确定性 3）输入 4）输出 5）能行性 算法分析的目的： 基本数据结构： 线性结构(元素之间是一对一的关系) 用顺序存储结构存储的线性表称为顺序表 用链式存储结构存储的线性表称为链表。 树形结构(元素之间是一对多的关系) 图(网)状结构(元素之间是多对多的关系) 栈：是一种只允许在表的一端进行插入或删除操作的线性表。允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。当栈中没有数据元素时，称之为空栈。栈的插入操作称为进压栈，删除操作称为出栈。 队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表。允许进行插入操作的一端称为队尾。允许进行删除操作的一端称为队头。当队列中没有数据元素时，称之为空队列。队列的插入操作称为进队或入队。队列的删除操作称为退队或出队。 树：树型结构是一种非线性结构，它用于描述数据元素之间的层次关系图 图：G＝(V，E)是一个二元组

其中：V是图G中数据元素（顶点）的非空有限集集合 E是图G中关系的有限集合 由表达式求渐进表达式：例：(n2+n)/4 n2/4（增长速率最快的那一项） 时间复杂度的计算：（P23） 性能的比较：O(1) < O(log2n) < O(n) < O(nlog2n) =O(nlogn)< O(n2) < O(n3) < O(n k) < O(2n) 第三章 算法思想、稳定性、时间复杂度、应用、排序的移动次数： 希尔排序（数据结构P265）：先将待排序列分割为若干个子序列分别进行直接插入排序；待整个序列基本有序时，再对全体记录进行一次直接插入排序。也称缩小增量的直接插入排序。 希尔排序的时间复杂度在O(nlog2n)和 O(n2)之间，大致为O 合并排序（P59）：设初始序列含有n个记录，则可看成n个表长为1的有序表将这n个有序表两两合并，则可得n/2个表长为2的有序表再将这n/2个有序表两两合并，则可得n/4个长为4的有序表依次重复，直到对2个表长为n/2的有序表两两合并得1个表长为n的有序表为止。 堆排序、堆调整（P62）： 初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。 基数排序（P71）：不进行记录关键字的比较，借助多关键字排序的思想对单逻辑关键字进行排序。 算法时间复杂度稳定性 希尔排序 O不稳定 快速排序 O(nlogn)不稳定