算法设计与分析 学习与实验指导 第2版PDF电子书下载

第1章 练习题及参考答案 1

1.1 第1章——概论 2

1.1.1 练习题 2

1.1.2 练习题参考答案 3

1.2 第2章——递归算法设计技术 12

1.2.1 练习题 12

1.2.2 练习题参考答案 13

1.3 第3章——分治法 23

1.3.1 练习题 23

1.3.2 练习题参考答案 25

1.4 第4章——蛮力法 33

1.4.1 练习题 33

1.4.2 练习题参考答案 35

1.5 第5章——回溯法 41

1.5.1 练习题 41

1.5.2 练习题参考答案 42

1.6 第6章——分枝限界法 50

1.6.1 练习题 50

1.6.2 练习题参考答案 51

1.7 第7章——贪心法 56

1.7.1 练习题 56

1.7.2 练习题参考答案 58

1.8 第8章——动态规划 64

1.8.1 练习题 64

1.8.2 练习题参考答案 66

1.9 第9章——图算法设计 71

1.9.1 练习题 71

1.9.2 练习题参考答案 71

1.10 第10章——计算几何 78

1.10.1 练习题 78

1.10.2 练习题参考答案 78

1.11 第11章——计算复杂性理论简介 81

1.11.1 练习题 81

1.11.2 练习题参考答案 81

1.12 第12章——概率算法和近似算法 82

1.12.1 练习题 82

1.12.2 练习题参考答案 83

第2章 上机实验题及参考答案 85

2.1 第1章——概论 86

2.1.1 实验1统计求最大、最小元素的平均比较次数 86

2.1.2 实验2求无序序列中第k小的元素 87

2.1.3 实验3出队第k个元素 88

2.1.4 实验4设计一种好的数据结构Ⅰ 89

2.1.5 实验5设计一种好的数据结构Ⅱ 91

2.2 第2章——递归算法设计技术 92

2.2.1 实验1逆置单链表 92

2.2.2 实验2判断两棵二叉树是否同构 93

2.2.3 实验3求二叉树中最大和的路径 95

2.2.4 实验4输出表达式树等价的中缀表达式 96

2.2.5 实验5求两个正整数x、y的最大公约数 98

2.3 第3章——分治法 99

2.3.1 实验1求解查找假币问题 99

2.3.2 实验2求解众数问题 102

2.3.3 实验3求解逆序数问题 104

2.3.4 实验4求解半数集问题 105

2.3.5 实验5求解一个整数数组划分为两个子数组问题 106

2.4 第4章——蛮力法 108

2.4.1 实验1求解「？n」问题 108

2.4.2 实验2求解钱币兑换问题 109

2.4.3 实验3求解环绕的区域问题 110

2.4.4 实验4求解钓鱼问题 116

2.5 第5章——回溯法 118

2.5.1 实验1求解查找假币问题 118

2.5.2 实验2求解填字游戏问题 120

2.5.3 实验3求解组合问题 122

2.5.4 实验4求解满足方程解问题 123

2.6 第6章——分枝限界法 124

2.6.1 实验1求解4皇后问题 124

2.6.2 实验2求解布线问题 129

2.6.3 实验3求解迷宫问题 133

2.6.4 实验4求解解救Amaze问题 136

2.7 第7章——贪心法 139

2.7.1 实验1求解一个序列中出现次数最多的元素问题 139

2.7.2 实验2求解删数问题 140

2.7.3 实验3求解汽车加油问题 143

2.7.4 实验4求解磁盘驱动调度问题 144

2.7.5 实验5求解仓库设置位置问题 146

2.8 第8章——动态规划 148

2.8.1 实验1求解矩阵最小路径和问题 148

2.8.2 实验2求解添加最少括号数问题 150

2.8.3 实验3求解买股票问题 151

2.8.4 实验4求解双核处理问题 152

2.8.5 实验5求解拆分集合为相等的子集合问题 154

2.8.6 实验6求解将集合部分元素拆分为两个元素和相等且尽可能大的子集合问题 156

2.9 第9章——图算法设计 157

2.9.1 实验1求解自行车慢速比赛问题 157

