趣题学算法pdf

趣题学算法 内容简介

书中内容基于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

趣题学算法 精彩文摘

信息时代，人们时刻都在利用各种 App 解决生活、工作中的问题，或获取各种服务。早晨，手机里设定的闹钟铃声（或你喜欢的音乐）将你唤醒。来到餐厅，你用手中的 IC 卡到取餐处的刷卡机上支付美味早餐的费用。上班途中，打开手机上的音乐播放器，用美妙的乐声，打发掉挤在公交车上的乏味的时间。上班时，利用计算机中的各种办公软件处理繁忙的业务。闲暇时，你用平板电脑里的视频程序看一部热映的大片，或在淘宝网上选购你喜欢的宝贝。晚间，你用 QQ 或 Facetime与远方的朋友聊天、交流情感……凡此种种，不一而是。

五彩缤纷的 App 后面是什么？这些神奇的体验是怎么创造出来的？如果你对这样的问题感兴趣的话，我们就成为朋友了。从这里开始，我们将探索创造 App——计算机（及网络）应用程序的基本原理和基本技能。