算法设计与问题求解——计算思维培养 第2版

在信息时代，计算思维是解决复杂工程问题的重要思维方式，计算机则是求解问题的重要工具。本书以计算机经典问题求解为导向，通用算法思维和编程能力培养为目标，引入ACM国际大学生程序设计竞赛的有益元素，组织教材的理论教学和编程实践两方面的内容。本书主要内容包括计算机问题求解的经典算法模型和设计范式，包括计算机问题求解中常用的数据结构、枚举算法、递归与分治策略、动态规划、贪心算法和搜索技术。除了强调经典的问题原型和算法原理，本书兼顾编程实践能力，力图使得学生面对复杂问题时既能“想到”还能“做到”。

第1章计算机问题求解概述
1.1问题与问题实例
1.2计算机问题求解周期
1.3算法与程序
1.4算法复杂性分析
1.4.1空间复杂性
1.4.2时间复杂性
习题1
第2章程序设计语言与数据结构
2.1程序设计语言的“盲点”
2.1.1long不够长
2.1.2double不够准
2.1.3递归不够快
2.2基本数据结构
2.2.1线性表
2.2.2栈和队列
2.2.3树和二叉树
2.2.4优先队列和堆
2.2.5图
2.2.6并查集
2.3标准模板库
2.3.1模板的基本概念
2.3.2标准模板库概述
2.3.3标准模板库应用
习题2
第3章枚举算法
3.1枚举的基本思想
3.2模糊数字
3.3真假银币
3.4m钱n鸡
3.5数字配对
3.6绳子切割
3.7石头距离
习题3
第4章递归与分治
4.1递归程序
4.2分治法的基本原理
4.3合并排序
4.4逆序对问题
4.5快速排序
4.6最接近点对问题
4.7指数运算
4.8二分查找
习题4
第5章动态规划
5.1动态规划的基本思想
5.1.1动态规划的基本要素
5.1.2动态规划的求解步骤
5.2矩阵连乘
5.3很优二叉搜索树
5.4多段图最短路径
5.5最长公共子序列
5.60-1背包问题
5.7优选上升子序列
习题5
第6章贪心算法
6.1贪心算法的基本要素
6.2活动安排问题
6.3小数背包问题
6.4很优前缀码
6.5单源最短路径
6.6最小生成树
6.6.1Prim算法
6.6.2Kruskal算法
习题6
第7章搜索技术
7.1问题的状态空间表示
7.2深度优先搜索
7.3广度优先搜索
7.4回溯算法
7.4.1回溯算法的基本原理和框架程序
7.4.2装载问题的回溯算法
7.4.3圆排列问题
7.5分支限界
7.5.1分支限界法的基本原理
7.5.2装载问题的分支限界法
7.6启发式搜索
7.6.1启发式搜索基本原理
7.6.2装载问题的启发式搜索
习题7
附录A复杂度分析的数学基础
附录B常用C语言和STL函数
附录C程序设计竞赛和OnlineJudge介绍
附录D教学资源
参考文献