计算机算法基础

第1章 算法与数学

1.1 复杂性的计量

1.2 生成函数

1.3 递归方程求解

1.4 和与积

1.5 组合公式

1.6 思考题

第2章 分治算法

2.1 大整数的乘法

2.2 棋盘覆盖问题

2.3 循环赛日程表

2.4 矩阵乘法

2.5 思考题

第3章 动态规划法

3.1 DNA比对

3.2 最长公共子序列

3.3 计算矩阵连乘积

3.4 思考题

第4章 贪心算法

4.1 0l背包

4.2 拓扑排序

4.3 最小生成树

4.4 汽车加油问题

4.5 思考题

第5章 回溯法

5.1 4皇后问题

5.2 排列组合问题

5.3 01背包问题

5.4 任务分配问题

5.5 桥本分数式

5.6 思考题

第6章 分支限界法

6.1 01背包

6.2 装载问题

6.3 布线问题

6.4 思考题

第7章 数论及Fibonacci数列

7.1 欧几里德定律

7.2 中国剩余定理

7.3 Fibonacci数列

7.4 Fibonacci与矩阵连乘

7.5 思考题

第8章 图

8.1 图的遍历

8.2 最短路径问题

8.3 最大流

8.4 二部图最大匹配

8.5 思考题

第9章 组合问题与大数运算

9.1 大数运算

9.2 平面幻方

9.3 Catalan数

9.4 P61ya计数法

9.5 思考题

第10章 背包问题

10.1 01背包问题

10.2 完备背包

10.3 多重背包

10.4 混合背包

10.5 二维背包的费用问题

10.6 分组的背包问题

10.7 有依赖的背包问题

10.8 泛化问题

10.9 思考题

第11章 博弈

11.1 巴什博奕

11.2 威佐夫博奕

11.3 Ferguson博弈

11.4 斐波那契博弈

11.5 尼姆博奕

11.6 SG函数与sG定理

11.7 思考题

参考文献

计算机算法作为程序设计的灵魂，在大型程序设计中越来越受到人们的重视，掌握常见计算机算法是计算机软件开发人员应具备的基本素质。《计算机算法基础》将经典问题和算法设计技术进行了巧妙地结合，系统地论述了算法设计技术及其在经典问题中的应用。《计算机算法基础》共11章。第1章介绍了算法的基本概念和与算法分析相关的数学问题，第2～11章分别介绍了分治法、动态规划法、回溯法、贪心法、分支限界法、图、数论、组合数学、背包、博弈等算法及设计技术。书中所有程序均在vc6．0环境下调试通过。
　　《计算机算法基础》内容丰富，深入浅出，结合应用，图例丰富，可作为程序设计大赛、计算机专业本科高年级学生和研究生学习算法的教材，也可供工程技术人员、软件设计师培训使用和读者自学参考。