计算机算法设计与分析习题解答

章节摘录

版权页：   插图：   问题描述：1944年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为N行，东西方向被划分为M列，于是整个迷宫被划分为N×M个单元。每一个单元的位置可用一个有序数对（单元的行号，单元的列号）来表示。南北或东西方向相邻的2个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成P类，打开同一类的门的钥匙相同，不同类门的钥匙不同。 大兵瑞恩被关押在迷宫的东南角，即（N，M）单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入（1，1）单元。另外，麦克从一个单元移动到另一个相邻单元的时间为1，拿取所在单元钥匙的时间及用钥匙开门的时间可忽略不计。

前言

　　一些著名的计算机科学家在有关计算机科学教育的论述中认为，计算机科学是一种创造性思维活动，其教育必须面向设计。计算机算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。通过对计算机算法系统的学习与研究，理解和掌握算法设计的主要方法，培养对算法的计算复杂性进行正确分析的能力，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础，对从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者是非常重要和必不可少的。　　电子工业出版社出版的《计算机算法设计与分析（第4版）》是普通高等教育“十一五”国家级规划教材，它是根据教育部高教司主持评审的《中国计算机科学与技术学科教程2002》以及ACM和IEEE/CS CC2001组织编写的教材，在内容选材、深度把握、系统性和可用性方面进行了精心设计，力图适合高校本科生教学对学时数和知识结构的要求。本书是与《计算机算法设计与分析（第4版）》配套的辅助教材，对该书中的习题做了解答或给出了解题思路提示。　　算法设计与分析是计算学科的9个主科目之一，而且在整个学科知识体系中具有学科核心的重要地位，它充分体现了计算机科学方法论的理论、抽象和设计3个过程，知识面较宽，且有一定的深度；算法设计与分析课程需要反复再现计算机科学中用到的大问题的复杂性、效率、抽象的层次、重用、折中等带有普遍性的概念。根据作者多年的教学经验，算法设计与分析课程教学有以下3个特点，这使许多学生感到学习相当困难。　　（1） 按照《中国计算机科学与技术学科教程2002》以及ACM和IEEE/CS CC2001的要求，算法设计与分析课程教学包括的知识点多，内容十分丰富，学习量大。　　（2） 课程内容理论性很强，对学生的抽象思维能力和逻辑推理能力要求较高。　　（3） 课程内容还有很强的实践性，要求学生灵活运用所学到的算法设计策略解决实际问题。　　教材中的课后习题能在很大程度上解决上面所说的困难。《计算机算法设计与分析（第4版）》所配备的习题正是为此目的而设计的。教材出版后，许多读者纷纷要求给出习题解答和提示。为了让使用《计算机算法设计与分析（第4版）》作为教材的师生在广度和深度的各个层面更深刻地理解理论、抽象和设计这3个过程以及重复出现的12个基本概念（绑定、大问题的复杂性、概念和形式模型、一致性和完备性、演化、效率、抽象层次、按空间排序、按时间排序、重用、安全性、折中的结论），作者根据多年的教学经验编写了这本辅助教材，旨在让使用该书的教师更容易教，学生更容易学。为了便于对照阅读，本书的章序与《计算机算法设计与分析（第4版）》保持一致，且一一对应。　　本书的内容是对教材《计算机算法设计与分析（第4版）》的扩展，一些在教材中无法讲述的较深入的主题通过习题的形式展现出来。为了提高学生灵活运用算法设计策略解决实际问题的能力，本书将原教材中的许多习题改造成算法实现题，要求学生不仅设计出解决具体问题的算法，而且能上机实现。其中很多题目使用了多种不同解法，体现了算法的灵活性和适用性。根据作者多年的教学实践，这类算法实现题的教学效果非常好。　　本书内容丰富，理论联系实际，可作为高等学校计算机科学与技术、软件工程、信息安全、信息与计算科学等专业本科生和研究生学习计算机算法设计的辅助教材，也是工程技术人员和自学者的参考书。　　作者还结合国家精品课程建设  ，进行了教材的立体化开发，包括主教材、习题解答、电子课件和教学网站等资源  。欢迎广大读者访问教学网站并提出宝贵意见。　　本书提供的教学资源包含各章算法实现题的题目、测试数据和答案。共有12个子目录，包括：ch1，ch2，…，ch8，midexam1，midexam2，finalexam1，finalexam2。每章的每个算法实现题都对应一个子目录，其中的test子目录中是测试数据，answer子目录中是相应的答案。midexam1和midexam2目录中是两套期中试卷。finalexam1和finalexam2目录中是两套期终试卷。本书主教材提供电子课件，需要者可登录华信教育资源网免费注册下载。算法设计的实现平台是Microsoft Visual Studio 60或Microsoft Visual Studio.NET。采用面向对象的C++语言作为算法描述手段。　　在本书编写过程中，福州大学“211工程”计算机与信息工程重点学科实验室提供了优良的设备与工作环境。电子工业出版社负责本书编辑出版工作的全体同仁为本书的　　出版付出了大量辛勤劳动，他们认真细致，一丝不苟的工作精神保证了本书的出版质量。在此，谨向每位曾经关心和支持本书编写工作的各方面人士表示衷心的谢意！　　作 者

