《算法设计与分析》课后习题答案

本教材为计算机科学技术专业核心课程“算法设计与分析”教材.全书以算法设计技术和分析方法为主线来组织各知识单元，主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、算法分析与问题的计算复杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等.书中突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出适当的建议，同时也简要介绍了计算复杂性理论的核心内容和处理难解问题的一些新技术.

本书有配套的学习指导与习题解析用书以及PPT电子教案.

本书可作为大学计算机科学与技术、软件工程、信息安全、信息与计算机科学等专业本科生和研究生教学用书，也可以作为从事实际问题求解的算法设计与分析工作的参考书.

目录

• 目 录CONTENTS第1章 基础知识1
• 1.1 有关算法的基本概念1
• 1.2 算法的伪码描述5
• 1.3 算法的数学基础6
• 1.3.1 函数的渐近的界6
• 1.3.2 求和的方法10
• 1.3.3 递推方程求解方法12
• 习题121
• 第2章 分治策略25
• 2.1 分治策略的基本思想25
• 2.1.1 两个熟悉的例子 25
• 2.1.2 分治算法的一般性描述26
• 2.2 分治算法的分析技术26
• 2.3 改进分治算法的途径30
• 2.3.1 通过代数变换减少子问题个数30
• 2.3.2 利用预处理减少递归内部的计算量33
• 2.4 典型实例36
• 2.4.1 快速排序算法36
• 2.4.2 选择问题39
• 2.4.3 n-1次多项式在全体2n次方根上的求值43
• 习题246
• 第3章 动态规划51
• 3.1 动态规划的设计思想51
• 3.1.1 多起点、多终点的最短路径问题51
• 3.1.2 使用动态规划技术的必要条件53
• 3.2 动态规划算法的设计要素54
• 3.2.1 子问题的划分和递推方程55
• 3.2.2 动态规划算法的递归实现56
• 3.2.3 动态规划算法的迭代实现57
• 3.2.4 一个简单实例的计算过程58
• 3.3 动态规划算法的典型应用59
• 3.3.1 投资问题59
• 3.3.2 背包问题61
• 3.3.3 最长公共子序列LCS 64
• 3.3.4 图像压缩67
• 3.3.5 最大子段和71
• 3.3.6 最优二分检索树74
• 3.3.7 生物信息学中的动态规划算法78
• 习题381
• 目  录   算法设计与分析第4章 贪心法85
• 4.1 贪心法的设计思想85
• 4.2 关于贪心法的正确性证明88
• 4.3 对贪心法得不到最优解情况的处理92
• 4.4 贪心法的典型应用96
• 4.4.1 最优前缀码96
• 4.4.2 最小生成树101
• 4.4.3 单源最短路径106
• 习题4108
• 第5章 回溯与分支限界112
• 5.1 回溯算法的基本思想和适用条件112
• 5.1.1 几个典型的例子112
• 5.1.2 回溯算法的适用条件116
• 5.2 回溯算法的设计步骤117
• 5.2.1 回溯算法的递归实现和迭代实现117
• 5.2.2 几个典型的例子118
• 5.3 回溯算法的平均效率和改进途径120
• 5.4 分支限界122
• 5.4.1 背包问题123
• 5.4.2 最大团问题125
• 5.4.3 货郎问题125
• 5.4.4 圆排列问题127
• 5.4.5 连续邮资问题129
• 习题5130
• 第6章 算法分析与问题的计算复杂度132
• 6.1 平凡下界133
• 6.2 直接计数求解该问题所需要的最少运算 134
• 6.3 决策树135
• 6.4 检索算法的时间复杂度分析136
• 6.5 排序算法的时间复杂度分析138
• 6.5.1 冒泡排序算法138
• 6.5.2 堆排序算法139
• 6.5.3 排序算法的决策树与算法类时间复杂度的下界144
• 6.6 选择算法的时间复杂度分析146
• 6.6.1 找最大和最小问题147
• 6.6.2 找第二大问题148
• 6.6.3 找中位数的问题150
• 6.7 通过归约确认问题计算复杂度的下界152
• 习题6153
• 第7章 NP完全性155
• 7.1 P类与NP类155
• 7.1.1 易解的问题与难解的问题155
• 7.1.2 判定问题157
• 7.1.3 NP类159
• 7.2 多项式时间变换与NP完全性160
• 7.2.1 多项式时间变换160
• 7.2.2 NP完全性162
• 7.2.3 Cook-Levin定理--第一个NP完全问题163
• 7.3 几个NP完全问题163
• 7.3.1 最大可满足性与三元可满足性163
• 7.3.2 顶点覆盖、团与独立集165
• 7.3.3 哈密顿回路与货郎问题167
• 7.3.4 恰好覆盖169
• 7.3.5 子集和、背包、装箱与双机调度171
• 习题7174
• 第8章 近似算法176
• 8.1 近似算法及其近似比176
• 8.2 多机调度问题177
• 8.2.1 贪心的近似算法177
• 8.2.2 改进的贪心近似算法178
• 8.3 货郎问题179
• 8.3.1 最邻近法179
• 8.3.2 最小生成树法180
• 8.3.3 最小权匹配法181
• 8.4 背包问题182
• 8.4.1 一个简单的贪心算法182
• 8.4.2 多项式时间近似方案182
• 8.4.3 伪多项式时间算法与完全多项式时间近似方案183
• 习题8185
• 第9章 随机算法187
• 9.1 概率论预备知识187
• 9.2 对随机快速排序算法的分析189
• 9.3 随机算法的分类及其局限性191
• 9.3.1 拉斯维加斯型随机算法191
• 9.3.2 蒙特卡洛型随机算法191
• 9.3.3 随机算法的局限性192
• 9.4 素数检验和多项式恒等检验193
• 9.4.1 素数检验193
• 9.4.2 多项式恒等检验194
• 9.5 随机游动算法195
• 9.5.1 有限马氏链及其表示195
• 9.5.2 求解二元布尔可满足性问题的随机游动算法196
• 习题9197
• 第10章 处理难解问题的策略198
• 10.1 对问题施加限制198
• 10.1.1 二元可满足性问题199
• 10.1.2 霍恩公式可满足性问题200
• 10.2 固定参数算法201
• 10.3 改进指数时间算法203
• 10.4 启发式方法205
• 10.5 平均情形的复杂性206
• 10.6 难解算例生成208
• 10.6.1 相变现象与难解性208
• 10.6.2 隐藏解的难解算例210
• 10.7 基于统计物理的消息传递算法211
• 10.7.1 消息传递算法与回溯法、局部搜索算法的比较211
• 10.7.2 基于统计物理的消息传递算法212
• 10.8 量子算法简介213
• 10.8.1 量子比特213
• 10.8.2 正交测量214
• 10.8.3 量子门215
• 10.8.4 一个量子算法216
• 习题10218
• 参考文献219
• 第1章 程序设计概述11.1 学习要点1
• 1.2 Visual C++ 6.0集成开发环境1
• 1.2.1 Visual C++ 6.0开发环境介绍1
• 1.2.2 创建一个C源程序6
• 1.2.3 C源程序的编译、连接和运行12
• 1.2.4 C程序的单步调试命令13
• 1.2.5 C程序的调试窗口18
• 1.2.6 创建一个项目文件(工程)28
• 1.3 实验 认识Visual C++ 6.0的开发环境32
• 1.4 常见错误及解决方法33
• 第2章 C语言基础知识34
• 2.1 学习要点34
• 2.2 实验内容36
• 2.2.1 实验1 变量的使用与赋值运算36
• 2.2.2 实验2 格式化输入输出函数的应用37
• 2.2.3 实验3 宏定义、条件编译编程39
• 2.2.4 实验4 位运算编程39
• 2.3 常见错误及解决方法40
• 第3章 程序的控制结构46
• 3.1 学习要点46
• 3.2 实验内容48
• 3.2.1 实验1 if语句编程48
• 3.2.2 实验2 switch语句编程50
• 3.2.3 实验3 循环结构编程50
• 3.3 常见错误及解决方法51目  录   程序设计基础(C语言)实验指导第4章 数组58
• 4.1 学习要点58
• 4.2 实验内容62
• 4.2.1 实验1 一维数组编程62
• 4.2.2 实验2 二维数组编程63
• 4.2.3 实验3 字符数组编程64
• 4.3 常见错误及解决方法65
• 第5章 函数69
• 5.1 学习要点69
• 5.2 实验内容70
• 5.2.1 实验1 简单函数编程70
• 5.2.2 实验2 综合运用一维数组和函数编程71
• 5.2.3 实验3 综合运用二维数组和函数编程73
• 5.2.4 实验4 递归函数与分治算法编程75
• 5.2.5 实验5 变量的存储类别、内部与外部函数编程75
• 5.3 常见错误及解决方法77
• 第6章 指针84
• 6.1 学习要点84
• 6.2 实验内容87
• 6.2.1 实验1 指向变量的指针变量编程87
• 6.2.2 实验2 字符指针编程88
• 6.2.3 实验3 指向一维数组的指针变量编程89
• 6.2.4 实验4 指向二维数组的指针变量编程90
• 6.2.5 实验5 动态数组编程91
• 6.3 常见错误及解决方法92
• 第7章 结构体与链表96
• 7.1 学习要点96
• 7.2 实验内容98
• 7.2.1 实验1 结构体变量与结构体数组编程98
• 7.2.2 实验2 链表基本操作编程99
• 7.2.3 实验3 链表复杂应用编程101
• 7.3 常见错误及解决方法102
• 第8章 文件105
• 8.1 学习要点105
• 8.2 实验内容107
• 8.2.1 实验1 文件顺序读写编程107
• 8.2.2 实验2 文件随机读写编程108
• 8.3 常见错误及解决方法109
• 第9章 综合程序设计112
• 9.1 学习要点112
• 9.2 实验内容112
• 9.2.1 实验1 通讯录管理系统112
• 9.2.2 实验2 学生成绩管理系统113
• 9.2.3 实验3 高校教师人事管理系统113
• 9.2.4 实验4 企业职工工资管理系统114
• 9.2.5 实验5 仓库物资管理系统115
• 9.2.6 实验6 笔记本电脑销售管理系统116
• 9.2.7 实验7 停车场管理系统117
• 9.2.8 实验8 火车订票管理系统118
• 附录A 常见编译错误和警告121
• 附录B 常用标准库函数123B.1 stdio.h中包括的常用函数123
• B.2 math.h中包括的常用函数129
• B.3 stdlib.h中包括的常用函数132
• B.4 string.h中包括的常用函数135
• B.5 time.h中包括的常用函数138
• B.6 ctype.h中包括的常用函数140
• B.7 conio.h中包括的常用函数142
• 参考文献144