查字典图书网
查字典图书网
内容简介：
第一部分 开始解决问题
第二部分 算法分析
第三部分 算法设计范式
第四部分 一些著名的算法
第五部分 基本数据结构
第六部分 树
第七部分 图
作者简介：
具宗万
毕业于韩国延世大学计算机科学系，曾在innotive公司和NHN公司任软件工程师，现在芝加哥高频交易（HFT）公司从事算法交易开发工作。2007年开始参与运营韩国程序设计竞赛参赛者网络社交平台algospot （http://algospot.com）。
获奖经历
•2002年、2003年 韩国大学生程序设计竞赛 金奖
•2003年、2004年 世界大学生程序设计竞赛 入围决赛
•2004年、2006年、2008年 Google Code Jam 入围决赛
•2007年 Top Coder Open 亚军，2006年 入围决赛
•2008年、2009年 Java算法竞赛 冠军
目录：
第一部分 开始解决问题
第1 章 解决问题与程序设计竞赛4
1.1 引言4
1.2 程序设计竞赛4
1.3 阅读本书的方法7
1.4 值得参加的程序设计竞赛8
1.5 对赛前准备工作的一些建议9
1.6 续读12
第2 章 解决问题概述13
2.1 引言13
2.2 解决问题的过程13
2.3 解决问题的策略17
2.4 续读26
第3 章 编码与调试27
3.1 引言：不要忽视编码的重要性27
3.2 编写优秀代码的原则27
3.3 常见失误32
3.4 调试与测试39
3.5 变量的取值范围42
3.6 理解实数型数据类型46
3.7 续读55
第二部分 算法分析
第4 章 分析算法的时间复杂度60
4.1 引言60
4.2 线性时间算法62
4.3 次线性时间算法65
4.4 指数时间算法67
4.5 时间复杂度70
4.6 推测执行时间76
4.7 计算复杂度类：P、NP、NP-完备81
4.8 续读84
第5 章 算法正确性证明85
5.1 引言85
5.2 数学归纳法和循环不变式86
5.3 归谬法90
5.4 其他技巧92
5.5 续读95
第三部分 算法设计范式
第6 章 暴力解决法99
6.1 引言99
6.2 递归调用和穷举搜索法100
6.3 练习题：郊游（习题 ID：PICNIC，难度：低）106
6.4 解题：郊游107
6.5 练习题：盖游戏板（习题 ID：BOARDCOVER，难度：低）109
6.6 解题：盖游戏板111
6.7 优化问题113
6.8 练习题：时钟同步（习题 ID：CLOCKSYNC，难度：中）116
6.9 解题：时钟同步117
6.10 常见穷举搜索类型119
第7 章 分治法120
7.1 引言120
7.2 练习题：四叉树问题（题目 ID：QUADTREE，难度：低） 130
7.3 解题：四叉树问题131
7.4 练习题：切割篱笆（习题 ID：FENCE，难度：中）134
7.5 解题：切割篱笆135
7.6 练习题：粉丝见面会（题目 ID：FANMEETING，难度：高）139
7.7 解题：粉丝见面会141
第8 章 动态规划法143
8.1 引言143
8.2 练习题：通配符（习题 ID：WILDCARD，难度：中） 151
8.3 解题：通配符152
8.4 典型优化问题156
8.5 练习题：合并LIS（题目 ID：JLIS，难度：低）163
8.6 解题：合并LIS164
8.7 练习题：背诵圆周率（题目 ID：PI，难度：低） 166
8.8 解题：背诵圆周率167
8.9 练习题：Quantization（题目 ID：QUANTIZE，难度：中） 169
8.10 解题：Quantization 170
8.11 所有可能的个数与概率174
8.12 练习题：非对称铺设（题目 ID：ASYMTILING，难度：低）180
8.13 解题：非对称铺设181
8.14 练习题：多联骨牌（题目 ID：POLY，难度：中）183
8.15 解题：多联骨牌185
8.16 练习题：逃狱的韩尼拔博士（题目 ID：NUMB3RS，难度：中）187
8.17 解题：逃狱的韩尼拔博士189
第9 章 动态规划技巧194
9.1 计算优化问题的实际答案194
9.2 练习题：打包行李（题目 ID：PACKING，难度：中）195
9.3 解题：打包行李 197
9.4 练习题：光学字符识别（题目 ID：OCR，难度：高） 199
9.5 解题：光学字符识别 201
9.6 计算第k个答案 204
9.7 练习题：第k个最大递增子序列（题目 ID：KLIS，难度：高）209
9.8 解题：第k个最长递增子序列 210
9.9 练习题：龙曲线（题目 ID：DRAGON，难度：中）214
9.10 解题：龙曲线 216
9.11 对非整数型输入的制表 219
9.12 练习题：韦布巴津（题目 ID：ZIMBABWE，难度：高） 224
9.13 解题：韦布巴津 225
9.14 练习题：恢复实验数据（题目 ID：RESTORE，难度：中）230
9.15 解题：恢复实验数据 231
9.16 组合游戏 234
9.17 练习题：数字游戏（题目 ID：NUMBERGAME，难度：低）239
9.18 解题：数字游戏 240
9.19 练习题：方块游戏（题目 ID：BLOCKGAME，难度：中） 242
9.20 解题：方块游戏 243
9.21 迭代动态规划法 245
9.22 练习题：回转寿司（题目 ID：SUSHI，难度：中）249
9.23 解题：回转寿司 250
9.24 练习题：Genius（题目 ID：GENIUS，难度：中）253
9.25 解题：Genius254
9.26 续读 256
第10 章 贪心法 257
10.1 引言 257
10.2 练习题：加热便当（题目 ID：LUNCHBOX，难度：低）264
10.3 解题：加热便当 265
10.4 练习题：合并字符串（题目 ID：STRJOIN，难度：中）268
10.5 解题：合并字符串269
10.6 练习题：米那斯雅诺（题目 ID：MINASTIRITH，难度：高）273
10.7 解题：米那斯雅诺275
第11 章 组合搜索281
11.1 引言281
11.2 组合搜索的方法283
11.3 练习题：盖游戏板2（题目 ID：BOARDCOVER2，难度：低）298
11.4 解题：盖游戏板2 299
11.5 练习题：患有严重过敏症的朋友们（题目 ID：ALLERGY，难度：中）303
11.6 解题：患有严重过敏症的朋友们........304
11.7 练习题：数谜（题目 ID：KAKURO2，难度：中）307
11.8 解题：数谜309
11.9 续读315
第12 章 将优化问题转换为决策问题求解316
12.1 引言316
12.2 练习题：南极基地（题目 ID：ARCTIC，难度：低） 320
12.3 解题：南极基地321
12.4 练习题：加拿大旅行（题目 ID：CANADATRIP，难度：中）323
12.5 解题：加拿大旅行324
12.6 练习题：退选课程（题目 ID：WITHDRAWAL，难度：高）326
12.7 解题：退选课程327
第四部分 一些著名的算法
第13 章 数值分析331
13.1 引言331
13.2 二分法331
13.3 练习题：提高获胜率（题目 ID：RATIO，难度：低） 338
13.4 解题：提高获胜率339
13.5 三叉搜索341
13.6 练习题：花粉化石（题目 ID：FOSSIL，难度：高） 346
13.7 解题：花粉化石347
13.8 其他主题351
第14 章 整数论352
14.1 引言352
14.2 素数352
14.3 练习题：密码486（题目 ID：PASS486，难度：中）357
14.4 解题：密码486 357
14.5 欧几里得算法360
14.6 练习题：魔法药水（题目 ID：POTION，难度：中）361
14.7 解题：魔法药水362
14.8 模运算364
14.9 续读366
第15 章 计算几何367
15.1 引言367
15.2 计算几何的工具367
15.3 相交、距离、面积373
15.4 练习题：弹球模拟（题目 ID：PINBALL，难度：高）377
15.5 解题：弹球模拟379
15.6 多边形383
15.7 练习题：金银岛（题目 ID：TREASURE，难度：高） 386
15.8 解题：金银岛387
15.9 练习题：是呆子？不是呆子？（题目ID：NERDS，难度：中） 390
15.10 解题：是呆子？不是呆子？392
15.11 计算几何算法设计范式396
15.12 常见失误与注意事项403
15.13 续读404
第五部分 基本数据结构
第16 章 位掩码410
16.1 引言410
16.2 利用位掩码实现集合413
16.3 位掩码应用示例417
16.4 练习题：毕业学期（题目 ID：GRADUATION，难度：中） 420
16.5 解题：毕业学期422
16.6 续读424
第17 章 部分和425
17.1 引言425
17.2 练习题：圣诞娃娃（题目 ID：CHRISTMAS，难度：中）429
17.3 解题：圣诞娃娃430
17.4 其他学习内容432
第18 章 线性数据结构433
18.1 引言433
18.2 动态数组433
18.3 链表437
18.4 动态数组和链表的比较440
18.5 练习题：约瑟夫斯（题目 ID：JOSEPHUS，难度：低） 440
18.6 解题：约瑟夫斯441
18.7 续读442
第19 章 队列、栈以及双端队列443
19.1 引言443
19.2 队列、栈以及双端队列的实现方法444
19.3 队列与栈的应用445
19.4 练习题：不匹配括号（题目 ID：BRACKETS2，难度：低）448
19.5 解题：不匹配括号449
19.6 练习题：分析外星信号（题目 ID：ITES，难度：中）450
19.7 解题：分析外星信号451
第20 章 字符串455
20.1 引言455
20.2 字符串检索 456
20.3 练习题：宰河的保险箱（题目 ID：JAEHASAFE，难度：中）466
20.4 解题：宰河的保险箱 467
20.5 后缀数组 468
20.6 练习题：口头禅（题目 ID：HABIT，难度：中） 476
20.7 解题：口头禅 477
20.8 续读 478
第六部分 树
第21 章 树的实现与遍历 481
21.1 引言 481
21.2 树的遍历 483
21.3 练习题：变更树的遍历顺序（题目 ID：TRAVERSAL，难度：低）484
21.4 解题：变更树的遍历顺序 486
21.5 练习题：要塞（题目 ID：FORTRESS，难度：中） 487
21.6 解题：要塞 488
第22 章 二叉搜索树 493
22.1 引言 493
22.2 二叉搜索树的定义和操作 493
22.3 时间复杂度分析与平衡二叉搜索树496
22.4 练习题：是呆子？不是呆子？2（题目ID：NERD2，难度：中）496
22.5 解题：是呆子？不是呆子？2498
22.6 直接实现平衡二叉搜索树：树堆501
22.7 练习题：反转插入排序（题目 ID：INSERTION，难度：中）508
22.8 解题：反转插入排序 509
第23 章 优先级队列和堆 511
23.1 引言 511
23.2 堆的定义与实现方法 512
23.3 练习题：变化的中间值（题目 ID：RUNNINGMEDIAN，难度：低）518
23.4 解题：变化的中间值 519
第24 章 区间树521
24.1 区间树：区间相关问题解答521
24.2 练习题：登山路（题目 ID：MORDDR，难度：中） 527
24.3 解题：登山路528
24.4 练习题：寻根问祖（题目 ID：FAMILYTREE，难度：高）529
24.5 解题：寻根问祖530
24.6 树状数组：快速而简单的区间和533
24.7 练习题：计算插入排序的时间（题目 ID：MEASURETIME，难度：中） 536
24.8 解题：计算插入排序的时间537
第25 章 互斥集合541
25.1 引言541
25.2 练习题：编辑器之争（题目 ID：EDITORWARS，难度：中）546
25.3 解题：编辑器之争548
第26 章 字典树553
26.1 引言553
26.2 练习题：再见，谢谢所有的鱼（题目 ID：SOLONG，难度：中）557
26.3 解题：再见，谢谢所有的鱼559
26.4 利用字典树检索多重字符串563
26.5 练习题：安全终结者（题目 ID：NH，难度：高）569
26.6 解题：安全终结者570
第七部分 图
第27 章 图的表示方式及定义576
27.1 引言576
27.2 图的应用示例579
27.3 隐式图结构580
27.4 图的几种表示法581
第28 章 图的深度优先搜索585
28.1 引言585
28.2 练习题：古语词典（习题 ID：DICTIONARY，难度：低）590
28.3 解题：古语词典591
28.4 欧拉回路594
28.5 练习题：有限单词接龙（题目 ID：WORDCHAIN，难度：低） 597
28.6 解题：有限单词接龙598
28.7 理论背景及应用602
28.8 练习题：安装监控摄像头（题目 ID：GALLERY，难度：中）613
28.9 解题：安装监控摄像头614
28.10 练习题：安排会议室（题目 ID：MEETINGROOM，难度：高）616
28.11 解题：安排会议室618
第29 章 图的宽度优先搜索625
29.1 引言625
29.2 练习题：排序游戏（题目 ID：SORTGAME，难度：中）629
29.3 解题：排序游戏630
29.4 练习题：儿童节（题目 ID：CHILDRENDAY，难度：高）633
29.5 解题：儿童节634
29.6 最短路径策略637
29.7 练习题：汉诺塔（题目 ID：HANOI4B，难度：中） 648
29.8 解题：汉诺塔650
第30 章 最短路径问题653
30.1 引言653
30.2 迪杰斯特拉最短路径算法654
30.3 练习题：信号路由（题目 ID：ROUTING，难度：低）661
30.4 解题：信号路由662
30.5 练习题：消防车（题目 ID：FIRETRUCKS，难度：中）663
30.6 解题：消防车664
30.7 练习题：铁人N项比赛（题目 ID：NTHLON，难度：高） 665
30.8 解题：铁人N项比赛667
30.9 贝尔曼－福特最短路径算法669
30.10 练习题：时间旅行（题目 ID：TIMETRIP，难度：中） 674
30.11 解题：时间旅行675
30.12 弗洛伊德多源最短路径算法677
30.13 练习题：检查酒驾（题目 ID：DRUNKEN，难度：中） 682
30.14 解题：检查酒驾684
30.15 练习题：竞选承诺（题目 ID：PROMISES，难度：中） 685
30.16 解题：竞选承诺687
第31 章 最小生成树689
31.1 引言689
31.2 克鲁斯克尔最小生成树算法690
31.3 普里姆最小生成树算法694
31.4 练习题：局域网（题目 ID：LAN，难度：低）697
31.5 解题：局域网698
31.6 练习题：选定旅行路线（题目 ID：TPATH，难度：高） 699
31.7 解题：选定旅行路线 700
第32 章 网络流 705
32.1 引言 705
32.2 福特－富尔克森算法 706
32.3 网络建模 713
32.4 练习题：操纵比赛（题目 ID：MATCHFIX，难度：中）715
32.5 解题：操纵比赛 717
32.6 练习题：国家项目（题目 ID：PROJECTS，难度：高）719
32.7 解题：国家项目 720
32.8 二分图匹配 723
32.9 练习题：象（题目 ID：BISHOPS，难度：中）729
32.10 解题：象 730
32.11 练习题：设置陷阱（题目 ID：TRAPCARD，难度：高）732
32.12 解题：设置陷阱 734
32.13 其他学习内容 737
文章试读：参加程序设计竞赛是培养解决问题能力的最佳途径。在目前各式各样的程序设计竞赛当中，本书选取设计要求较少、有运算时间限制、比拼快速设计能力的竞赛。此处的设计要求不同于实际开发中的要求，而是以“读入某个值，然后计算出某个值”的形式给出。 下面针对未接触过程序设计竞赛的读者举个简单的示例。 题目：摇滚音乐节（难度：低，题目ID：FESTIVAL） 要租用一个大的演出场地举办摇滚音乐节。这次音乐节将...
(查看全部试读)