书籍目录

第1章 算法概述 
 算法分析题1 
 1-1 函数的渐近表达式 
 1-2 O(1)和O(2)的区别 
 1-3 按渐近阶排列表达式 
 1-4 算法效率 
 1-5 硬件效率 
 1-6 函数渐近阶 
 1-7 n!的阶 
 1-8 3n+1问题 
 1-9 平均情况下的计算时间复杂性
 算法实现题1 
 1-1 统计数字问题 
 1-2 字典序问题 
 1-3 最多约数问题 
 1-4 金币阵列问题 
 1-5 最大间隙问题 
第2章 递归与分治策略 
 算法分析题2 
 2-1 Hanoi塔问题的非递归算法
 2-2 7个二分搜索算法 
 2-3 改写二分搜索算法 
 2-4 大整数乘法的O(nmlog(3/2))算法 
 2-5 5次n/3位整数的乘法 
 2-6 矩阵乘法 
 2-7 多项式乘积 
 2-8 O(1)空间子数组换位算法 
 2-9 O(1)空间合并算法 
 2-10 n段合并排序算法 
 2-11 自然合并排序算法 
 2-12 第k小元素问题的计算时间下界 
 2-13 非增序快速排序算法 
 2-14 构造Gray码的分治算法 
 2-15 网球循环赛日程表 
 2-16 二叉树T的前序、中序和后序序列 
 算法实现题2 
 2-1 众数问题 
 2-2 马的Hamilton周游路线问题
 2-3 半数集问题 
 2-4 半数单集问题 
 2-5 有重复元素的排列问题 
 2-6 排列的字典序问题 
 2-7 集合划分问题 
 2-8 集合划分问题 
 2-9 双色Hanoi塔问题 
 2-10 标准二维表问题 
 2-11 整数因子分解问题 
第3章 动态规划 
 算法分析题3 
 3-1 最长单调递增子序列 
 3-2 最长单调递增子序列的O(nlogn)算法 
 3-3 整数线性规划问题 
 3-4 二维0-1背包问题 
 3-5 Ackermann函数 
 算法实现题3 
 3-1 独立任务最优调度问题 
 3-2 编辑距离问题 
 3-3 石子合并问题 
 3-4 数字三角形问题 
 3-5 乘法表问题 
 3-6 租用游艇问题 
 3-7 汽车加油行驶问题 
 3-8 最小m段和问题 
 3-9 圈乘运算问题 
 3-10 最大长方体问题 
 3-11 正则表达式匹配问题 
 3-12 双调旅行售货员问题 
 3-13 最大k乘积问题 
 3-14 最少费用购物问题 
 3-15 收集样本问题 
 3-16 最优时间表问题 
 3-17 字符串比较问题 
 3-18 有向树k中值问题 
 3-19 有向树独立k中值问题 
 3-20 有向直线m中值问题
 3-21 有向直线2中值问题 
 3-22 树的最大连通分支问题 
 3-23 直线k中值问题 
 3-24 直线k覆盖问题 
 3-25 m处理器问题 
第4章 贪心算法
 算法分析题4 
 4-1 程序最优存储问题 
 4-2 最优装载问题的贪心算法
 4-3 Fibonacci序列的哈夫曼编码 
 4-4 最优前缀码的编码序列 
 算法实现题4 
 4-1 会场安排问题 
 4-2 最优合并问题 
 4-3 磁带最优存储问题 
 4-4 磁盘文件最优存储问题 
 4-5 程序存储问题 
 4-6 最优服务次序问题 
 4-7 多处最优服务次序问题 
 4-8 d森林问题 
 4-9 汽车加油问题 
 4-10 区间覆盖问题 
 4-11 删数问题 
 4-12 磁带最大利用率问题 
 4-13 非单位时间任务安排问题
 4-14 多元Huffman编码问题 
 4-15 最优分解问题 
第5章 回溯法 
 算法分析题5 
 5-1 装载问题改进回溯法1 
 5-2 装载问题改进回溯法2 
 5-3 0-1背包问题的最优解 
 5-4 最大团问题的迭代回溯法
 5-5 旅行售货员问题的费用上界
 5-6 旅行售货员问题的上界函数
 算法实现题5 
 5-1 子集和问题 
 5-2 最小长度电路板排列问题 
 5-3 最小重量机器设计问题 
 5-4 运动员最佳配对问题 
 5-5 无分隔符字典问题 
 5-6 无和集问题 
 5-7 n色方柱问题 
 5-8 整数变换问题 
 5-9 拉丁矩阵问题 
 5-10 排列宝石问题 
 5-11 重复拉丁矩阵问题 
 5-12 罗密欧与朱丽叶的迷宫问题
 5-13 工作分配问题 
 5-14 布线问题 
 5-15 最佳调度问题 
 5-16 无优先级运算问题 
 5-17 世界名画陈列馆问题 
 5-18 世界名画陈列馆问题（不重复监视） 
 5-19 算m点问题 
 5-20 部落卫队问题 
 5-21 子集树问题 
 5-22 0-1背包问题 
 5-23 排列树问题 
 5-24 一般解空间搜索问题 
 5-25 最短加法链问题 
