编辑推荐

《ACM-ICPC基本算法》是ACM竞赛辅导书，兼具系统性和实用性特色。

（1）系统性。《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》在对算法概述的基础上，系统地讲解了ACM常用基本算法设计方法：数学法、递推法、递归法、枚举法、分治法、贪心法、回溯法、搜索法和动态规划法，并对算法设计的数学模型和技巧做了阐述。

（2）实用性。选材新颖，方法实用，例题丰富，取舍得当。采用C语言作为算法描述手段，简明清晰，便于上机实践。书中提供了大部分算法的C程序和伪码算法，尽量使算法的描述从算法到程序设计逐步求精。

内容简介

《ACM-ICPC基本算法》简要介绍了ACM-ICPC（ACM国际大学生程序设计竞赛）、算法和算法设计的基础知识，重点讲解算法设计方法，给出了ACM-ICPC中常用的10种算法设计方法：求值法、递推法、递归法、枚举法、模拟法、分治法、贪心法、回溯法、构造法和动态规划法。《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》针对每种程序设计方法，首先阐述该方法的基本思想，然后通过典型例题进行详细讲解，最后通过实战训练予以巩固和提高。

　　《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》注重ACM-ICPC的基本算法，思想高度概括、例题深入浅出、实战耐人寻味。《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》可作为ACM国际大学生程序设计竞赛和中学青少年信息学奥林匹克竞赛的指导书，也可作为IT技术人员和计算机编程爱好者的参考书。

　　

目录

第1章ACM与算法概述1
1.1ACM-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.2C算法描述的约定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.15HTML浏览器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.8n阶分形122
7.3.9m叉树问题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多人接水问题1150
8.3.14多人接水问题2151
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.11C小加问题218
11.3.12完全背包问题219
11.3.13分邮票问题220
11.3.14排列问题220
11.3.15完全覆盖问题221
11.4小结221
参考文献223

前言/序言

　　前言
　　ACM-ICPC是国际计算机学会组织的国际大学生程序设计竞赛。这项赛事是大学生智力与计算机解题能力的竞赛，是大学生展示水平与才华的大舞台，是各高校计算机教育成果的直接体现，也是IT企业与世界顶尖计算机人才对话的最佳机会。因而，程序设计竞赛吸引了越来越多的高校参赛。
　　ACM-ICPC中的“基本算法”用于指导学生分析问题和设计算法解决问题。学习常用基本算法设计方法，有助于理解算法设计的基本思想和科学原理，掌握算法设计的基本知识和基本技能，掌握算法设计中的计算思维和解题策略。
　　在《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》各章的讨论中，首先介绍一种算法设计方法的基本思想，然后将计算机经典问题和算法设计方法很好地结合起来，运用该算法设计方法去解决这些问题，并给出C语言描述，最后通过实战训练予以巩固和提高，以达到融会贯通的效果。
　　《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》的资料来源于吉林师范大学ACM-ICPC训练讲义，所选典型例题和实战训练题目分别来自吉林师范大学ONLINEJUDGE（JLOJ），网址为http://acm.jlnu.edu.cn；北京大学ONLINEJUDGE（POJ），网址为http://poj.org；浙江大学ONLINEJUDGE（ZOJ），网址为http://acm.zju.edu.cn；杭州电子科技大学ONLINEJUDGE（HDOJ），网址为http://acm.hdu.edu.cn。
　　《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》共11章。第1章简要介绍了ACM-ICPC、算法、算法分析和优化的基础知识；第2～11章系统讲解了10种常用的算法设计方法，分别为求值法、递推法、递归法、枚举法、模拟法、分治法、贪心法、回溯法、构造法和动态规划法。
　　《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》由吉林师范大学滕国文教授和李昊讲师撰写，从2005年开始，两位老师先后担任吉林师范大学ACM-ICPC代表队的主教练，开设了ACM-ICPC选修课，并成立了ACM-ICPC集训队，进行了十多年的教学尝试和实践训练。集训队主力队员施海勇、郭志鑫、李俊岐、李长彬和李婉琪参加了《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》部分代码编写和程序调试工作，白文秀、曹宇、滕泰、于淼、温毓铭、王双印、李然、高巨、赵腾飞和米雪阳等参与了《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》文稿的校对工作，作者在此一并致以诚挚的谢意！《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》由滕国文教授统稿。
　　在《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）：ACM-ICPC基本算法》的编写过程中，作者参阅并借鉴了国内外诸多同行的文章和着作，这里不一一列举、标明，在此向他们致以谢意！
　　由于作者水平有限，加之学科理论与技术发展日新月异，对于书中疏漏与不妥之处，恳请广大读者批评指正。
　　作者
　　2018年1月于四平

其他推荐