ACM-ICPC基本算法 本书特色
《ACM-ICPC基本算法》简要介绍了ACM-ICPC（ACM国际大学生程序设计竞赛）、算法和算法设计的基础知识，重点讲解算法设计方法，给出了ACM-ICPC中常用的10种算法设计方法：求值法、递推法、递归法、枚举法、模拟法、分治法、贪心法、回溯法、构造法和动态规划法。本书针对每种程序设计方法，首先阐述该方法的基本思想，然后通过典型例题进行详细讲解，*后通过实战训练予以巩固和提高。本书注重ACM-ICPC的基本算法，思想高度概括、例题深入浅出、实战耐人寻味。本书可作为ACM国际大学生程序设计竞赛和中学青少年信息学奥林匹克竞赛的指导书，也可作为IT技术人员和计算机编程爱好者的参考书。
ACM-ICPC基本算法 内容简介
《ACM-ICPC基本算法》是ACM竞赛辅导书，兼具系统性和实用性特色。（1）系统性。本书在对算法概述的基础上，系统地讲解了ACM常用基本算法设计方法：数学法、递推法、递归法、枚举法、分治法、贪心法、回溯法、搜索法和动态规划法，并对算法设计的数学模型和技巧做了阐述。（2）实用性。选材新颖，方法实用，例题丰富，取舍得当。采用C语言作为算法描述手段，简明清晰，便于上机实践。书中提供了大部分算法的C程序和伪码算法，尽量使算法的描述从算法到程序设计逐步求精。
ACM-ICPC基本算法 目录
目 录
第1章 ACM与算法概述 1
1.1
ACM-ICPC简介 1
1.1.1
历史 1
1.1.2
比赛规则 2
1.1.3
区域和全球决赛 2
1.2 算法与问题求解 2
1.2.1
算法的定义 3
1.2.2
问题求解 3
1.3 算法的特性 5
1.3.1
算法的要素 5
1.3.2
算法的基本特性 6
1.4 算法的描述 6
1.4.1
基本控制结构的描述 7
1.4.2
C算法描述的约定 9
1.5 算法分析 11
1.5.1
算法的评价标准 11
1.5.2
算法的时间复杂性 12
1.5.3
算法的空间复杂性 13
1.6 算法的优化 14
1.6.1
全局优化 14
1.6.2
局部优化 15
1.6.3
算法优化中的注意事项 16
第2章 求值法 18
2.1 算法设计思想 18
2.2 典型例题 18
2.2.1
求*大数 18
2.2.2
中位数和平均数 19
2.2.3
判断闰年 20
2.2.4
素数 21
2.2.5
判断天数 23
2.2.6
大整数阶乘 24
2.3 实战训练 25
2.3.1
求年长者 25
2.3.2
一元二次方程求根 26
2.3.3
三角形的面积 26
2.3.4
*大公约数 26
2.3.5
求整数的位数 27
2.3.6
孪生素数 27
2.3.7
求圆的周长 27
2.3.8
阶乘求和 28
2.3.9
计算圆周率 28
2.3.10
求闰年 29
2.3.11
连续自然数的平方和 29
2.3.12
大整数求和问题 29
2.3.13
公牛和母牛 30
2.3.14
十六进制的运算 30
2.3.15
亲和数 31
2.4 小结 31
第3章 递推法 32
3.1 算法设计思想 32
3.2 典型例题 33
3.2.1
兔子繁殖问题 33
3.2.2
*大公约数问题 34
3.2.3
猴子吃桃问题 35
3.2.4
杨辉三角问题 36
3.2.5
穿越沙漠问题 37
3.2.6
方格涂色问题 39
3.3 实战训练 40
3.3.1
求年龄 40
3.3.2
斐波那契数列求和 40
3.3.3
绝不后退 41
3.3.4
取数 41
3.3.5
王小二的刀 41
3.3.6
蜜蜂回家 42
3.3.7
富二代的生活费 42
3.3.8
平面分割问题 43
3.3.9
特殊性质的数 43
3.3.10
求天数 44
3.3.11
上楼梯 44
3.3.12
开奖 44
3.3.13
月之数 45
3.3.14
洗牌 45
3.3.15
飞跃悬崖 46
3.4 小结 46
第4章 递归法 47
4.1 算法设计思想 47
4.2 典型例题 47
4.2.1
母牛繁殖问题 47
4.2.2
输出各位数字 48
4.2.3
*大值问题 49
4.2.4
计算x的n次幂 51
4.2.5
数组逆置 52
4.2.6
汉诺塔问题 53
4.3 实战训练 54
4.3.1
递归取数 54
4.3.2
递归拆数 55
4.3.3
求素数之积 55
4.3.4
反转字符串 56
4.3.5
公共子序列 56
4.3.6
卖鸭子 56
4.3.7
进制转换 57
4.3.8
角谷定理 57
4.3.9
杨辉三角 58
4.3.10
质因数分解 58
4.3.11
全排列 58
4.3.12
特殊性质的数 59
4.3.13
放盘子 59
4.3.14
无序划分 60
4.3.15
回文数 60
4.4 小结 60
第5章 枚举法 62
5.1 算法设计思想 62
5.2 典型例题 62
5.2.1
百鸡问题 62
5.2.2
水仙花数 63
5.2.3
完数 64
5.2.4
可逆素数 65
5.2.5
串匹配问题 67
5.2.6
*小公倍数问题 69
5.2.7
狱吏问题 71
5.3 实战训练 72
5.3.1
素数筛选问题 72
5.3.2
纸币换硬币 73
5.3.3
勾股数问题 73
5.3.4
生理周期问题 73
5.3.5
构造比例数 74
5.3.6
自守数 75
5.3.7
谁是窃贼 75
5.3.8
独特的数 76
5.3.9
握手问题 76
5.3.10
趣味数学 77
5.3.11
暴力枚举之绝对值 77
5.3.12
回文数 78
5.3.13
逆序对数 79
5.3.14
放牧 79
5.3.15
餐厅点餐 80
5.4 小结 81
第6章 模拟法 82
6.1 算法设计思想 82
6.2 典型例题 82
6.2.1
电梯问题 82
6.2.2
扑克洗牌问题 83
6.2.3
进站时间模拟 85
6.2.4
消息队列 86
6.2.5
清除杂草 89
6.2.6
机器人的指令 92
6.3 实战训练 93
6.3.1
报数问题 93
6.3.2
无限次幂 94
6.3.3
金币工资 95
6.3.4
进制转换 95
6.3.5
卡片魔术 96
6.3.6
木棍上的蚂蚁 96
6.3.7
串联数字 97
6.3.8
多连块覆盖问题 98
6.3.9
括号表达式 99
6.3.10
假币问题 100
6.3.11
会议安排 101
6.3.12
取火柴游戏 102
6.3.13
取石子游戏 103
6.3.14
伪造的美元 103
6.3.15
HTML浏览器 104
6.4 小结 105
第7章 分治法 106
7.1 算法设计思想 106
7.2 典型例题 106
7.2.1
折半查找 106
7.2.2
金块问题 108
7.2.3
寻找第二的问题 110
7.2.4
归并排序 112
7.2.5
大整数乘法 114
7.2.6
二叉树遍历 115
7.3 实战训练 118
7.3.1
数组二分求和 118
7.3.2
子序列*大值 118
7.3.3
棋盘覆盖 118
7.3.4
*接近点对问题 120
7.3.5
第k小元素问题 120
7.3.6
循环赛日程表问题 121
7.3.7
找假币问题 121
7.3.8
n阶分形 122
7.3.9
m叉树问题 122
7.3.10
电话查重 123
7.3.11
树的有效点对 124
7.3.12
回文串交换 125
7.3.13
史密斯数 125
7.3.14
矩阵乘积 126
7.3.15
士兵排队问题 126
7.4 小结 127
第8章 贪心法 128
8.1 算法设计思想 128
8.2 典型例题 129
8.2.1
找零钱问题 129
8.2.2
*优装载 130
8.2.3
哈夫曼编码 132
8.2.4
单源*短路径 136
8.2.5
埃及分数问题 139
8.2.6
多机调度问题 141
8.3 实战训练 144
8.3.1
小船过河问题 144
8.3.2
纪念品分组 144
8.3.3
数列极差问题 145
8.3.4
函数求底问题 145
8.3.5
开心的金明 146
8.3.6
小明坐车问题 147
8.3.7
田忌赛马 147
8.3.8
装箱问题 148
8.3.9
删数问题 148
8.3.10
移动纸牌问题 149
8.3.11
组合正整数 149
8.3.12
活动安排问题 150
8.3.13
多人接水问题1 150
8.3.14
多人接水问题2 151
8.3.15
搬桌子问题 151
8.4 小结 152
第9章 回溯法 153
9.1 算法设计思想 153
9.2 典型例题 153
9.2.1
八皇后问题 153
9.2.2
图着色问题 155
9.2.3
桥本分数式 158
9.2.4
高逐位整除数 160
9.2.5
直尺刻度分布问题 162
9.2.6
素数环问题 164
9.2.7
伯努利装错信封问题 167
9.3 实战训练 169
9.3.1
排列问题 169
9.3.2
低逐位整除数 169
9.3.3
子集问题 170
9.3.4
旅行售货员问题 170
9.3.5
两组均分问题 171
9.3.6
组合数问题 171
9.3.7
运动员*佳配对问题 172
9.3.8
任务*佳调度问题 172
9.3.9
迷宫问题 173
9.3.10
背包问题 174
9.3.11
翻币问题 174
9.3.12
*长滑雪问题 175
9.3.13
流水线作业调度问题 175
9.3.14
组合三角形问题 176
9.3.15
情侣排列问题 176
9.4 小结 177
第10章 构造法 178
10.1
算法设计思想 178
10.2
典型例题 179
10.2.1
计算π值 179
10.2.2
求n的阶乘 180
10.2.3
求第k大的数 181
10.2.4
比赛日程表 183
10.2.5
奇数阶魔方 185
10.2.6
二叉树操作 187
10.3
实战训练 189
10.3.1
自然数倒数求和 189
10.3.2
今夕是何日 189
10.3.3
计算e值 190
10.3.4
自数 190
10.3.5
火星人 191
10.3.6
整数平方后9位 192
10.3.7
构造等式 192
10.3.8
构造回文字符串 192
10.3.9
开灯问题 193
10.3.10
“1”的个数 193
10.3.11
小明的烦恼 194
10.3.12
乒乓球赛 194
10.3.13
自然数拆分问题 195
10.3.14
集卡片赢大奖 195
10.3.15
括号匹配问题 196
10.4
小结 196
第11章 动态规划法 198
11.1
算法设计思想 198
11.2
典型例题 199
11.2.1
数塔问题 199
11.2.2
矩阵连乘问题 201
11.2.3
*长公共子序列问题 205
11.2.4
*长上升子序列问题 207
11.2.5
陪审团问题 209
11.3
实战训练 212
11.3.1
*少硬币问题 212
11.3.2
编辑距离问题 213
11.3.3
石子合并问题 213
11.3.4
*小m段和问题 214
11.3.5
*大长方体问题 214
11.3.6
*大k乘积问题 215
11.3.7
*少费用购物问题 215
11.3.8
*优时间表问题 216
11.3.9
矩形嵌套问题 217
11.3.10
导弹拦截问题 218
11.3.11
C小加问题 218
11.3.12
完全背包问题 219
11.3.13
分邮票问题 220
11.3.14
排列问题 220
11.3.15
完全覆盖问题 221
11.4
小结 221
参考文献 223
