程序设计方法及算法导引

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

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

第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