趣题学算法

趣题学算法
出版时间：2017
内容简介
　　书中内容基于C++全书共分10章。第0章讲解了算法的概念及体例说明。第1～7章分别就计数问题、信息查找问题、组合优化问题、图中搜索问题和数论问题展开，讨论了算法的构思和设计，详尽介绍了解决这些问题的渐增策略、分治策略、回溯策略、动态规划和贪婪策略、广度优先搜索策略、深度优先搜索策略等。第8章提供了10个让读者自解的计算问题，让读者有机会小试牛刀。第9章用书中给出的各问题的C++解决方案作为例子，讨论了C++语言的强大编程功能。书中一共收录了92个饶有兴趣的计算问题，每个问题（包括第8章留给读者自解的题目）都给出了完整的C++解决方案。 《趣题学算法》适于作为程序员的参考书，高校各专业学生学习“数据结构”“算法设计分析”“程序设计”等课程的扩展读物，也可以作为上述课程的实验或课程设计的材料，还可以作为准备参加国内或国际程序设计赛事的读者的赛前训练材料。
目录
第0章 从这里开始1
0.1　App程序与算法　2
0.2　计算问题　2
问题0-1　计算逆序数　3
0.3　算法的伪代码描述　4
0.4　算法的正确性　6
0.5　算法分析　7
0.6　算法运行时间的渐近表示　9
问题0-2　移动电话　10
0.7　算法的程序实现　13
0.8　从这里开始　15
第1章　计数问题　16
1.1　累积计数法　17
问题1-1　骑士的金币　17
问题1-2　扑克牌魔术　19
问题1-3　能量转换　22
问题1-4　美丽的花园　24
1.2　简单的数学计算　26
问题1-5　小小度刷礼品　26
问题1-6　找到牛妞　29
问题1-7　糟糕的公交调度　31
1.3　加法原理和乘法原理　34
问题1-8　冒泡排序　35
1.4　图的性质　38
问题1-9　聚会游戏　39
1.5　置换与轮换　41
问题1-10　牛妞排队　42
第2章　数据集合与信息查找　45
2.1　集合及其字典操作　46
问题2-1　开源项目　46
问题2-2　王子的难题　53
问题2-3　度度熊就是要第一个出场　56
问题2-4　寻找克隆人　62
问题2-5　疯狂搜索　64
2.2　文本串的查找　66
问题2-6　Pandora星球上的计算机病毒　69
2.3　全序集序列的排序　71
问题2-7　DNA排序　73
问题2-8　度度熊的礼物　76
问题2-9　通信系统　78
2.4　集合的并、交、差运算　80
问题2-10　计算机调度　81
第3章　现实模拟　85
3.1　简单模拟　86
问题3-1　对称排序　86
问题3-2　边界　89
3.2　栈及其应用　92
问题3-3　Web导航　93
问题3-4　周期序列　95
3.3　队列及其应用　99
问题3-5　稳定婚姻问题　99
问题3-6　最好的农场　102
3.4　基于二叉堆的优先队列及其应用　105
问题3-7　David购物　107
问题3-8　内存分配　110
3.5　二叉树及其应用　115
问题3-9　后缀表达式　116
问题3-10　符号导数　119
第4章　组合优化问题　125
4.1　组合问题及其回溯算法　126
3-色问题　126
N-后问题　127
0-1　背包问题　128
4.2　回溯算法框架　129
问题4-1　探险图　129
问题4-2　Jill的骑行路径　134
4.3　排列树问题　138
问题4-3　八元拼图　138
问题4-4　一步致胜　142
问题4-5　订单　145
4.4　子集树问题　147
问题4-6　命题逻辑　147
问题4-7　整除性　151
4.5　用回溯算法解组合优化问题　154
问题4-8　盗贼　154
问题4-9　牛妞玩牌　156
问题4-10　三角形游戏　159
问题4-11　轮子上的度度熊　162
4.6　加速计算组合优化问题　167
问题4-12　三角形N-后问题　167
第5章　动态规划与贪婪策略　172
5.1　动态规划　173
问题5-1　数字三角形　173
问题5-2　形式语言　176
5.2　0-1背包问题的动态规划算法　179
问题5-3　温馨旅程　180
5.3　最长公共子序列问题的动态规划算法　182
问题5-4　射雕英雄　184
问题5-5　人类基因功能　186
问题5-6　清洁机器人　189
5.4　贪婪策略　193
问题5-7　牛妞的最佳排列　193
问题5-8　渡河　197
5.5　无向带权图的最小生成树　199
问题5-9　网络设计　202
问题5-10　网页聚类　204
5.6　有向带权图单源最短路径　206
问题5-11　牛妞聚会　208
问题5-12　最短路　210
第6章　图的搜索算法　218
6.1　广度优先搜索　219
6.2　无向图的连通分支　221
问题6-1　女孩与男孩　221
问题6-2　卫星照片　224
6.3　图中顶点间最短路径　227
问题6-3　骑士移动　228
问题6-4　蜜蜂种群　230
6.4　深度优先搜索　233
6.5　有向无圈图的拓扑排序　235
问题6-5　考虑所有的光盘　236
问题6-6　循序　239
6.6　无向图的关节点和桥　242
问题6-7　网络保护　245
问题6-8　夫妻大盗　248
6.7　流网络的最大流问题　250
问题6-9　网络带宽　252
问题6-10　电网　255
问题6-11　选课　258
6.8　欧拉路径问题　261
问题6-12　观光旅游　262
问题6-13　Johnny的新车　267
问题6-14　放牛娃　269
第7章　数论问题　272
7.1　整数的进位制　273
问题7-1　牛牛计数　273
问题7-2　数制转换　275
7.2　10进制非负大整数的表示与算术运算　277
问题7-3　除法　281
7.3　整数的模运算　282
问题7-4　Maya历法　283
问题7-5　Euclid游戏　285
7.4　最大公约数　287
问题7-6　纽约大劫案　289
问题7-7　青蛙的约会　292
7.5　素数　295
问题7-8　素数分割　296
问题7-9　哥德巴赫猜想　298
问题7-10　困惑的密码员　299
7.6　算术基本定理　301
问题7-11　密码学中的幂　302
问题7-12　RSA因数分解　304
第8章　动手做　307
问题8-1　测谎　308
问题8-2　伪图形识别　309
问题8-3　反转数相加　311
问题8-4　直角多边形　312
问题8-5　二叉搜索堆　313
问题8-6　物以类聚　314
问题8-7　旅程　315
问题8-8　午餐　316
问题8-9　网络攻击　317
问题8-10　素数个数　318
第9章　C++程序设计　320
9.1　C++的程序结构　321
9.1.1　源文件的组成　322
9.1.2　语句与关键字　323
9.1.3　数据与表达式　325
9.1.4　指针类型和引用类型　328
9.2　C++的面向对象程序设计技术　331
9.2.1　类的封装　331
9.2.2　类的继承　338
9.2.3　多态　349
9.3　C++的模板技术　358
9.3.1　函数模板　358
9.3.2　类模板　360
9.4　C++的标准模板库——STL　366
9.4.1　容器类模板　367
9.4.2　算法模板和仿函数　383
9.4.3　类模板组合　386
9.5　数据的输入输出　391
9.5.1　文件输入输出流　391
9.5.2　串输入输出流　392
9.5.3　流运算符的重载　396