雅书

内容简介：

书中内容基于C 全书共分10章。第0章讲解了算法的概念及体例说明。第1～7章分别就计数问题、信息查找问题、组合优化问题、图中搜索问题和数论问题展开，讨论了算法的构思和设计，详尽介绍了解决这些问题的渐增策略、分治策略、回溯策略、动态规划和贪婪策略、广度优先搜索策略、深度优先搜索策略等。第8章提供了10个让读者自解的计算问题，让读者有机会小试牛刀。第9章用书中给出的各问题的C 解决方案作为例子，讨论了C 语言的强大编程功能。书中一共收录了92个饶有兴趣的计算问题，每个问题(包括第8章留给读者自解的题目)都给出了完整的C 解决方案。 《趣题学算法》适于作为程序员的参考书，高校各专业学生学习“数据结构”“算法设计分析”“程序设计”等课程的扩展读物，也可以作为上述课程的实验或课程设计的材料，还可以作为准备参加国内或国际程序设计赛事的读者的赛前训练材料。

作者简介：

作者长期在高校执教数学、算法与程序设计课程，并多次带队参加大学生程序设计大赛，教学经验丰富。编著多本算法书籍，深受读者喜爱。

目  录：

第0章 从这里开始 1

0.1App程序与算法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-6Pandora星球上的计算机病毒69

2.3全序集序列的排序71

问题2-7DNA排序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-3Web导航93

问题3-4周期序列95

3.3队列及其应用99

问题3-5稳定婚姻问题99

问题3-6最好的农场102

3.4基于二叉堆的优先队列及其应用105

问题3-7David购物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-2Jill的骑行路径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.20-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-13Johnny的新车267

问题6-14放牛娃269

第7章数论问题272

7.1整数的进位制273

问题7-1牛牛计数273

问题7-2数制转换275

7.210进制非负大整数的表示与算术运算277

问题7-3除法281

7.3整数的模运算282

问题7-4Maya历法283

问题7-5Euclid游戏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-12RSA因数分解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.1C 的程序结构321

9.1.1源文件的组成322

9.1.2语句与关键字323

9.1.3数据与表达式325

9.1.4指针类型和引用类型328

9.2C 的面向对象程序设计技术331

9.2.1类的封装331

9.2.2类的继承338

9.2.3多态349

9.3C 的模板技术358

9.3.1函数模板358

9.3.2类模板360

9.4C 的标准模板库——STL366

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