算法——数学应用与竞赛案例解析

第1章程序设计基础1
1.1程序设计语言入门1
1.1.1基本数据类型2
1.1.2顺序结构程序设计2
1.1.3条件结构程序设计3
1.1.4循环结构7
1.1.5数组12
1.1.6函数18
1.1.7指针20
1.1.8结构体22
1.2数据结构入门（基础）27
1.2.1栈28
1.2.2队列29
1.2.3链队30
第2章算法基础33
2.1递归算法33
2.1.1递归算法概述33
2.1.2汉诺塔问题33
2.1.3n皇后问题35
2.2分治算法37
2.2.1分治算法概述37
2.2.2计数问题38
2.2.3归并排序40
2.3枚举41
2.3.1木棒三角形42
2.3.2四大湖问题43
2.4贪心44
2.4.1砝码称重44
2.4.2石头剪刀布45
2.4.3马驰爱钓鱼48
2.5模拟50
2.5.1猜数50
2.5.2敌兵布阵52
第3章排序55
3.1冒泡排序57
3.1.1冒泡排序的基本原理57
3.1.2冒泡排序的算法步骤57
3.1.3冒泡排序的基本算法实现57
3.1.4冒泡排序的优化58
3.2快速排序59
3.2.1快速排序的基本原理59
3.2.2快速排序算法的步骤59
3.2.3快速排序的基本算法实现59
3.3其他排序60
3.4实例演示60
3.4.1出现次数超过一半的数60
3.4.2奖学金发放62
3.4.3魔法照片63
3.4.4输出前k大的数65
3.4.5不重复地输出数66
3.4.6单词排序67
3.4.7快速排序68
3.4.8第k个数70
第4章查找72
4.1查找的概念72
4.2顺序查找算法72
4.2.1顺序查找算法的概念72
4.2.2顺序查找算法的步骤72
4.2.3顺序查找算法的实现73
4.3折半查找算法73
4.3.1折半查找算法的基本思想73
4.3.2折半查找算法的步骤73
4.3.3折半查找算法的实现73
4.4实例演示74
4.4.1丢瓶盖74
4.4.2查找*接近的元素75
4.4.3油田合并77
第5章搜索79
5.1基本搜索算法79
5.1.1递归与迭代79
5.1.2深度优先搜索与广度优先搜索81
5.1.3回溯84
5.2搜索算法的一些优化85
5.2.1剪枝函数85
5.2.2双向广度搜索85
5.3实例演示85
5.3.1宝石游戏85
5.3.2骑士移动89
5.3.3Tetravex游戏93
5.3.4集合分解96
第6章字符串匹配99
6.1BF算法99
6.2RK算法99
6.3KMP算法100
6.4BM算法102
6.5Sunday算法103
6.6实例演示104
6.6.1*低三元字符串104
6.6.2从左侧删除107
6.6.3字母删除109
6.6.4潜伏者111
6.6.5处女座与复读机113
6.6.6缩写117
第7章图论119
7.1*短路径介绍119
7.2*小生成树121
7.2.1Kruskal算法121
7.2.2Prim算法122
7.3树的直径与*近公共祖先123
7.3.1树的直径123
7.3.2*近公共祖先123
7.4基环树125
7.4.1定义125
7.4.2一般的题型125
7.4.3一般解题思路125
7.5Tarjan算法与无向图和有向图连通性125
7.5.1Tarjan算法与无向图连通性125
7.5.2Tarjan算法与有向图连通性126
7.6二分图127
7.6.1定义127
7.6.2辨别二分图127
7.6.3充要条件128
7.6.4二分图*大匹配129
7.6.5判别129
7.7实例演示130
7.7.1黑与白130
7.7.2迷宫132
7.7.3*短网络133
7.7.4畅通工程135
7.7.5城市公交137
7.7.6趣味象棋140
第8章动态规划143
8.1基本思想145
8.2基本概念145
8.3基本原理146
8.3.1*优化原理146
8.3.2无后效性146
8.4一般步骤146
8.5实例演示147
8.5.1数字三角形147
8.5.2括号匹配150
8.5.3背包问题151
8.5.4骨灰级玩家考证篇154
8.5.5猴子游戏157
第9章高级数据结构159
9.1三种常用高级数据结构159
9.1.1线段树159
9.1.2并查集162
9.1.3树状数组167
9.2红黑树172
9.2.1红黑树的调整策略173
9.2.2参考程序179
9.3实例演示183
9.3.1人工湖公路183
9.3.2宗教信仰问题186
9.3.3无线网络188
第10章数论192
10.1质数查找192
10.2快速乘方194
10.3*大公约数196
10.4*小公倍数196
10.5模幂运算197
10.6斐波那契数列198
10.6.1斐波那契数列(递归实现)199
10.6.2斐波那契数列2(递推实现)200
10.6.3爬楼梯201
10.6.4一只小蜜蜂202
10.6.5骨牌铺方格203
10.7欧拉函数205
10.7.1概念205
10.7.2性质205
10.7.3实现方法205
10.8实例演示207
10.8.1欧拉函数例题207
10.8.2阿里巴巴的宝藏208
第11章组合数学211
11.1基本计数定理211
11.1.1加法原理与乘法原理211
11.1.2抽屉原理（鸽巢原理）214
11.2容斥原理219
11.2.1原理概述219
11.2.2常见应用219
11.2.3矩形并的面积222
11.2.42月29日223
11.2.5跳蚤226
11.2.6帮助蝉228
11.2.7你能找到多少个整数231
11.3排列233
11.3.1可重复排列233
11.3.2不可重复排列233
11.3.3不全相异元素的选排列235
11.3.4不全相异元素的全排列235
11.3.5错位排列235
11.3.6圆排列235
11.3.7卡片排列236
11.3.8疯狂外星人238
11.3.9重排列得到2的幂239
11.3.10permutation（排列）241
11.4组合244
11.4.1不可重组合数244
11.4.2可重复组合数244
11.4.3不相邻组合数244
11.4.4组合数的常用公式245
11.4.5求组合数的方法245
11.4.6车248
11.4.7壁画250
11.4.8二项式252
11.4.9集合的划分254
11.5组合数取模255
11.5.1递推打表255
11.5.2卢卡斯定理255
11.5.3卢卡斯定理扩展256
11.5.4孤独的李雷259
11.5.5走格子的骑士261
11.5.6组合问题262
11.5.7问题制造者264
11.5.8抽奖游戏267
11.6卡特兰数列269
11.6.1卡特兰数的公式269
11.6.2卡特兰数的应用270
11.6.3卡特兰数的实现270
11.6.4小涛叔叔的礼物271
11.6.5号码连接游戏272
11.6.6李嵩的作业274
11.7斯特林数277
11.7.1**类斯特林数277
11.7.2第二类斯特林数278
11.7.3二进制斯特林数280
11.8母函数282
11.8.1方形硬币（母函数）282
11.8.2寻找拉希德284
11.8.3排列组合286
第12章计算几何基础289
12.1矢量289
12.1.1矢量的概念289
12.1.2矢量加减法289
12.1.3矢量叉积289
12.1.4矢量叉积的应用290
12.2包含关系291
12.2.1判断图形是否包含在矩形中291
12.2.2判断图形是否包含在多边形中291
12.2.3判断图形是否包含在圆中294
12.2.4飞行员294
12.3凸包299
12.3.1凸包的概念299
12.3.2凸包的求法299
12.3.3捕野猪301
第13章博弈论304
13.1博弈论的基本构成要素304
13.1.1零和博弈304
13.1.2严格优势策略305
13.1.3囚徒困境305
13.1.4智猪博弈305
13.1.5纳什均衡306
13.2*小*大问题306
13.3尼姆博弈307
13.4巴什博弈310
13.5斐波那契博弈311
参考文献313