第6章 分支限界法 
 算法分析题6 
 6-1 0-1背包问题的栈式分支限界法 
 6-2 释放结点空间的队列式分支限界法 
 6-3 及时删除不用的结点 
 6-4 用最大堆存储活结点的优先队列式分支限界法 
 6-5 释放结点空间的优先队列式分支限界法 
 6-6 团顶点数的上界 
 6-7 团顶点数改进的上界 
 6-8 修改解旅行售货员问题的分支限界法 
 6-9 解旅行售货员问题的分支限界法中保存已产生的排列树 
 6-10 电路板排列问题的队列式分支限界法 
 算法实现题6 
 6-1 最小长度电路板排列问题
 6-2 最小权顶点覆盖问题 
 6-3 无向图的最大割问题 
 6-4 最小重量机器设计问题 
 6-5 运动员最佳配对问题 
 6-6 n皇后问题 
 6-7 布线问题 
 6-8 最佳调度问题 
 6-9 无优先级运算问题 
 6-10 世界名画陈列馆问题 
 6-11 子集空间树问题 
 6-12 排列空间树问题 
 6-13 一般解空间的队列式分支限界法 
 6-14 子集空间树问题 
 6-15 排列空间树问题 
 6-16 一般解空间的优先队列式分支限界法 
 6-17 推箱子问题 
第7章 概率算法 
 算法分析题7 
 7-1 模拟正态分布随机变量 
 7-2 随机抽样算法 
 7-3 随机产生m个整数 
 7-4 集合大小的概率算法 
 7-5 生日问题 
 7-6 易验证问题的拉斯维加斯算法 
 7-7 用数组模拟有序链表 
 7-8 O(n3/2)舍伍德型排序算法
 7-9 n后问题解的存在性 
 7-10 整数因子分解算法 
 7-11 非蒙特卡罗算法的例子
 7-12 重复3次的蒙特卡罗算法
 7-13 集合随机元素算法 
 7-14 由蒙特卡罗算法构造拉斯维加斯算法 
 7-15 产生素数算法 
 7-16 矩阵方程问题 
算法实现题7 
 7-1 模平方根问题 
 7-2 素数测试问题 
 7-3 集合相等问题 
 7-4 逆矩阵问题 
 7-5 多项式乘积问题 
 7-6 皇后控制问题 
 7-7 3-SAT问题 
 7-8 战车问题 
第8章 线性规划与网络流 算法分析题8 
 8-1 线性规划可行区域无界的例子
 8-2 单源最短路与线性规划 
 8-3 网络最大流与线性规划 
 8-4 最小费用流与线性规划 
 8-5 运输计划问题 
 8-6 单纯形算法 
 8-7 边连通度问题 
 8-8 有向无环网络的最大流
 8-9 无向网络的最大流 
 8-10 最大流更新算法 
 8-11 混合图欧拉回路问题 
 8-12 单源最短路与最小费用流
 8-13 中国邮路问题 
算法实现题8 
 8-1 飞行员配对方案问题 
 8-2 太空飞行计划问题 
 8-3 最小路径覆盖问题 
 8-4 魔术球问题 
 8-5 圆桌问题 
 8-6 最长递增子序列问题 
 8-7 试题库问题 
 8-8 机器人路径规划问题 
 8-9 方格取数问题 
 8-10 餐巾计划问题 
 8-11 航空路线问题 
 8-12 软件补丁问题 
 8-13 星际转移问题 
 8-14 孤岛营救问题 
 8-15 汽车加油行驶问题 
 8-16 数字梯形问题 
 8-17 运输问题 
 8-18 分配工作问题 
 8-19 负载平衡问题 
 8-20 最长k可重区间集问题 
 8-21 最长k可重线段集问题 
参考文献

编辑推荐

《国家精品课程教材•高等学校规划教材:计算机算法设计与分析习题解答(第2版)》内容丰富，理论联系实际，可作为高等学校计算机科学与技术、软件工程、信息安全、信息与计算科学等专业本科生和研究生学习计算机算法设计的辅助教材，也是工程技术人员和自学者的参考书。

作者简介

《国家精品课程教材•高等学校规划教材:计算机算法设计与分析习题解答(第2版)》是与普通高等教育“十一五”国家级规划教材《计算机算法设计与分析（第4版）》配套的辅助教材和国家精品课程教材，分别对主教材中的算法分析题和算法实现题给出了解答或解题思路提示。为了提高学生灵活运用算法设计策略解决实际问题的能力，《国家精品课程教材•高等学校规划教材:计算机算法设计与分析习题解答(第2版)》还将主教材中的许多习题改造成算法实现题，要求学生设计出求解算法并上机实现。作者还结合国家精品课程建设，进行了教材的立体化开发，包括主教材、习题解答、电子课件和教学网站等资源。《国家精品课程教材•高等学校规划教材:计算机算法设计与分析习题解答(第2版)》教学资料包含各章算法实现题、测试数据和答案，可在华信教育资源网免费注册下载。

图书封面

---

 计算机算法设计与分析习题解答下载

---