新書推薦：
《
海盗之书
》
售價：HK$
81.6
《
亲美与反美：战后日本的政治无意识
》
售價：HK$
69.6
《
亲爱的安吉维拉：或一份包含15条建议的女性主义宣言
》
售價：HK$
58.8
《
理想国译丛064：狼性时代：第三帝国余波中的德国与德国人，1945—1955
》
售價：HK$
122.4
《
海外中国研究·明清中国的经济结构
》
售價：HK$
153.6
《
理想国译丛018：活着回来的男人：一个普通日本兵的二战及战后生命史（2024版）
》
售價：HK$
110.4
《
考古四记：田野中的历史人生
》
售價：HK$
105.6
《
大洗牌
》
售價：HK$
93.6
|
| 內容簡介： |
|
本书从ACM-ICPC程序设计竞赛等各种程序设计竞赛的试题进行了分析和整理，并精选出典型试题进行分类解析，既可用于高校算法、程序设计课程的实验和教学，也可以用于竞赛选手的系统训练。
|
| 目錄：
|
前 言
第1章 求解Ad Hoc类问题的编程实验1
1.1 机理分析法的实验范例1
1.2 统计分析法的实验范例5
1.3 相关题库9
第2章 模拟法的编程实验31
2.1 直叙式模拟的实验范例31
2.2 筛选法模拟的实验范例46
2.3 构造法模拟的实验范例56
2.4 相关题库60
第3章 数论的编程实验72
3.1 素数运算的实验范例72
3.1.1 使用筛法生成素数72
3.1.2 测试大素数79
3.2 求解不定方程和同余的实验范例82
3.2.1 计算最大公约数和不定方程82
3.2.2 计算同余方程和同余方程组89
3.2.3 计算多项式同余方程99
3.3 特殊的同余式的实验范例102
3.3.1 威尔逊定理和费马小定理102
3.3.2 伪素数105
3.3.3 欧拉定理112
3.4 积性函数的实验范例116
3.4.1 欧拉φ函数φn116
3.4.2 莫比乌斯函数μn121
3.4.3 完全数和梅森素数124
3.5 高斯素数的实验范例129
3.6 相关题库135
第4章 组合分析的编程实验152
4.1 生成排列的实验范例152
4.1.1 按字典序思想生成下一个排列152
4.1.2 按字典序思想生成所有排列154
4.2 排列组合计数的实验范例156
4.2.1 一般的排列组合计数公式156
4.2.2 两种特殊的排列组合计数公式167
4.2.3 多重集的排列数和组合数174
4.3 鸽笼原理与容斥原理的实验范例178
4.3.1 利用鸽笼原理求解存在性问题178
4.3.2 容斥原理应用实验180
4.3.3 Ramsey定理的应用188
4.4 Pólya计数公式的实验范例190
4.5 生成函数与递推关系的实验范例201
4.5.1 幂级数型生成函数201
4.5.2 指数型生成函数204
4.5.3 递推关系207
4.6 快速傅里叶变换的实验范例211
4.7 相关题库216
第5章 贪心法的编程实验229
5.1 体验贪心法内涵的实验范例229
5.1.1 贪心法的经典问题229
5.1.2 体验贪心法内涵236
5.2 利用数据有序化进行贪心选择的实验范例241
5.3 在综合性的P类问题中使用贪心法的实验范例249
5.4 相关题库255
第6章 动态规划方法的编程实验265
6.1 线性DP的实验范例266
6.1.1 初步体验线性DP问题266
6.1.2 子集和问题270
6.1.3 最长公共子序列问题271
6.1.4 最长递增子序列问题273
6.2 0-1背包问题280
6.2.1 基本的0-1背包问题280
6.2.2 完全背包281
6.2.3 多重背包285
6.2.4 混合背包287
6.2.5 二维背包292
6.2.6 分组背包294
6.2.7 有依赖的背包298
6.3 树形DP的实验范例300
6.4 状态压缩DP的实验范例305
6.5 单调优化1D1D DP的实验范例309
6.5.1 经典模型1：利用决策代价函数w的单调性优化310
6.5.2 经典模型2：利用决策区间下界的单调性优化313
6.5.3 经典模型3：利用最优决策点的凸性优化318
6.6 相关题库322
第7章 高级数据结构的编程实验353
7.1 后缀数组的实验范例353
7.1.1 使用倍增算法计算名次数组和后缀数组353
7.1.2 计算最长公共前缀356
7.1.3 后缀数组的应用357
7.2 线段树的实验范例370
7.2.1 线段树的基本概念和基本操作370
7.2.2 线段树单点更新的维护372
7.2.3 线段树子区间更新的维护375
7.3 处理特殊图的实验范例387
7.3.1 计算欧拉图387
7.3.2 计算哈密顿图393
7.3.3 计算最大独立集402
7.3.4 计算割点、桥和双连通分支406
7.4 相关题库414
第8章 计算几何的编程实验433
8.1 点线面运算的实验范例433
8.1.1 计算点积和叉积433
8.1.2 计算线段交440
8.1.3 利用欧拉公式计算多面体449
8.2 利用扫描线算法计算矩形的并的面积的实验范例453
8.2.1 沿垂直方向计算矩形的并面积453
8.2.2 沿水平方向计算矩形的并面积457
8.3 计算半平面交的实验范例460
8.3.1 计算半平面交的联机算法461
8.3.2 利用极角计算半平面交的算法466
8.4 计算凸包和旋转卡壳的实验范例474
8.4.1 计算凸包474
8.4.2 旋转卡壳实验479
8.5 相关题库482
|
| 內容試閱：
|
本书是“大学程序设计课程与竞赛训练教材”系列著作中的第2部。我们编著这一系列著作的指导思想如下。
（1）程序设计竞赛是“通过编程解决问题”的竞赛。国际大学生程序设计竞赛（Inter-national Collegiate Programming Contest，ICPC）和中学生国际信息学奥赛（International Olympiad in Informatics，IOI）在20世纪80年代中后期走向成熟，30多年来，累积了海量的试题。这些来自全球各地、凝聚了无数命题者的心血和智慧的试题，不仅可以用于程序设计竞赛选手的训练，而且可以用于教学，以系统、全面地提高学生编程解决问题的能力。
（2）我们认为，评价一个人的专业能力，要看这个人的两个方面：1）知识体系，即他能用哪些知识去解决问题，或者说，他所真正掌握并能应用的知识，而不仅仅是他学过的知识；2）思维方式，即他在面对问题（特别是不太标准化的问题）的时候，解决问题的策略是什么？对于程序设计竞赛选手所要求的知识体系，可以概括为1984年图灵奖得主Niklaus Wirth提出的著名公式“算法+数据结构=程序”，这也是计算机学科知识体系的核心部分，因此本系列的前两部著作分别是《数据结构编程实验》和《算法设计编程实验》。对于需要采用某些策略进行求解的程序设计试题，比如，不采用常用的数据结构或者需要优化解题的算法，我们进行分析整理，编写了本系列的第3部著作《程序设计解题策略》。
（3）从本质上说，程序设计是技术，所以，首先牢记学习编程要不断“Practice, Practice,
Practice”!本系列选用程序设计竞赛的大量试题，以案例教学的方式进行教学实验并安排学生进行解题训练。其次，“Practice in a systematic way”。本系列的编写基于传统的教学大纲，以系统、全面地提高学生编程解决问题的能力为目标，以程序设计竞赛的试题及详细的解析、带注释的程序作为实验，在每一章的结束部分给出相关题库及解题提示，并对大部分试题给出官方的测试数据。
2013年，我们在机械工业出版社出版了《算法设计编程实验：大学程序设计课程与竞赛训练教材》。2018年，我们在CRC Press出版了该书的英文版《Algorithm Design Practice： for Collegiate Programming Contest and Education》。此外，我们还在中国台湾地区出版了繁体中文版。
本书的第1版是在复旦大学程序设计集训队长期活动的基础上编写而成的，共分8章，主要内容如下：
第1章“求解Ad Hoc类问题的编程实验”：介绍了机理分析法和统计分析法，引导读者在没有经典和模式化算法可对应的情况下，学会自创简单的算法。
第2章“模拟法的编程实验”：引导读者按照题意设计数学模型的各种参数，观察变更这些参数所引起的过程状态的变化，在此基础上展开算法设计。
第3章“数论的编程实验”和第4章“组合分析的编程实验”：这两章凸显了数论和组合分析知识在算法中的应用。其中，第3章围绕初等数论中的素数运算、求解不定方程和同余方程、应用积性函数等问题展开实验。第4章介绍在编程求解组合类问题时如何计算具有某种特性的对象个数，如何将它们完全列举出来，如何使用抽屉原理解决存在性问题，如何使用容斥原理计算多个集合并的元素数，如何使用Pólya定理对一个问题的各种不同的组合状态计数。
第5章“贪心法的编程实验”和第6章“动态规划方法的编程实验”：在求解具备最优子结构特征的问题时，这两种方法是最常用、最经典的思想方法，但适用场合不同，既有相同点又有区别之处。
第7章“高级数据结构的编程实验”：选择在一般数据结构教材中没有出现但很有用的一些知识，例如后缀数组、线段树、欧拉图、哈密顿图、最大独立集、割点、桥和双连通分支等内容展开编程实验。
第8章“计算几何的编程实验”：计算几何学是算法体系中一个重要的组成部分，也是先前算法教材中最薄弱的环节。该章开展点线面运算、扫描线算法、计算半平面交、凸包计算和旋转卡壳算法等实验。
近来年，我们使用本书第1版的中、英文版在全球高校进行教学，根据读者和学生的反馈，我们对本书第1版的内容进行了修订，形成了第2版。我们除了修正第1版中的小错误，以及改进一些表述之外，还做了如下较大改进：
对于第3章“数论的编程实验”和第4章“组合分析的编程实验”的内容和结构，基于数论、组合数学的知识体系，进行全面的加强和改进。其中，第3章从素数运算、求解不定方程和同余方程、特殊的同余式、积性函数的应用、高斯素数5个方面展开实验；而第4章从排列的生成、排列和组合的计数、容斥原理与鸽笼原理、Pólya计数公式、生成函数与递推关系、快速傅里叶变换（FFT）6个方面展开实验。对于数论、组合分析所涉及的知识点，都采用程序设计竞赛的试题作为实验范例，也就是说，基于数论、组合分析的知识体系，实验范例“鱼鳞状”分布在各个知识点中。同时，将数学证明能力和编程解决问题能力的训练相结合，这也是数学类试题的特征。
对于第5章“贪心法的编程实验”和第6章“动态规划方法的编程实验”，则增加了经典问题的实验。在第5章中，增加了背包问题、任务调度、区间调度等经典贪心问题的实验；在第6章中，则以“背包九讲”为基础，增加0-1背包问题的实验。这样改进的目的，是使读者能够更好地体验贪心和动态规划的方法。
本书可以用于大学的算法及相关数学课程的教学和实验，也可以用于程序设计竞赛选手的系统训练。对于本书，我们的使用建议是：书中每章的实验范例可以用于算法和数学课程的教学、实验和上机作业，以及程序设计竞赛选手掌握相关知识点的入门训练；而每章最后给出的相关题库中的试题则可以作为程序设计竞赛选手的专项训练试题，以及学生进一步提高编程能力的练习题。
我们对浩如烟海的ACM-ICPC预赛和总决赛、各种大学生程序设计竞赛、在线程序设计竞赛及中学生信息学奥林匹克竞赛的试题进行了分析和整理，从中精选出314道试题作为本书的试题。其中157道试题作为实验范例试题，每道试题不仅有详尽的解析，还给出标有详细注释的参考程序；另外的157道试题为题库试题，所有试题都有清晰的提示。
本书提供了所有试题的英文原版以及大部分试题的官方测试数据和解答程序，有需要者可登录华章网站（http：www.hzbook.com）下载。
感谢Stony Brook University的Steven Skiena教授和Rezaul Chowdhury教授，Texas State University的C. Jinshong Hwang教授、Ziliang Zong教授和Hongchi Shi教授，German University of Technology in Oman的Rudolf Fleischer教授，North South University的Abul L. Haque教授和Shazzad Hosain教授，International Islamic University Malaysia的Normaziah Abdul Aziz教授，以及香港理工大学的曹建农教授，他们为本书英文版书稿的试用和改进提供了以英语为母语或官方语言的平台。感谢Georgia Institute of Technology的Jiaqi Chen同学审阅英文版书稿的部分章节。
感谢巴黎第十一大学博士生张一博同学、香港中文大学博士生王禹同学和复旦大学已故教授朱洪先生，他们对于第2版的编写提出了建设性的意见。
感谢组织程序设计训练营集训并邀请我使用本书书稿讲学的香港理工大学曹建农教授，台湾“东华大学”彭胜龙教授，西北工业大学姜学峰教授和刘君瑞教授，宁夏理工学院副校长俞经善教授，中国矿业大学毕方明教授，以及中国矿业大学徐海学院刘昆教授等。
感谢指出书稿中错误的西安电子科技大学朱微、张恩溶和中国矿业大学徐海学院贺小梅等同学。
特别感谢和我一起创建ACM-ICPC亚洲训练联盟的国内同仁，他们不仅为本书书稿，也为我的系列著作及其课程建设提供了一个实践的平台。这些年，我们并肩作战，风雨同舟，如莎士比亚《亨利五世》的台词：“今日谁与我共同浴血，他就是我的兄弟！”
由于时间和水平所限，书中肯定夹杂了一些缺点和错误，表述不当和笔误也在所难免，热忱欢迎学术界同仁和读者赐正。如果你在阅读中发现了问题，请通过电子邮件告诉我们，以便我们在课程建设和中、英文版再版时改进。我们的联系方式如下：
通信地址：上海市邯郸路220号复旦大学计算机科学技术学院 吴永辉（邮编：200433）
电子邮件：yhwu@fudan.edu.cn
吴永辉 王建德
2019年10月30日于上海
注：本书试题的在线测试地址如下：
在线评测系统简称网址
北京大学在线评测系统POJhttp：poj.org
浙江大学在线评测系统ZOJhttp：acm.zju.edu.cnonlinejudge
http：zoj.pintia.cnhome
UVA在线评测系统UVAhttp：uva.onlinejudge.org
http：livearchive.onlinejudge.org
Ural在线评测系统Uralhttp：acm.timus.ru
HDOJ在线评测系统HDOJhttp：acm.hdu.edu.cn
|
|
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