2.9.2 实验2求解股票经纪人问题 158

2.9.3 实验3求解最大流最小费用问题 160

2.10 第10章——计算几何 162

2.10.1 实验1求解判断三角形类型问题 162

2.10.2 实验2求解凸多边形的直径问题 163

2.11 第 11章——概率算法和近似算法 165

第3章 在线编程题及参考答案 167

3.1 第1章——概论 168

3.1.1 在线编程题1求解两种排序方法问题 168

3.1.2 在线编程题2求解删除公共字符问题 169

3.1.3 在线编程题3求解移动字符串问题 170

3.1.4 在线编程题4求解大整数相乘问题 172

3.1.5 在线编程题5求解旋转词问题 173

3.1.6 在线编程题6求解门禁系统问题 174

3.1.7 在线编程题7求解数字排序问题 175

3.2 第2章——递归算法设计技术 176

3.2.1 在线编程题1求解n阶螺旋矩阵问题 176

3.2.2 在线编程题2求解幸运数问题 178

3.2.3 在线编程题3求解回文序列问题 179

3.2.4 在线编程题4求解投骰子游戏问题 181

3.3 第3章——分治法 182

3.3.1 在线编程题1求解满足条件的元素对个数问题 182

3.3.2 在线编程题2求解查找最后一个小于等于指定数的元素问题 183

3.3.3 在线编程题3求解递增序列中与x最接近的元素问题 185

3.3.4 在线编程题4求解按“最多排序”到“最少排序”的顺序排列问题 186

3.4 第4章——蛮力法 189

3.4.1 在线编程题1求解一元三次方程问题 189

3.4.2 在线编程题2求解完数问题 189

3.4.3 在线编程题3求解好多鱼问题 191

3.4.4 在线编程题4求解推箱子游戏问题 192

3.5 第5章——回溯法 196

3.5.1 在线编程题1求解会议安排问题 196

3.5.2 在线编程题2求解最小机器重量设计问题Ⅰ 197

3.5.3 在线编程题3求解最小机器重量设计问题Ⅱ 199

3.5.4 在线编程题4求解密码问题 201

3.5.5 在线编程题5求解马走棋问题 203

3.5.6 在线编程题6求解最大团问题 205

3.5.7 在线编程题7求解幸运的袋子问题 206

3.6 第6章——分枝限界法 208

3.6.1 在线编程题1求解饥饿的小易问题 208

3.6.2 在线编程题2求解最小机器重量设计问题Ⅰ 210

3.6.3 在线编程题3求解最小机器重量设计问题Ⅱ 213

3.6.4 在线编程题4求解最少翻译个数问题 215

3.7 第7章——贪心法 217

3.7.1 在线编程题1求解最大乘积问题 217

3.7.2 在线编程题2求解区间覆盖问题 218

3.7.3 在线编程题3求解Wooden Sticks（POJ 1230）问题 219

3.7.4 在线编程题4求解奖学金问题 221

3.7.5 在线编程题5求解赶作业问题 223

3.8 第8章——动态规划 225

3.8.1 在线编程题1求解公路上任意两点的最近距离问题 225

3.8.2 在线编程题2求解袋鼠过河问题 226

3.8.3 在线编程题3求解数字和为sum的方法数问题 228

3.8.4 在线编程题4求解人类基因功能问题 229

3.8.5 在线编程题5求解分饼干问题 232

3.8.6 在线编程题6求解堆砖块问题 234

3.8.7 在线编程题7求解小易喜欢的数列问题 236

3.8.8 在线编程题8求解石子合并问题 238

3.8.9 在线编程题9求解相邻比特数问题 240

3.8.10 在线编程题10求解周年庆祝会问题 241

3.9 第9章——图算法设计 243

3.9.1 在线编程题1求解全省畅通工程的最低成本问题 243

3.9.2 在线编程题2求解城市的最短距离问题 245

3.9.3 在线编程题3求解小人移动最小费用问题 247

3.10 第10章——计算几何 251

3.10.1 在线编程题1求解两个多边形公共部分的面积问题 251

3.10.2 在线编程题2求解最大三角形问题 254

3.11 第12章——概率算法和近似算法 256