教 案
２００７ ￣￣ ２００８ 学年 第 二 学期
院（系、所、部） 计算机学院
教 研 室 计算机科学系
课 程 名 称 算法设计与分析
授 课 对 象 ０６本科专业（１班、２班）
授 课 教 师 陈卫东
职 称 职 务 副教授、教师
教 材 名 称 算法设计技巧与分析
２００８ 年 ２ 月 日
- 1 -
授课类型 理论课 授课题目（教学章节或主题）：
第一章 算法分析的基本概念（包括课程概述）
授课时间
第 １ 周
（３学时）
教学目标或要求：
了解本课程的学科地位及发展现状；了解本课程的主要内容、学习目标、学习方法，本课程与先行课程与后续课程的关系，熟悉衡量算法性能好坏的标准；理解并掌握与算法分析有关的概念。
教学内容（包括基本内容、重点、难点）：
１．课程的学科地位及发展现状
２．课程的主要内容、学习目标、学习方法
通过实例来让学生体会到影响问题求解效率的关键是算法；并通过实例说明什么是难解问题和易解问题；给出一些常见典型的难问题；指出探求这些难问题的好算法是计算机领域的核心问题之一，并介绍该领域当前的某些发展现状。
３．算法分析的基本概念
（１）算法及其特性
（２）衡量一个算法性能的好坏的标准
（３）算法的时间和空间复杂度的概念
重点：算法分析的基本概念。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。通过举例来阐述算法分析的基本概念。
思考题、讨论题、作业：
预习第一章内容。
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 2 -
授课类型 理论课 授课题目（教学章节或主题）：
第一章算法分析的基本概念（算法分析的基本方法）第二章数学知识 授课时间
第 ２ 周
（３学时）
教学目标或要求：
掌握算法分析的基本步骤；理解与掌握算法复杂度渐近表示的几个记号；熟悉分析求解复杂度的常用方法，掌握其中最基本的方法；了解最优算法的概念。
教学内容（包括基本内容、重点、难点）：
４．算法分析的基本方法及必备数学基础知识
（１）分析算法时间复杂度的基本步骤
举例说明：基本运算ｂａｓｉｃ ｏｐｅｒａｔｉｏｎ、问题大小ｓｉｚｅ、渐近表示的记号Ο、?、Θ。
（２）算法时间复杂度的有关概念
举例（检索问题、排序问题）说明，平均、最好、最坏时间复杂度的概念。
（３）分析、求解算法复杂度的方法
分析复杂度的方法：循环统计、递归关系、分摊统计（Ａｍｏｒｔｉｚｅｄ Ａｎａｌｙｓｉｓ）。
数学知识（求解复杂度的方法）：典型求和公式、积分近似求和、解递归方程（不等式）。 举例说明。
５．最优算法（Ｏｐｔｉｍａｌ Ａｌｇｏｒｉｔｈｍｓ）
最优算法的概念。举例说明。
重点：理解表示复杂度的三个渐近记号；算法分析的基本步骤；算法复杂度的基本分析、求解方法；递归方程的解法。
难点：递归方程的解法。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。通过多媒体演示，并通过举例来阐述基本概念、基本方法。
思考题、讨论题、作业：
P34—1.16；P64—2.16,2.18,2.19,2.20
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 3 -
授课类型 理论课 授课题目（教学章节或主题）：
第五章 归纳（Ｉｎｄｕｃｔｉｏｎ）
授课时间
第３ 周
（３学时）
教学目标或要求：
理解归纳与递归的关系；掌握使用归纳原理来设计算法、使用递归过程来表示算法的基本思想；掌握基数排序算法、求整数次幂算法、多项式求值算法的设计思想。
教学内容（包括基本内容、重点、难点）：
１．递归与归纳的关系
通过分析选择排序算法和插入排序算法来给出归纳原理与递归算法之间关系。指出，递归算法可以使用归纳原理来设计，并保证其正确性。
２．基数排序（Ｒａｄｉｘ Ｓｏｒｔ）
问题的描述、使用归纳原理进行算法设计的思想、算法描述及其时间复杂度分析。
３．求整数次幂（Ｉｎｔｅｇｅｒ Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ）
问题的描述、使用归纳原理进行算法设计的思想、算法描述及其时间复杂度分析。
４．多项式求值（Ｅｖａｌｕａｔｉｎｇ Ｐｏｌｙｎｏｍｉａｌｓ）
问题的描述、使用归纳原理进行算法设计的思想、算法描述及其时间复杂度分析。
强调：递归算法的设计可以使用归纳原理。递归算法可以借助于递归调用图来进行直观的理解。尾递归形式的算法易于直接转化为非递归即迭代形式。
重点：掌握使用归纳原理设计算法的基本思想。
难点：递归调用过程的理解。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。使用多媒体演示，通过举例和图示来阐述基本原理和各算法的思想。
思考题、讨论题、作业：
P99-100—5.8,5.9
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 4 -
授课类型 理论课 授课题目（教学章节或主题）：
第五章 归纳（Ｉｎｄｕｃｔｉｏｎ）<续>
授课时间
第 ４ 周
（３学时）
教学目标或要求：
通过几个问题进一步掌握使用归纳原理来设计算法的基本思想。掌握产生排列、产生组合的算法的思想，它们是某些回溯法、分枝限界法的编程基础。
教学内容（包括基本内容、重点、难点）：
５．产生排列（Ｇｅｎｅｒａｔｉｎｇ Ｐｅｒｍｕｔａｔｉｏｎｓ）
问题的描述、使用归纳原理进行算法设计的思想、算法描述及其时间复杂度分析。向学生指出两种算法的差别。可以画出算法在ｎ＝４时的递归调用树来理解算法的执行流程。
６．产生组合（Ｇｅｎｅｒａｔｉｎｇ Ｃｏｍｂｉｎａｔｉｏｎｓ）（补充）
问题的描述、使用归纳原理进行算法设计的思想、算法描述及其时间复杂度分析。可以画出算法在n＝４时的递归调用树来理解算法的执行流程。
７． 找主元素（Ｆｉｎｄｉｎｇ ｔｈｅ Ｍａｊｏｒｉｔｙ Ｅｌｅｍｅｎｔ）
问题的描述、算法设计的思想、算法描述及其时间复杂度分析。向学生指出，要设计好的算法需要理解问题并善于充分利用问题的特点。
强调：递归算法的设计可以使用归纳原理。递归算法可以借助于递归调用图来进行直观的理解。
重点：掌握使用归纳原理设计算法的基本思想；
难点：递归调用过程的理解。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。使用多媒体演示。通过举例和图示来阐述各算法的思想。
思考题、讨论题、作业：
P100-101—5.23,5.31
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 5 -
授课类型 理论课 授课题目（教学章节或主题）：
第六章 分治法（Ｄｉｖｉｄｅ ａｎｄ Ｃｏｎｑｕｅｒ）
授课时间
第 ５ 周
（３学时）
教学目标或要求：
了解分治法的适用范围，熟悉其基本思想、特点，掌握设计分治算法的基本步骤。掌握使用分治策略设计的快速排序算法和选择问题的分治算法的基本思想、复杂度的分析方法和结论，能在给定问题实例上模拟算法的执行。
教学内容（包括基本内容、重点、难点）：
１．分治法的框架（Ｔｈｅ Ｄｉｖｉｄｅ ａｎｄ Ｃｏｎｑｕｅｒ Ｐａｒａｄｉｇｍ）
通过学生熟悉的二分检索算法、归并排序算法来介绍分治法的基本思想、设计步骤、适用范围、以及分治算法的复杂度的一般分析方法。
２．选择问题（Ｓｅｌｅｃｔｉｏｎ： Ｆｉｎｄｉｎｇ ｔｈｅ Ｍｅｄｉａｎ ａｎｄ ｔｈｅ ｋ－ｔｈ Ｓｍａｌｌｅｓｔ Ｅｌｅｍｅｎｔ） 介绍选择问题的分治算法的思想，及算法复杂度的分析方法及结论。通过与直接算法相比，体会分治策略设计算法的好处。
３．快速排序（Ｑｕｉｃｋ Ｓｏｒｔ）
介绍快速排序算法的基本思想，及算法复杂度的分析方法及结论。通过与其它算法相比，体会分治策略设计算法的特点。
强调：通过动态演示或者在具体实例上模拟算法的执行来理解这些精巧的算法。
重点：使用分治策略设计算法的步骤；分治算法的分析方法；典型问题的精巧算法。
难点：分治算法的分析方法；了解影响算法复杂度的几个因素。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。使用多媒体演示。通过举例和图示来阐述分治法的基本框架和各个算法的思想。 思考题、讨论题、作业：
１．P127—6.39
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 6 -
授课类型 理论课 授课题目（教学章节或主题）：
第六章 分治法（Ｄｉｖｉｄｅ ａｎｄ Ｃｏｎｑｕｅｒ）<续>
授课时间
第 ６ 周
（３学时）
教学目标或要求：
通过分治策略的典型应用来进一步熟练掌握使用分治策略设计算法的基本方法，熟悉通过减少合并步骤的时间来降低算法时间复杂度的方法。掌握使用分治策略设计的典型问题的精巧算法，能在给定问题实例上模拟算法的执行。
教学内容（包括基本内容、重点、难点）：
引入：
先回顾一个递归方程的解：定理２．５ 和引理２．１。由此说明，通过减少合并步骤的时间可降低分治算法的时间复杂度。
４．大整数乘法（Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ ｏｆ Ｌａｒｇｅ Ｉｎｔｅｇｅｒｓ）
介绍问题的描述，多种算法及其时间复杂度的比较。特别是分治算法中合并步骤的设计。 ５．矩阵乘法（Ｍａｔｒｉｘ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）
介绍问题的描述，多种算法及其时间复杂度的比较。特别是分治算法中合并步骤的设计。 ６．最近点对问题（Ｔｈｅ Ｃｌｏｓｅｓｔ Ｐａｉｒ Ｐｒｏｂｌｅｍ）
介绍问题的描述，多种算法及其时间复杂度的比较。特别是分治算法中合并步骤的设计。
强调：上述问题的分治算法之所以要比及直接算法有效，关键是设法减少了合并步骤的时间，这往往可降低分治算法的时间复杂度。
重点：使用分治策略设计算法的步骤；减少合并步骤的时间的方法；典型问题的精巧算法。
难点：减少合并步骤的时间的方法。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。使用多媒体演示。通过举例和图示来阐述分治法的基本框架和各个算法的思想。 思考题、讨论题、作业：
１．P127—6.44 2．实验作业：通过实验对归并排序和快速排序进行比较，要求统计分析实验结果。 参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 7 -
授课类型 理论课 授课题目（教学章节或主题）：
第七章 动态规划法（Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｍｉｎｇ）
授课时间
第 ７ 周
（３学时）
教学目标或要求：
了解动态规划法的适用范围，熟悉其基本思想、特点，掌握针对具体问题设计动态规划算法的基本步骤。掌握典型问题的动态规划算法，能在给定问题实例上模拟算法的执行。
教学内容（包括基本内容、重点、难点）：
１．引入
通过Ｆｉｂｏｎａｃｃｉ序列通项的计算和二项式系数的计算来说明，直接使用递归计算时往往子问题中有大量的重复计算，从而使得算法效率很低。由此给出动态规划的基本思想：重复的子问题只算一次。
２．最长公共子序列问题（Ｔｈｅ Ｌｏｎｇｅｓｔ Ｃｏｍｍｏｎ Ｓｕｂｓｅｑｕｅｎｃｅ Ｐｒｏｂｌｅｍ）
结合具体实例来说明：问题的描述、问题的求解的递推计算公式、算法的分析。
３．矩阵的链乘（Ｍａｔｒｉｘ Ｃｈａｉｎ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）
结合具体实例来说明：问题的描述、问题的求解的递推计算公式、算法的分析。
４．动态规划法框架（Ｔｈｅ Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｍｉｎｇ Ｐａｒａｄｉｇｍ）
以多段图问题为例来阐述最优性原理、设计动态规划法的几个步骤、具体的计算方法等。
强调：使用动态规划法求解的问题的特点为最优解满足最优性原理、子问题有重叠性。设计动态规划算法的关键在于获取递推计算公式，而最优性原理是递推计算公式正确性的保证。
重点：递推公式的获得。
难点：算法正确性的理解。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。使用多媒体演示，通过举例和图示来阐述动态规划法的基本原理和各算法的思想。 思考题、讨论题、作业：
１．通过递推计算公式能计算出最优值，如何由此构造出最优解？ ２．P140-141—7.5,7.11
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 8 -
授课类型 理论课 授课题目（教学章节或主题）：
第七章 动态规划法（Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｍｉｎｇ）<续>
授课时间
第 ８ 周
（３学时）
教学目标或要求：
通过典型应用来进一步熟练掌握使用态规划法设计算法的关键步骤。掌握典型问题的动态规划算法，能在给定问题实例上模拟算法的执行。
教学内容（包括基本内容、重点、难点）：
５．所有点对间的最短路径问题（Ｔｈｅ Ａｌｌ－Ｐａｉｒｓ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｐｒｏｂｌｅｍ）
掌握Ｆｌｏｙｄ算法的基本思想（递推计算公式的获取）、计算过程，熟悉其适用范围、复杂度分析及结论。
注意与Ｄｉｊｋｓｔｒａ算法的区别：适用范围、算法策略、复杂度等。
６．０／１背包问题（Ｔｈｅ Ｋｎａｐｓａｃｋ Ｐｒｏｂｌｅｍ）
掌握算法基本思想（递推计算公式的获取）、计算过程，熟悉其适用范围、复杂度分析及结论。 ７．旅行商问题（Ｔｈｅ Ｔｒａｖｅｌｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ）
掌握算法的基本思想（递推计算公式的获取）、计算过程，熟悉其复杂度分析及结论。
强调：设计动态规划算法的关键步骤在于获取递推计算的公式，然后采用自下而上来计算。可以通过在具体实例上模拟执行算法来掌握这些算法。
重点：递推公式的获得。
难点：算法正确性的理解。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。使用多媒体演示。通过举例和图示来阐述各个算法的思想。
思考题、讨论题、作业：
１．P141-143—7.15, 7.22 ２．实验作业：设计求解资源分配问题的动态规划算法，并编程实现之。 参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 9 -
授课类型 理论课 授课题目（教学章节或主题）：
第八章 贪心法（Ｔｈｅ Ｇｒｅｅｄｙ Ａｐｐｒｏａｃｈ）
授课时间
第 ９ 周
（３学时）
教学目标或要求：
了解贪心法的应用范围，熟悉贪心法的基本思想、特点，掌握针对具体问题设计贪心算法的关键步骤以及算法正确性的证明方法。掌握典型问题的精巧贪心算法的基本思想，能在给定实例上模拟算法的执行。
教学内容（包括基本内容、重点、难点）：
１．引入
以背包问题为实例，通过设计该问题的多种贪心算法来让学生了解贪心法的基本特点、贪心法的适用范围、使用贪心策略设计算法的基本步骤、贪心法正确性的证明方法等。
２． 贪心准则的选取
通过考虑设计如下问题的贪心算法：活动安排问题、拓扑排序问题、０／１背包问题，来进一步使得学生理解贪心准则的选择是设计贪心算法的关键步骤，熟悉贪心准则的选取方法。
３．应用举例
（１）最短路径问题（Ｔｈｅ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｐｒｏｂｌｅｍ）
掌握Ｄｉｊｋｓｔｒａ算法的基本思想（贪心准则），熟悉其适用范围、复杂度分析及结论、正确性证明方法、以及选择适当的数据结构来改进复杂度的方法。
强调：使用贪心算法求解问题的关键是选好贪心准则。掌握这些贪心算法的关键在于掌握其贪心准则。可以通过在给定实例上模拟执行算法来掌握这些精巧算法。
重点：贪心准则的选取方法；贪心法正确性的证明方法；典型问题的精巧算法。
难点：贪心法正确性的证明方法。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。使用多媒体演示。通过举例和图示来阐述设计贪心法的基本思路和各个算法的思想。 思考题、讨论题、作业：
P160—8.13, 8.22
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 10 -
授课类型 理论课 授课题目（教学章节或主题）：
第八章 贪心方法（Ｔｈｅ ｇｒｅｅｄｙ Ａｐｐｒｏａｃｈ）<续>
授课时间
第 １０ 周
（３学时）
教学目标或要求：
通过贪心法的典型应用来进一步掌握使用贪心策略设计算法的基本方法，熟悉对贪心算法分析的方法以及贪心算法正确性的证明方法。掌握这些典型问题的精巧贪心算法的基本思想，能在给定实例上模拟算法的执行。
教学内容（包括基本内容、重点、难点）：
３．应用举例
（２）Ｋｒｕｓｋａｌ算法
掌握Ｋｒｕｓｋａｌ算法的基本思想（贪心准则），熟悉其适用范围、复杂度分析及结论、正确性证明方法。
（３）Ｐｒｉｍ算法
掌握Ｐｒｉｍ算法的基本思想（贪心准则），熟悉其适用范围、复杂度分析及结论、正确性证明方法、以及选择适当的数据结构来改进复杂度的方法。
（４）文件压缩
掌握Ｈｕｆｆｍａｎ算法的基本思想（贪心准则），熟悉其适用范围、复杂度分析及结论、正确性证明方法。
强调：使用贪心算法求解问题的关键是选好贪心准则。掌握这些贪心算法的关键在于掌握其贪心准则。可以通过在给定实例上模拟执行算法来掌握这些精巧算法。
重点：贪心准则的选取；贪心法的正确性证明；典型问题的精巧算法。
难点：贪心法的正确性证明。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。使用多媒体演示。通过举例和图示来阐述各个算法的思想。
思考题、讨论题、作业：
P160-161—8.23,8.24,8.31
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 11 -
授课类型 理论课 授课题目（教学章节或主题）：
第九章 图的遍历（Ｇｒａｐｈ Ｔｒａｖｅｒｓａｌ）
授课时间
第 １１ 周
（３学时）
教学目标或要求：
掌握图的两种基本的遍历方法即深度优先和宽度优先，以及它们的典型应用。为后面的回溯法和分枝限界法奠定基础。
教学内容（包括基本内容、重点、难点）：
１．引入
通过对例图的结点进行遍历来说明两种遍历方法即深度优先和宽度优先的共同点与差别。 ２．深度优先搜索（Ｄｅｐｔｈ－Ｆｉｒｓｔ Ｓｅａｒｃｈ）
通过定义活结点、死结点、扩展结点等几个概念，并结合动态演示来说明深度优先搜索的基本特点、算法描述以及算法的时空复杂度。
３．深度优先搜索的应用
图的无环性（Ｇｒａｐｈ ａｃｙｃｌｉｃｉｔｙ）
图的无环性（Ｔｏｐｏｌｏｇｉｃａｌ ｓｏｒｔｉｎｇ）
找图的拐点（Ｆｉｎｄｉｎｇ ａｒｔｉｃｕｌａｔｉｏｎ ｐｏｉｎｔｓ ｉｎ ａ ｇｒａｐｈ）
４．宽度优先搜索（Ｂｒｅａｄｔｈ－Ｆｉｒｓｔ Ｓｅａｒｃｈ）
通过活结点、死结点、扩展结点等几个概念，并结合动态演示来说明深度优先搜索的基本特点、算法描述以及算法的时空复杂度。
５．宽度优先搜索的应用
在带权图中找一点到另外一点的最短路径。
重点：掌握两种遍历方法的特点。
难点：两种遍历方法的应用。需要着重注意几类边：向前边、向后边、回边、交叉边。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。通过软件的动态演示来阐述两种图的遍历方法，用图示法来阐述各算法的执行过程。 思考题、讨论题、作业：
P171-172—9.6, 9.31, 9.33
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 12 -
授课类型 理论课 授课题目（教学章节或主题）：
第十三章 回溯法（Ｂａｃｋｔｒａｃｋｉｎｇ）
授课时间
第 １２ 周
（３学时）
教学目标或要求：
了解回溯法的应用范围，熟悉回溯法的基本思想、特点，掌握针对具体问题设计回溯算法的基本步骤和方法。
教学内容（包括基本内容、重点、难点）：
１．引言
强调：回溯法是一种通用的穷举方法，一种在状态空间树上系统且具有跳跃性的搜索方法。其基本思想是：树的深度优先搜索＋剪枝操作。
２．回溯法的适用问题
存在性问题；最优化问题。
强调：约束条件一般要求满足完备性性质。
３．回溯算法的基本框架（Ｔｈｅ Ｇｅｎｅｒａｌ Ｂａｃｋｔｒａｃｋｉｎｇ Ｍｅｔｈｏｄ）
回溯法基本要素：解空间的树形表示，剪枝操作；
设计回溯算法的基本步骤；
回溯算法的形式和终止条件。
４．回溯法求解问题举例
（１） 图的ｋ着色问题（Ｔｈｅ ｋ－Ｃｏｌｏｒｉｎｇ Ｐｒｏｂｌｅｍ）
强调：使用回溯法求解问题的关键是要设计好构成回溯算法的基本要素。
重点：具体回溯算法的基本要素的设计；回溯算法搜索过程的理解。
难点：隐式解空间树的构造。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。通过软件的动态演示让学生理解回溯算法的搜索过程。
思考题、讨论题、作业：
P227-228—13.12,13.17 （要求：给出求解问题的回溯法的基本要素即可）
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 13 -
授课类型 理论课 授课题目（教学章节或主题）：
第十三章 回溯法（Ｂａｃｋｔｒａｃｋｉｎｇ）<续1>
授课时间
第 １３ 周
（３学时）
教学目标或要求：
通过具体应用进一步熟练掌握使用回溯法求解问题的基本步骤和方法，并能熟练编程序实现算法。了解回溯算法的效率估计方法。
教学内容（包括基本内容、重点、难点）：
４．回溯法求解问题举例
（２）ｎ皇后问题；（３）０／１背包问题；（４）骑士问题
强调：使用回溯法求解问题的关键是要设计好构成回溯算法的基本要素。
５．回溯法编程举例
（１）产生一个集合的所有的子集
（２）产生ｎ个元素的所有排列
（３）ｎ皇后问题
（４）０／１背包问题
强调：回溯算法的实现一般仅需在（１）或（２）程序的适当地方插入剪枝操作即可。
６．回溯法的效率分析
（１）理论上，回溯算法最坏时间一般都是指数型复杂度，空间往往是多项式，比如Ｏ（ｎ）。
（２）实际中，使用蒙特卡洛法通过实验来估计回溯算法运行在一个实例的时间效率。
强调：影响算法效率的因素；蒙特卡洛法的思想。以解８皇后问题的回溯算法为例来说明。 重点：具体回溯算法的基本要素的设计；回溯算法的实现。
难点：隐式解空间树的构造；回溯法的实现。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。通过程序演示和图示来阐述各个算法的要素、回溯法效率分析的基本方法。
思考题、讨论题、作业：
１．在实现回溯算法时，如何只产生一个解？如何产生所有的解？如何保存最优解？
２．编写程序实现求解下列问题之一的回溯法：骑士问题、独立钻石问题、智力拼图问题。
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 14 -
授课类型 理论课 授课题目（教学章节或主题）：
第十三章 回溯法<续2>—分枝限界法（Ｂｒａｎｃｈ ａｎｄ Ｂｏｕｎｄ）
授课时间
第 １４ 周
（３学时）
教学目标或要求：
了解分枝限界法的应用范围，熟悉分枝限界法的基本思想、种类及特点，掌握针对具体问题设计分枝限界算法的基本步骤和方法。
教学内容（包括基本内容、重点、难点）：
１．引言
强调：分枝限界法是另一种通用的穷举方法，一种在状态空间树上系统且具有跳跃性的搜索方法。其基本思想是：树的宽度优先搜索或优先队列搜索＋剪枝操作。
２．分枝限界法的适用问题
存在性问题；最优化问题
强调：约束条件一般要求满足完备性性质。
３．分枝限界算法的基本框架（Ｔｈｅ Ｇｅｎｅｒａｌ Ｂｒａｎｃｈ ａｎｄ Ｂｏｕｎｄ Ｍｅｔｈｏｄ）
分枝限界算法基本要素：解空间的树形表示，剪枝操作，成本函数；
设计分枝限界算法的基本步骤；分枝限界算法的形式和终止条件；
分枝限界算法的种类；分枝限界算法与回溯法的区别。
４．分枝限界算法求解问题举例（Ａｐｐｌｉｃａｔｉｏｎｓ）
九宫重排问题；０／１背包问题
强调：使用分枝限界法求解问题的关键是要设计好构成算法的基本要素，特别是成本函数的设计（启发式信息的挖掘）。分枝限界算法通过启发式信息，往往能快速得到问题的解。
重点：具体分枝限界算法的基本要素的设计；分枝限界算法搜索过程的理解。
难点：成本函数的设计（启发式信息的挖掘）。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。通过软件的动态演示让学生理解分枝限界算法的搜索过程。
思考题、讨论题、作业：
P228—13.21（要求：给出求解问题的分枝限界算法的基本要素即可）
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 15 -
授课类型 理论课 授课题目（教学章节或主题）：
第十三章 回溯法<续3>—分枝限界法（Ｂｒａｎｃｈ ａｎｄ Ｂｏｕｎｄ）
授课时间
第 １５ 周
（３学时）
教学目标或要求：
通过具体应用进一步熟练掌握使用分枝限解法求解问题的基本步骤和方法，并能编程序实现算法。了解分枝限界算法的效率估计方法。
教学内容（包括基本内容、重点、难点）：
４．分枝限界法求解问题举例——旅行商问题
强调：使用分枝限界法求解问题的关键是要设计好构成回溯算法的基本要素。
５．分枝限界法编程举例
以设计解０／１背包问题的分枝限界算法为例，主要说明实现算法时的数据结构：
活结点表（Ｏｐｅｎ表）——大根堆
得到最优值后，如何构造最优解？Ｃｌｏｓｅｄ表——链表
模拟运行实例：［实例］ ｎ＝４，Ｍ＝１５，Ｐ（１：４）＝（１０，１０，１２，１８），Ｗ（１：４）＝（２，４，６，９）。
６．分枝限界法的效率分析
方法与回溯法类似。
强调：分枝限界法的优点在通过启发式信息，往往能快速得到问题的解。其缺点在于需要的空间可能相当大。
重点：具体分枝限界算法的基本要素的设计；分枝限界法的实现。
难点：成本函数的设计（启发式信息的挖掘）；分枝限界法的实现。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。使用多媒体演示。通过举例和图示来阐述算法的要素及其程序的执行过程。
思考题、讨论题、作业：
１．回溯法与分枝限界法各自的优缺点是什么？ ２．编程实现P228-13.21中的分枝限界算法。 参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 16 -
授课类型 理论课 授课题目（教学章节或主题）：
第十四章 随机算法（Ｒａｎｄｏｍｉｚｅｄ Ａｌｇｏｒｉｔｈｍｓ）
授课时间
第 １６ 周
（３学时）
教学目标或要求：
了解随机算法的基本特征。熟悉数值随机算法、舍伍德算法、拉斯维加斯算法、蒙特卡洛算法的特点和适用范围，掌握其简单应用。
教学内容（包括基本内容、重点、难点）：
１．引入——介绍随机算法的基本特征。与确定性算法相比，随机算法有如下特征：
（１）允许算法在执行过程中随机地选择一个计算步骤；（２）运行时间和空间性能好；
（３）设计和实现都很简单；（４）不能保证对所有输入产生正确的结果；
（５）对同一问题实例用同一个概率算法求解两次可能产生完全不同的效果；
２． 数值随机算法及其应用举例
算法特点及适用范围；典型应用举例：使用随机投点法来求π的近似值、求定积分的近似值。 ３． 舍伍德算法（Ｓｈｅｒｗｏｏｄ ａｌｇｏｒｉｔｈｍｓ）及其应用举例
算法特点及适用范围；典型应用举例：随机快速排序算法、随机选择算法。
４．拉斯维加斯算法（Ｌａｓ Ｖｅｇａｓ ａｌｇｏｒｉｔｈｍｓ）及其应用举例
算法特点及适用范围；应用举例：求皇后问题。强调：拉斯维加斯算法往往能快速地求解问题，且一旦得到问题的一个解，一定是正确的。但是，这种算法所作随机性决策有可能导致找不到问题的解。此时，可通过多次调用同一拉斯维加斯算法来增加得到问题解的概率。
５． 蒙特卡洛算法（Ｍｏｎｔｅ Ｃａｒｌｏ ａｌｇｏｒｉｔｈｍｓ）及其应用举例
算法特点及适用范围；应用举例：找主元素等。强调：使用蒙特卡洛算法肯定能得到问题的一个解，但这个解未必是正确的。可以通过重复调用同一个蒙特卡洛算法多次来提高获得正确解的概率。 重点：各算法的基本思想。
难点：算法的误差分析，要求学生熟悉概率论知识。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。通过举例和程序演示来阐述各类随机算法的基本思想。
思考题、讨论题、作业：
1．P241—14.8,14.9 2．通过实验来比较两个随机算法的效果：Algorithm 14.1和Ａｌｇｏｒｔｉｔｈｍ14.5。 参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 17 -
授课类型 理论课 授课题目（教学章节或主题）：
课程总复习
授课时间
第 １７ 周
（３学时）
教学目标或要求：
通过课程总复习使学生熟悉本课程各章需要掌握的知识要点，熟练掌握算法分析的基本方法和算法设计的基本技术。
教学内容（包括基本内容、重点、难点）：
课程总复习
一、算法分析的基本方法
1．渐近记号O 、W 、 Q的含义
２．最好、最坏、平均时间（空间）复杂度
3．简单求和公式、定积分求和
４．简单递归方程的解法
二、算法设计的常用方法
１．归纳技术
２．分治法
３．动态规划法
４．贪心法
５．图的遍历——深度优先遍历和宽度优先遍历
６．回溯法和分枝限界法
７．随机算法
强调：掌握每一种算法设计方法的基本思想、适用范围、算法分析方法、典型应用等。
重点：各算法的基本思想及其应用。
教学手段与方法：
手段：多媒体授课。
方法：讲授法。使用多媒体展示各章知识要点。
思考题、讨论题、作业：
根据复习内容，在课本各章后面的习题中挑选少量相关习题供学生讨论、思考。
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 18 -
授课题目（教学章节或主题）：
授课类型 实验课
实验一 分类算法平均性能比较
授课时间 第 ６ 、７周
教学目标或要求：
通过实验比较归并分类与快速分类算法的平均时间效率；加深对时间复杂度概念的理解。
教学内容（包括基本内容、重点、难点）：
1．实验任务
（1）用C/C++语言编程实现归并分类算法6.3 和快速分类算法6.6。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。
（2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行快速分类和归并分类算法，并记录各自的运行时间（以毫秒为单位）。
（3）根据实验数据及其结果来比较快速分类和归并分类算法的平均时间，并得出结论。
2．主要步骤
（1）根据实验目标，明确实验的具体任务；
（2）理解实验所涉及的两个分类算法；
（3）编写程序实现两个分类算法；
（4）设计实验数据并运行程序、记录运行的结果；
（5）根据实验数据及其结果得出结论；
（6）写出实验后的心得体会。
教学手段与方法：
手段：上机编程实验。
方法：由学生独立完成实验任务，教师可加以辅导。
实验设备及环境：PC；C/C++等编程语言。
思考题、讨论题、作业：
使用3个学时来完成实验一。
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7 注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 19 -
授课题目（教学章节或主题）：
授课类型 实验课
实验二 动态规划法的应用
授课时间 第 ８、９ 周
教学目标或要求：
通过实验，掌握用动态规划方法求解实际问题的基本思路；进一步理解动态规划方法的实质，巩固设计动态规划算法的基本步骤。
教学内容（包括基本内容、重点、难点）：
1．实验任务
（1）设计动态规划算法求解资源分配问题，给出算法的非形式描述。
（2）在Windows环境下用C语言实现该算法。计算10个实例，每个实例中n=30，m=10，C i j为随机产生于范围（0，103）内的整数。记录各实例的数据及执行结果（即最优分配方案、最优分配方案的值）、运行时间。（3）从理论上分析算法的时间和空间复杂度，并由此解释相应的实验结果。
2．主要步骤
（1）根据实验目标，明确实验的具体任务；
（2）分析资源分配问题，获得计算其最优值的递推计算公式；
（3）设计求解问题的动态规划算法，并编写程序实现算法；
（4）设计实验数据并运行程序、记录运行的结果；
（5）分析算法的时间和空间复杂度，并由此解释释相应的实验结果；
（6）写出实验后的心得体会。
重点、难点：递推计算公式的获得
教学手段与方法：
手段：上机编程实验。
方法：由学生独立完成实验任务，教师可加以辅导。
实验设备及环境：PC；C/C++等编程语言。
思考题、讨论题、作业：
使用3个学时完成实验二。
参考资料（含参考书、文献等）：
1．计算机算法基础(第二版)，余祥宣、崔国华、邹海明，华中科技大学出版社，2000.1 2．Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出版社，2001.7
注：１、每项页面大小可自行添减；２一次课为一个教案；３、“重点”、“难点”、“教学手段与
方法”部分要尽量具体；４、授课类型指：理论课、讨论课、实验或实习课、练习或习题课等。
- 20 -
《计算机算法设计与分析》习题及答案 一．选择题 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 ）。
算法设计与分析考试题 及答案 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
华南农业大学期末考试试卷（A卷） 2004学年第二学期(2005.6)考试科目：算法设计与分析考试类型：（开卷）考试时间：120分钟 学号姓名年级专业 一、选择题（30分，每题2分） 1、一个算法应该包含如下几条性质，除了 A 。 （A）二义性（B）有限性（C）正确性（D）可终止性 2、解决一个问题通常有多种方法。若说一个算法“有效”是指 D 。 （A）这个算法能在一定的时间和空间资源限制内将问题解决 （B）这个算法能在人的反应时间内将问题解决 （C）这个算法比其他已知算法都更快地将问题解决 （D）A和C 3、当输入规模为n时，算法增长率最小的是 B 。 （A）5n （B）20log2n（C）2n2（D）3nlog3n 4、渐进算法分析是指 B 。 （A）算法在最佳情况、最差情况和平均情况下的代价 （B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析（C）数据结构所占用的空间 （D）在最小输入规模下算法的资源代价 5、当上下限表达式相等时，我们使用下列哪种表示法来描述算法代价？C （A）大O表示法（B）大Ω表示法 （C）Θ表示法（D）小o表示法 6、采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素。以下对顺序搜索法分析正确的是 B 。
（A）最佳情况、最差情况和平均情况下，顺序搜索法的渐进代价都相同 （B）最佳情况的渐进代价要好于最差情况和平均情况的渐进代价 （C）最佳情况和平均情况的渐进代价要好于最差情况的渐进代价 （D）最佳情况的渐进代价要好于平均情况的渐进代价，而平均情况的渐进代价要好于最差情况的渐进代价 7、递归通常用 C 来实现。 （A）有序的线性表（B）队列（C）栈（D）数组 8、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。C （A）问题规模相同，问题性质相同 （B）问题规模相同，问题性质不同 （C）问题规模不同，问题性质相同 （D）问题规模不同，问题性质不同 9、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n 个元素进行划分，如何选择划分基准？下面 D 答案解释最合理。 （A）随机选择一个元素作为划分基准 （B）取子序列的第一个元素作为划分基准 （C）用中位数的中位数方法寻找划分基准 （D）以上皆可行。但不同方法，算法复杂度上界可能不同 10、对于0－1背包问题和背包问题的解法，下面 C 答案解释正确。 （A）0－1背包问题和背包问题都可用贪心算法求解 （B）0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解 （C）0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解 （D）因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解 11、关于回溯搜索法的介绍，下面D是不正确描述。 （A）回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解（B）回溯法是一种既带系统性又带有跳跃性的搜索算法 （C）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯 （D）回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径 改：树结构 回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结
算法设计与分析 实 验 报 告 班级： 姓名： 学号： (备注：共给出5个参考实验案例，根据学号尾数做对应的实验，即如尾号为1，则模仿案例实验123；尾号2，则模仿案例实验234；尾号3，即345；尾号4，同1.)
目录 实验一分治与递归 (1) 1、基本递归算法 (1) 2、棋盘覆盖问题 (2) 3、二分搜索 (3) 4、实验小结 (5) 实验二动态规划算法 (5) 1、最长公共子序列问题 (5) 2、最大子段和问题 (7) 3、实验小结 (8) 实验三贪心算法 (8) 1、多机调度问题 (8) 2、用贪心算法求解最小生成树 (10) 3、实验小结 (12) 实验四回溯算法和分支限界法 (12) 1、符号三角形问题 (12) 2、0—1背包问题 (14) 3、实验小结 (18) 实验五多种排序算法效率比较 1、算法：起泡排序、选择排序、插入排序、shell排序，归并排序、快速排序等 (19) 2、实验小结 (18)
P art1：课程设计过程 设计选题--→题目分析---→系统设计--→系统实现--→结果分析---→撰写报告 P art2：课程设计撰写的主要规范 1.题目分析：主要阐述学生对题目的分析结果，包括题目描述、 分析得出的有关模型、相关定义及假设； 2.总体设计：系统的基本组成部分，各部分所完成的功能及相互 关系； 3.数据结构设计：主要功能模块所需的数据结构，集中在逻辑设 计上； 4.算法设计：在数据结构基础上，完成算法设计； 5.物理实现：主要有数据结构的物理存储，算法的物理实现，系 统相关的实现。具体在重要结果的截图，测试案例的结果数据，核心算法的实现结果等； 6.结果分析：对第五步的分析，包括定性分析和定量分析，正确 性分析，功能结构分析，复杂性分析等； 7.结论：学生需对自己的课程设计进行总结，给出评价，并写出 设计体会； 8.附录：带有注释的源代码，系统使用说明等； 9.参考文献：列出在撰写过程中所需要用到的参考文献。
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算法的思想。
《算法分析与设计》课程教学大纲 【课程编号】：14314025 【英文译名】：Analysis and Design of Computer Algorithms 【适用专业】：软件工程、计算机科学与技术、信息安全 【学分数】：3 【总学时】：48学时 【实践学时】：0 一、本课程教学目的和课程性质 本课程是软件工程、计算机科学与技术、信息安全等专业的选修课程，也可作为其它计算机相关专业的选修课程。课程属于专业教育课。 课程主要介绍计算机算法分析、算法设计及复杂性理论的基本概念、基本的算法分析方法和常用的算法设计方法。通过本课程的教学，强化学生算法分析与设计的基础理论知识，使学生掌握计算机算法分析的基本方法及常见的算法设计方法（如：分治法、回溯法、贪心法、动态规划法、分枝限界法等）。通过学习，学生能够用利用常见的算法设计方法来解决软件开发中的实际问题。培养扎实的专业知识和基本技能和从事应用软件开发和测试的能力。 二、本课程的基本要求 本课程的基本要求是让学生理解计算机算法效率分析与设计所涉及的基本概念和基础知识，掌握基本的算法分析方法和常见的算法设计方法，能熟练应用课程介绍的算法设计方法来解决软件开发中的实际问题。通过对算法实例的分析，进一步加深学生对算法设计方法的认识和理解。 1、理解算法的基本概念和算法的效率分析方法。 2、理解分治策略的原理、效率分析，掌握分支策略在常见问题（如：二分检索、归并分类、快速排序、选择问题等）问题中的应用。了解分治策略的变形（减治策略、变治策略）的思想和简单应用。 3、理解动态规划的原理、适用条件，了解算法的效率，掌握该算法在常见问题（如：多段图、最优二分检索树、0/1背包问题、货郎担问题、可靠性设计等）问题中的应用。 4、理解贪心方法的原理、效率分析方法，掌握在常见问题（如：背包问题、带有期限的作业排序、最小生成树、单源点最短路径等）问题中的应用。 5、理解回溯法的原理，掌握在常见问题（如：8-皇后、子集和数、图的着色、哈密顿环等）问题中的简单应用。 6、了解分支-限界方法的基本思想和简单应用。 7、了解基本的检索和周游方法的基本思想。 8、了解NP-难度和NP-完全问题基本思想和简单应用。 9、了解概率算法的基本思想及简单应用。 三、本课程与其他课程的关系
内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(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
成绩评定表 学生姓名吴旭东班级学号1309010236 专业信息与计算 科学课程设计题目 分治法解决棋盘覆 盖问题；回溯法解 决数字拆分问题 评 语 组长签字： 成绩 日期20 年月日
课程设计任务书 学院理学院专业信息与计算科学 学生姓名吴旭东班级学号1309010236 课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题实践教学要求与任务: 要求： 1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。 2．培养学生自学参考书籍，查阅手册、和文献资料的能力。 3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4．了解与课程有关的知识，能正确解释和分析实验结果。 任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1.运用分治算法求解排序问题。 2. 运用回溯算法求解N后问题。 工作计划与进度安排: 第12周：查阅资料。掌握算法设计思想，进行算法设计。 第13周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年月日专业负责人： 201 年月日 学院教学副院长： 201 年月日
算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法 （Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上， 恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。 关键词：分治法，回溯法，棋盘覆盖，数字拆分
湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型: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、二分搜索算法是利用（ 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 ）。
算法设计技巧与分析习题答案 【篇一：算法设计与分析考试题及答案】 一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要 特性:_________,________,________,__________,__________。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.若n=4，在机器m1和m2上加工作业i所需的时间分别为ai和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业 的最优调度方案，并计算最优值。 4.使用回溯法解0/1背包问题：n=3，c=9，v={6,10,3}，w={3,4,4}, 其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示 其解空间（从根出发，左1右0），并画出其解空间树，计算其最优 值及最优解。 6.描述0-1背包问题。三、简答题（30分） 1.流水作业调度中，已知有n个作业，机器m1和m2上加工作业i 所需的时间分别为ai和bi，请写出流水作业调度问题的johnson法 则中对ai和bi的排序算法。（函数名可写为sort(s,n)）
算法设计技巧与分析 参考答案 第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 不能用 关系来比较2n 和2100n 增长的阶。 ∵221 lim 0100100 n n n →∞=≠ 2n ∴不是2(100)o n 的，即不能用 关系来比较2n 和2100n 增长 的阶。 1.32
一、填空题（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
算法：EX5_33 输入：已排序的数组A[1,…,n]，整数x 输出：如果A中存在两个数，它们的和是x，则输出这两个数，若不存在，则输出none find(1,n) end EX5_33 过程：find(s,t) // 确定A[s,…,t]中是否存在两个数，它们的和是x，如果存在则输出这两个数，若不存在，则输出none if s=t then output none; else if s EX6_51 输入： 输出： h=high(R) return h end EX6_51 过程high(T) // if T为空then return -1 else left=high(T->left); right=high(T->right); return 1+max{left,right} end if end high 递归出口T->left == null and T->right==null then return 0 ? 全局变量？ 6.52 算法SECONDV ALUE 输入：正整数n和存储n个元素的数组a[1..n] 输出：数组a的第二大元素 (x1,x2)=secondvalue(1,n,a); return x2; end SECONDV ALUE 过程secondvalue(low,high,a) //返回数对(x1,x2)其中x1>=x2 if high-low=0 then return (a[low],-∞); //这个地方有修改else if high-low=1 then if a[high]>=a[low] then return (a[high],a[low]); else return (a[low],a[high]); end if end if end if mid=(low+high)/2; (x1,x2)=secondvalue(low,mid,a); (y1,y2)=secondvalue(mid+1,high,a); 实验一、归并排序及各种排序算法性能比较 一、实验实习目的及要求 了解归并排序等各种排序算法，并能独立在计算机上实现，同时并能够计算它们的时间复杂度，并用计算机来验证。 二、实验实习设备（环境）及要求（软硬件条件） 计算机eclipse软件，执行环境JavaSE-1.8. 三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明) 项目：对10 4 6 3 8 2 5 7进行从小到大排序，采用几种排序方法，并统计这几种方法的运行时间，与归并排序比较。 内容及步骤： (1)归并排序：将序列每次分成两组，再进行合并，直到递归完成； 1、递归调用mergeSort对数组排序 2、merge将两个有序数组合并为一个有序数组 3、主函数调用mergeSort对数组排序 4、统计时间 (2) 选择排序：每次选择一个当前最小的并和当前的相对的第一个元素交换，直到最后 只有一个元素时结束；也可选择当前最大的并与当前的相对的最后一个 元素交换，直到最后只有一个元素时结束。 1、数组长度为n，需要选择n-1次；每次选择完成后，将数组中的最大值与最后一 个元素互换，调用java.util包中Arrays类。 2、主函数调用ChooseSort对数组排序。 3、统计运行时间。 (3)插入排序：从第二个元素开始，每次插入一个到当前有序序列中，使得有序，当 所有的元素插入完毕时，就排好序了； 1、从第二个元素开始，与之前序列比较，插入到合适的位置。 2、主函数调用sort对数组排序。 3、统计运行时间 (4) 快速排序：每次选择一个中间元素，并进行交换，使得中间元素的左边比它小，右 边比它大，然后对左右两边进行递归； 1、选取一个基准位，从右边向左边看，找比基准位小的元素，再从左边向右边看， 找比基准位大的元素，若两者均存在则交换；若两者相遇，则相遇元素与基准位元素交换，然后递归排序左右半数组。 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： 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.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 。 计算机算法设计与分析小论文 摘要： 算法是一个系列解决问题的清晰指令,即在有限时间内能够对一定规范的输入,能够得到所需要的输出。如果一个算法本身是有缺陷的!那么他往往不是这个问题的最佳解决方法,可见一个算法的优劣是通过一定的准则来规定的。通过这学期的对《计算机算法分析设计》这门课程的学习让我们充分的了解到了计算机算法的多样性和复杂性，让我们更加细心和耐心的去对待这门课程。例如甲某要去某个地方旅游,他有很多种方案到旅游地,但是不见的每种方案都是合理最优的!这时就是需要考虑透过一定的算法来得到自己的最优路线。所以可见算法就是以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件，必须遵循软件工程的原则，设计出高效率的程序。一个高效的程序不仅需要编程技巧，更需要合理的数据组织和清晰高效的算法。目前我们将进行常见的算法分析设计策略介绍： 1.递归算法 1.1递归算法介绍: 直接或间接的调用自身的算法称为递归算法。或者说就是用自己来定义自己,不断调用自己的某一种状态。 1.2递归算法满足的条件 （1）递归满足2个条件： 1）有反复执行的过程（调用自身） 2）有跳出反复执行过程的条件（递归出口） 1.3递归例子 递归例子：阶乘问题 n! = n * (n-1) * (n-2) * ...* 1(n>0) //阶乘 intresult(int i) { int sum = 0; if (0 == i) return (1); else sum = i * result(i-1); return sum; } 可见一个递归算法都有一个比较特殊的特点,那就是要先处理一些比较特殊的情况再处理递归关系。如上例中如果是0!的话！那么他的阶乘就是1，所以先处理0!这个特殊情况，然后再调用其他的递归关系得到自己想要的阶乘。比如当我们想要求出4!的结果那么我们就需要调用result(3)的结果而result(3)又要调用result(2)的结果！就这样直到得出答案为止。 在我们日常,递归算法的出现可以帮助我们解决很多问题,正因为它的：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 2.分治算法 2.1分治算法介绍: 一个分治算法把问题实例划分成若干子实例（多数情况是分成两个），并分别递归地解决每个子实例，然后把这些子实例的解组合起来，得到原问题实例的解。 2.2 分治算法的特性 1）规模小，则很容易解决 2）大问题可以分为若干规模小的相同问题 3）利用子问题的解可以合并成该问题的解 2.3分治算法的遇到问题 为了阐明这个方法，考虑这样一问题：在一个整数组A[1...n]中，同时寻找最大值和最小值。下面我们来看一下用分治策略：将数组分割成两半，A[1...n/2]和A[(n/2)+1...n]，在每一半中找到最大值和最小值，并返回这两个最小值中的最小值及这两个最大值中的最大值。 过程 Min-Max ⅰ输入 n个整数元素的数组A[1...n]n为2的幂 ⅱ输出 (x,y), A中的最大元素和最小元素算法分析与设计实验报告
算法设计与分析试卷及答案.doc
算法设计技巧与分析答案上课讲义
计算机算法设计与分析小论文
相关主题
文本预览