正版新书]程序设计方法及算法导引王桂平,刘君,李韧978730131841

第1章程序设计竞赛与在线程序实践1

1.1程序设计竞赛1

1.1.1大学生程序设计竞赛1

1.1.2蓝桥杯全国软件和信息技术专业人才大赛4

1.1.3中国高校计算机大赛团体程序设计天梯赛7

1.2在线程序实践7

1.3程序设计竞赛题目的特点9

1.3.1程序设计题目的组成9

1.3.2从单个测试数据的处理过渡到多个测试数据的处理9

1.3.3程序设计竞赛题目的输入/输出11

1.3.4程序设计竞赛题目的类型12

1.4程序设计竞赛题目解析13

练习题19

1.5实践进阶：基本的输入/输出的处理20

1.5.1输入的处理21

1.5.2输出的处理22

第2章枚举24

2.1枚举算法及例题解析24

2.1.1枚举算法及实现要点24

2.1.2例题解析25

练习题31

2.2哥德巴赫猜想34

练习题37

2.3尺取法及应用38

2.3.1尺取法的原理及注意事项38

2.3.2例题解析39

练习题43

2.4实践进阶：算法及算法复杂度44

2.4.1算法的概念44

2.4.2算法的效率及算法复杂度45

2.4.3算法时间复杂度的渐进分析和表示47

2.4.4好、坏和平均情况48

2.4.5基本的算法复杂度模型49

第3章模拟51

3.1模拟方法及例题解析51

3.1.1模拟方法及实现要点51

3.1.2例题解析52

练习题56

3.2模拟约瑟夫环58

练习题62

3.3游戏的模拟63

练习题70

3.4实践进阶：程序测试73

3.4.1解答程序设计竞赛题目的一般流程73

3.4.2程序测试方法74

第4章字符及字符串处理81

4.1字符转换与编码81

4.1.1字符转换81

4.1.2字符编码84

练习题87

4.2回文的判断与处理90

练习题94

4.3子串处理95

练习题98

4.4模式匹配问题及KMP算法99

4.4.1字符串的模式匹配问题99

4.4.2朴素的模式匹配算法99

4.4.3KMP算法101

4.4.4例题解析109

练习题114

4.5其他竞赛题目解析114

练习题118

4.6实践进阶：特殊的输入/输出的处理119

4.6.1特殊输入的处理120

4.6.2特殊输出的处理122

第5章时间和日期的处理123

5.1相关问题123

5.2例题解析127

5.2.1星期数计算127

5.2.2天数计算131

5.2.3日期合法性判断133

5.2.4日历转换138

5.2.5时间表示及转换140

练习题143

5.3实践进阶：程序调试145

5.3.1调试目的145

5.3.2调试步骤和方法145

5.3.3调试技巧146

第6章高精度计算147

6.1基础知识147

6.1.1高精度数147

6.1.2进制转换147

6.1.3用字符型数组或整型数组实现算术运算150

练习题152

6.2高精度计算原理及实现要点154

6.2.1高精度计算原理154

6.2.2高精度计算的基本思路155

6.2.3高精度计算要点156

练习题156

6.3高精度数的基本运算157

6.3.1高精度数的加法157

6.3.2高精度数的乘法159

6.3.3高精度数的除法161

练习题164

6.4其他高精度题目解析166

6.4.1数列问题166

6.4.2其他题目167

练习题169

6.5实践进阶：代码优化169

第7章递归、分治、动态规划和贪心171

7.1将较大规模问题降为较小规模问题171

7.2递归算法及例题解析175

7.2.1递归算法思想及存在的问题175

7.2.2例题解析176

练习题182

7.3分治算法及例题解析184

7.3.1分治算法的思想184

7.3.2例题解析188

练习题191

7.4动态规划算法及例题解析193

7.4.1动态规划算法的思想193

7.4.2例题解析199

练习题203

7.5贪心算法及例题解析205

7.5.1贪心算法的思想205

7.5.2例题解析211

练习题213

7.6实践进阶：函数及递归函数设计214

第8章搜索217

8.1深度优先搜索217

8.1.1深度优先搜索的思想217

