算法设计与实验题解

　　本书是与普通高等教育“十一五”国家级规划教材《计算机算法设计与分析》配套的辅助教材，对主教材中的全部习题做了解答或给出了解题思路提示，并对主教材的内容进行了扩展，有些主教材中无法讲述的较深入的主题以习题的形式展现出来。为了提高学生灵活运用算法设计策略解决实际问题的能力，本书还将主教材中的许多习题改造成算法实现题，要求学生设计出解算法并上机实现。作者还结合精品课程建设，进行了教材的立体化开发，包括主教材、辅助教材、实验与设计、电子课件和教学网站建设。本书附有光盘，包含各章算法实验题目、测试数据和答案。本书内容丰富，理论联系实际，可作为高等学校计算机科学与技术、软件工程、信息与计算科学等专业本科生和研究生学习计算机算法设计的辅助教材，也是工程技术人员和自学者的参考书。

暂缺《算法设计与实验题解》作者简介

第1章 算法概述
习题11 函数的渐近表达式
习题12 O(1)和O(2)的区别
习题14 按渐近阶排列表达式
习题15 算法效率
习题16 硬件效率
习题17 函数渐近阶
习题18 n!的阶
习题110 平均情况下的计算时间复杂性
算法实现题11 统计数字问题
算法实现题12 字典序问题
算法实现题13 最多约数问题
算法实现题14 金币阵列问题
算法实现题15 最大间隙问题
第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(logn)时间算法
习题29 主元素问题的线性时间算法
习题210 无序集主元素问题的线性时间算法
习题211 O(1)空间子数组换位算法
习题212 O(1)空间合并算法
习题213 n段合并排序算法 习题214 自然合并排序算法
习题215 最大值和最小值问题的最优算法 习题216 最大值和次大值问题的最优算法 习题217 整数集合排序
习题218 第k小元素问题的计算时间下界 习题219 非增序快速排序算法
习题220 随机化算法
习题221 随机化快速排序算法
习题222 随机排列算法
习题223 算法QuickSort中的尾递归
习题224 用栈模拟递归
习题225 算法Select中的元素划分
习题226 O(nlogn)时间快速排序算法 习题227 最接近中位数的k个数
习题228 X和Y的中位数
习题229 网络开关设计
习题232 带权中位数问题
习题234 构造Gray码的分治算法
习题235 网球循环赛日程表
习题236 二叉树T的前序、中序和后序序列 算法实现题21 输油管道问题（习题230） 算法实现题22 众数问题（习题231） 算法实现题23 邮局选址问题（习题232） 算法实现题24 马的Hamilton周游路线问题（习题233） 算法实现题25 半数集问题
算法实现题26 半数单集问题
算法实现题27 士兵站队问题
算法实现题28 有重复元素的排列问题
算法实现题29 排列的字典序问题
算法实现题210 集合划分问题
算法实现题211 集合划分问题
算法实现题212 双色Hanoi塔问题
算法实现题213 标准二维表问题
算法实现题214 整数因子分解问题
第3章 动态规划
习题31 最长单调递增子序列
习题32 最长单调递增子序列的O(nlogn)算法 习题37 漂亮打印
习题311 整数线性规划问题
习题312 二维01背包问题
习题314 Ackermann函数
习题317 最短行驶路线
习题319 最优旅行路线
算法实现题31 独立任务最优调度问题(习题33) 算法实现题32 最少硬币问题(习题34) 算法实现题33 序关系计数问题(习题35) 算法实现题34 多重幂计数问题(习题36)
算法实现题35 编辑距离问题(习题38) 算法实现题36 石子合并问题(习题39) 算法实现题37 数字三角形问题(习题310)
算法实现题38 乘法表问题(习题313)
算法实现题39 租用游艇问题(习题315) 算法实现题310 汽车加油行驶问题(习题316) 算法实现题311 最小m段和问题
算法实现题312 圈乘运算问题(习题318) 算法实现题313 最大长方体问题(习题321) 算法实现题314 正则表达式匹配问题(习题322) 算法实现题315 双调旅行售货员问题(习题323) 算法实现题316 最大k乘积问题(习题528)
算法实现题317 最少费用购物问题(习题320)
算法实现题318 收集样本问题
算法实现题319 最优时间表问题
算法实现题320 字符串比较问题
算法实现题321 有向树k中值问题
算法实现题322 有向树独立k中值问题
算法实现题323 有向直线m中值问题
算法实现题324 有向直线2中值问题
算法实现题325 树的最大连通分支问题
算法实现题326 直线k中值问题
算法实现题327 直线k覆盖问题
算法实现题328 m处理器问题
算法实现题329 红黑树的红色内结点问题
第4章 贪心算法
习题42 活动安排问题的贪心选择
习题43 背包问题的贪心选择性质
习题44 特殊的01背包问题
习题410 程序最优存储问题
习题413 最优装载问题的贪心算法
习题418 Fibonacci序列的哈夫曼编码
习题419 最优前缀码的编码序列
习题421 任务集独立性问题
习题422 矩阵拟阵
习题423 最小权最大独立子集拟阵
习题427 整数边权Prim算法
习题428 最大权最小生成树
习题429 最短路径的负边权
习题430 整数边权Dijkstra算法
算法实现题41 会场安排问题(习题41)
算法实现题42 最优合并问题(习题45)
算法实现题43 磁带最优存储问题(习题46)
算法实现题44 磁盘文件最优存储问题(习题47)
算法实现题45 程序存储问题(习题48)
算法实现题46 最优服务次序问题(习题411)
算法实现题47 多处最优服务次序问题(习题412)
算法实现题48 d森林问题(习题414)
算法实现题49 汽车加油问题(习题416)
算法实现题410 区间覆盖问题(习题417)
算法实现题411 硬币找钱问题(习题424)
算法实现题412 删数问题(习题425)
算法实现题413 数列极差问题(习题426)
算法实现题414 嵌套箱问题(习题431)
算法实现题415 套汇问题(习题432)
算法实现题416 信号增强装置问题(习题520)
算法实现题417 磁带最大利用率问题(习题49)
算法实现题418 非单位时间任务安排问题(习题415)
算法实现题419 多元Huffman编码问题(习题420)
算法实现题420 多元Huffman编码变形
算法实现题421 区间相交问题
算法实现题422 任务时间表问题
算法实现题423 最优分解问题
算法实现题424 可重复最优分解问题
算法实现题425 可重复最优组合分解问题
算法实现题426 旅行规划问题
算法实现题427 登山机器人问题
第5章 回溯法
习题51 装载问题改进回溯法1
习题52 装载问题改进回溯法2
习题54 01背包问题的最优解
习题55 最大团问题的迭代回溯法
习题57 旅行售货员问题的费用上界
习题58 旅行售货员问题的上界函数
算法实现题51 子集和问题（习题53） 算法实现题52 最小长度电路板排列问题（习题59） 算法实现题53 最小重量机器设计问题（习题510）
算法实现题54 运动员最佳配对问题（习题514）
算法实现题55 无分隔符字典问题（习题515）
算法实现题56 无和集问题（习题516）
算法实现题57 n色方柱问题（习题517）
算法实现题58 整数变换问题（习题518）
算法实现题59 拉丁矩阵问题
算法实现题510 排列宝石问题（习题519）
算法实现题511 重复拉丁矩阵问题（习题519）
算法实现题512 罗密欧与朱丽叶的迷宫问题（习题521） 算法实现题513 工作分配问题（习题522）
算法实现题514 独立钻石跳棋问题（习题523）
算法实现题515 智力拼图问题（习题524）
算法实现题516 布线问题（习题525）
算法实现题517 最佳调度问题（习题526）
算法实现题518 无优先级运算问题（习题527）
算法实现题519 世界名画陈列馆问题（习题529）
算法实现题520 世界名画陈列馆问题（不重复监视）（习题5
30） 算法实现题521 2×2×2魔方问题
算法实现题522 魔方(Rubik’s Cube)问题（习题531） 算法实现题523 算24点问题
算法实现题524 算m点问题
算法实现题525 双轨车皮编序问题
算法实现题526 多轨车皮编序问题
算法实现题527 部落卫队问题（习题56）
算法实现题528 虫蚀算式问题
算法实现题529 完备环序列问题
算法实现题530 离散01串问题
算法实现题531 喷漆机器人问题
算法实现题532 子集树问题（习题511）
算法实现题533 01背包问题（习题511）
算法实现题534 排列树问题（习题512）
算法实现题535 一般解空间搜索问题（习题513）
算法实现题536 最短加法链问题
算法实现题537 n2-1谜问题
第6章 分支限界法
习题61 01背包问题的栈式分支限界法 习题62 释放结点空间的队列式分支限界法 习题63 及时删除不用的结点
习题64 用最大堆存储活结点的优先队列式分支限界法
习题65 释放结点空间的优先队列式分支限界法
习题66 团顶点数的上界
习题67 团顶点数改进的上界
习题68 修改解旅行售货员问题的分支限界法
习题69 解旅行售货员问题的分支限界法中保存已产生的排列
树
习题610 电路板排列问题的队列式分支限界法
算法实现题61 最小长度电路板排列问题（习题611）
算法实现题62 最小长度电路板排列问题（习题612）
算法实现题63 最小权顶点覆盖问题（习题613）
算法实现题64 无向图的最大割问题（习题614）
算法实现题65 最小重量机器设计问题（习题615）
算法实现题66 运动员最佳配对问题（习题616）
算法实现题67 n皇后问题（习题618）
算法实现题68 圆排列问题（习题619）
算法实现题69 布线问题（习题620）
算法实现题610 最佳调度问题（习题621）
算法实现题611 无优先级运算问题（习题622）
算法实现题612 世界名画陈列馆问题（习题624）
算法实现题613 子集空间树问题（习题625）
算法实现题614 排列空间树问题（习题626）
算法实现题615 一般解空间的队列式分支限界法（习题627）
算法实现题616 子集空间树问题（习题628）
算法实现题617 排列空间树问题（习题629）
算法实现题618 一般解空间的优先队列式分支限界法（习题630）
算法实现题619 骑士征途问题
算法实现题620 推箱子问题
算法实现题621 图形变换问题
算法实现题622 行列变换问题
算法实现题623 重排n2宫问题
算法实现题624 最长距离问题
第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11 整数因子分解算法
习题712 非蒙特卡罗算法的例子
习题713 重复3次的蒙特卡罗算法
习题714 集合随机元素算法
习题715 由蒙特卡罗算法构造拉斯维加斯算法
习题716 产生素数算法
习题719 矩阵方程问题
算法实现题71 模平方根问题（习题710）
算法实现题72 素数测试问题（习题717）
算法实现题73 集合相等问题（习题718）
算法实现题74 逆矩阵问题（习题720）
算法实现题75 多项式乘积问题（习题721）
算法实现题76 皇后控制问题
算法实现题77 3SAT问题
算法实现题78 战车问题
算法实现题79 圆排列问题
算法实现题710 骑士控制问题
算法实现题711 骑士对攻问题
第8章 线性规划与网络流
习题81 线性规划可行区域无界的例子
习题82 单源最短路与线性规划
习题83 网络最大流与线性规划
习题84 最小费用流与线性规划
习题85 运输计划问题
习题86 单纯形算法
习题87 边连通度问题
习题88 有向无环网络的最大流
习题89 无向网络的最大流
习题812 最大流更新算法
习题816 混合图欧拉回路问题
习题822 单源最短路与最小费用流
习题823 中国邮路问题
算法实现题81 飞行员配对方案问题（习题810）
算法实现题82 太空飞行计划问题（习题811）
算法实现题83 最小路径覆盖问题（习题813）
算法实现题84 魔术球问题（习题814）
算法实现题85 圆桌问题（习题815）
算法实现题86 最长递增子序列问题（习题817）
算法实现题87 试题库问题（习题818）
算法实现题88 机器人路径规划问题（习题819）
算法实现题89 方格取数问题（习题820）
算法实现题810 餐巾计划问题（习题821）
算法实现题811 航空路线问题（习题824）
算法实现题812 软件补丁问题（习题825）
算法实现题813 星际转移问题（习题826）
算法实现题814 孤岛营救问题（习题827）
算法实现题815 汽车加油行驶问题（习题828）
算法实现题816 数字梯形问题
算法实现题817 运输问题
算法实现题818 分配工作问题
算法实现题819 负载平衡问题
算法实现题820 深海机器人问题
算法实现题821 最长k可重区间集问题
算法实现题822 最长k可重线段集问题
算法实现题823 火星探险问题
算法实现题824 骑士共存问题
第9章 NP完全性理论与近似算法
习题91 RAM和RASP程序
习题92 RAM和RASP程序的复杂性
习题93 计算nn的RAM程序
习题94 平面图着色问题的绝对近似算法
习题95 最优程序存储问题
习题96 树的最优顶点覆盖
习题97 顶点覆盖算法的性能比
习题98 团的常数性能比近似算法
习题910 旅行售货员问题的常数性能比近似算法
习题911 瓶颈旅行售货员问题
习题912 最优旅行售货员回路不自相交
习题914 集合覆盖问题的实例
习题916 多机调度问题的近似算法
习题917 LPT算法的最坏情况实例
习题918 多机调度问题的多项式时间近似算法
算法实现题91 旅行售货员问题的近似算法（习题99）
算法实现题92 可满足问题的近似算法（习题919）
算法实现题93 最大可满足问题的近似算法（习题920）
算法实现题94 子集和问题的近似算法（习题915）
算法实现题95 子集和问题的完全多项式时间近似算法
算法实现题96 2SAT问题的线性时间算法
算法实现题97 实现算法greedySetCover（习题913）
参考文献