第1章 算法概述 1
1.1算法与问题求解 1
1.1.1算法的定义 1
1.1.2问题求解 2
1.2算法的要素和特性 3
1.2.1算法的要素 3
1.2.2算法的基本特性 4
1.3算法的描述 5
1.3.1基本控制结构的描述 5
1.3.2 C算法描述约定 7
1.4算法分析 9
1.4.1算法的评价标准 9
1.4.2算法的时间复杂度 10
1.4.3算法的空间复杂度 11
1.5算法的优化 12
1.5.1全局优化 12
1.5.2局部优化 13
1.5.3算法优化中的注意事项 14
第2章 求值法 17
2.1算法设计思想 17
2.2典型例题 17
2.2.1求最大值 17
2.2.2求平均分 19
2.2.3判断闰年 21
2.2.4素数 23
2.2.5孪生数 25
2.2.6巧排螺旋阵 27
2.2.7百灯判熄 31
2.3小结 33
习题2 33
第3章 累加法 35
3.1算法设计思想 35
3.2典型例题 35
3.2.1自然数求和 35
3.2.2自然数倒数求和 37
3.2.3统计及格人数 38
3.2.4计算π值 41
3.2.5统计对称数 42
3.2.6数列求和 45
3.2.7判断天数 46
3.3小结 48
习题3 49
第4章 累乘法 51
4.1算法设计思想 51
4.2典型例题 51
4.2.1求n的阶乘 51
4.2.2计算偶数积 52
4.2.3求阶乘之和 54
4.2.4大整数阶乘 56
4.2.5国王奖赏问题 58
4.2.6计算e值 60
4.3小结 62
习题4 62
第5章 递推法 65
5.1算法设计思想 65
5.2典型例题 66
5.2.1兔子繁殖问题 66
5.2.2最大公约数问题 68
5.2.3猴子吃桃问题 70
5.2.4杨辉三角问题 71
5.2.5穿越沙漠问题 74
5.2.6分西瓜问题 75
5.3小结 77
习题5 77
第6章 递归法 81
6.1算法设计思想 81
6.2典型例题 81
6.2.1母牛繁殖问题 81
6.2.2输出各位数字 83
6.2.3最大值问题 85
6.2.4计算x的n次幂 87
6.2.5数组逆置 89
6.2.6汉诺塔问题 91
6.3小结 93
习题6 93
第7章 枚举法 97
7.1算法设计思想 97
7.2典型例题 97
7.2.1百鸡问题 97
7.2.2水仙花数 100
7.2.3完数 102
7.2.4可逆素数 104
7.2.5串匹配问题 107
7.2.6最小公倍数问题 111
7.2.7狱吏问题 113
7.3小结 116
习题7 116
第8章 分治法 119
8.1算法设计思想 119
8.2典型例题 119
8.2.1折半查找 119
8.2.2金块问题 121
8.2.3寻找第二的问题 124
8.2.4归并排序 127
8.2.5大整数乘法 131
8.2.6二叉树遍历 133
8.3小结 138
习题8 138
第9章 贪心法 141
9.1算法设计思想 141
9.2典型例题 142
9.2.1找零钱问题 142
9.2.2最优装载 145
9.2.3哈夫曼编码 149
9.2.4单源最短路径 155
9.2.5埃及分数问题 158
9.2.6多机调度问题 162
9.3小结 165
习题9 166
第10章 回溯法 169
10.1算法设计思想 169
10.2典型例题 170
10.2.1八皇后问题 170
10.2.2图着色问题 174
10.2.3桥本分数式 176
10.2.4高逐位整除数 180
10.2.5直尺刻度分布问题 183
10.2.6素数环问题 186
10.2.7伯努利装错信封问题 190
10.3小结 194
习题10 195
第11章 动态规划 197
11.1算法设计思想 197
11.2典型例题 198
11.2.1数塔问题 198
11.2.2矩阵连乘问题 202
11.2.3最长公共子序列问题 207
11.2.4最长上升子序列问题 211
11.2.5陪审团问题 215
11.3小结 218
习题11 218
第12章 综合应用 223
12.1 Fibonacci数列 223
12.2 π值求法 227
12.3循环赛日程表 230
12.4最大子段和问题 239
12.5背包问题 246
习题12 256