8.1.2例题解析218

练习题227

8.2用深度优先搜索求解排列和组合问题230

8.2.1排列问题230

8.2.2组合问题235

练习题242

8.3广度优先搜索244

8.3.1广度优先搜索的思想244

8.3.2例题解析245

练习题252

8.4实践进阶：搜索技巧256

8.4.1深度优先搜索技巧256

8.4.2广度优先搜索技巧257

第9章排序和检索260

9.1排序及排序函数的使用260

9.1.1排序及排序算法260

9.1.2排序的应用261

9.1.3排序函数qsort()的用法262

9.1.4排序函数sort()的用法264

9.1.5例题解析265

练习题268

9.2排序题目解析270

9.2.1数值型数据的排序270

9.2.2字符型数据的排序273

9.2.3混合数据的排序275

练习题277

9.3二分法思想及二分检索280

9.3.1二分法的思想280

9.3.2二分检索法及应用280

9.3.3例题解析282

练习题286

9.4实践进阶：标准模板库及常用数据结构的使用287

9.4.1数据结构的基本概念287

9.4.2标准模板库288

9.4.3向量288

9.4.4栈288

9.4.5队列293

9.4.6优先级队列296

9.4.7常用算法298

练习题298

第10章数论基础300

10.1符号说明300

10.2整除理论301

10.2.1自然数与整数301

10.2.2整除301

10.2.3带余数除法与辗转相除法304

10.2.4公约数理论306

10.2.5算术基本定理307

10.2.6符号[x]与n!的分解式308

10.2.7π(x)与欧拉函数309

练习题310

10.3同余理论312

10.3.1同余312

10.3.2同余类与剩余类314

10.3.3同余方程315

练习题317

10.4素数相关问题319

10.4.1相关问题319

10.4.2例题解析320

10.5实践进阶：程序设计竞赛技巧321

附录A程序设计竞赛的100个技巧322

附录B本书例题和练习题汇总353

参考文献360

王桂平，博士，副教授，重庆交通大学信息科学与工程学院，研究方向为程序设计(C、C 、Java)、算法分析与设计、图论，主编教材4部，以*作者发表SCI期刊论文8篇，EI期刊论文12篇,有ACM/ICPC竞赛12年的教练经验。
刘君，女，工学博士，现任重庆交通大学信息学院副教授，主要研究方向为大气颗粒物飘散模型，发表SCI/EI论文4篇，获授权发明专利5项。
李韧，男，工学博士，现任重庆交通大学信息学院副教授，主要研究方向为交通基础设施智能化管养，发表SCI/EI论文20余篇，获省部级科技进步二等奖1项。

本书系统地讲解了程序设计的基本思想和算法，并通过一些经典的程序设计竞赛题目阐述算法思想和实现方法。本书首先介绍了几类程序设计竞赛的起源、历史、竞赛规则、评判原理等，以及一种新的程序设计实践形式——在线程序实践；然后讲解了程序设计竞赛涉及的一些基础算法和应用问题，包括枚举、模拟、字符及字符串处理，时间和日期处理，高精度计算，递归、分治、动态规划和贪心，搜索，排序和检索，数论基础，在每章的最后一节引入了程序设计竞赛所需掌握的实践知识和技能；最后的附录总结了程序设计竞赛的100个技巧，并汇总了本书例题和练习题。本书可作为高校程序设计基础课程的教材或配套教材，也可作为程序设计竞赛的入门教材。

&nbsp&nbsp本教材以程序设计方法和算法的培养为主线，通过许多经典的程序设计竞赛题目为例阐述常用的程序设计方法和算法，如枚举、尺取法、模拟、字符串处理、时间和日期处理、高精度运算、递归、分治、动态规划、贪心、深度优先搜索、广度优先搜索、排序与检索、数论算法等。本教材附录为读者介绍了在线程序实践和程序设计竞赛需要掌握的一些方法和技巧。《程序设计方法及算法导引》可用作高等院校理工科专业程序设计基础类课程的参考教材，也可以作为大学生程序设计大赛、蓝桥杯大赛、团体程序设计天梯赛等程序设计竞赛的培训和自学教材。