算法设计与问题求解 微课版

"重量一流本科课程配套教材 全国高等学校计算机教育研究会“十四五”规划教材 本书有教学课件、教学大纲、教学计划、教学视频、源代码 "

本书是为以算法设计、问题求解为阅读目的的读者编写的教材，注重培养读者的算法设计与分析、问题求解的能力。本书读者需要掌握程序设计、数据结构等基础知识，并具备一定的编程能力。
本书以算法设计与分析为主线，通过问题和案例引入内容，重点讲解利用算法求解问题的思路、算法执行过程及能力拓展。本书主要内容为算法基础、蛮力法、递归法、分治法、贪心法、回溯法、分支限界法、动态规划法、图算法、随机算法等，讲解了背包问题、任务分配问题、批处理作业调度问题、很优装载问题、旅行商问题、计算几何等经典问题，并提供了能力拓展环节，引导读者开展算法应用实践。算法使用c语言程序、伪代码等形式加以描述，并用图解的形式详细描述算法的执行过程，使读者能够深入了解算法的运行过程和结果。
本书可作为本科院校算法设计与分析的教学用书，也可作为从事算法设计的科技人员、算法竞赛选手的参考书及培训教材。

邓泽林，博士，长沙理工大学计算机与通信工程学院软件工程系主任、特聘教授。主要从事模式识别、深度学习等相关研究。重量一流本科课程“程序设计、算法与数据结构”负责人，ACM程序设计类竞赛教练，近两年指导学生获得ACM ICPC亚洲区域赛、天梯赛等重量赛事一等奖1项、二等奖7项、三等奖十余项。

第1章 算法基础
1.1 算法概念
1.2 算法描述
1.3 算法主要类别及典型问题
1.3.1 递归法
1.3.2 递推法
1.3.3 穷举法
1.3.4 贪心算法
1.3.5 分治法
1.3.6 动态规划法
1.3.7 分支限界法
1.3.8 回溯法
1.4 算法复杂度
1.4.1 算法输入规模度量
1.4.2 算法运行时间的度量
1.4.3 渐进符号
1.4.4 算法复杂度分析
1.5 标准模板库
1.5.1 动态数组vector的使用
1.5.2 集合set的使用
1.5.3 映射map的使用
1.5.4 栈stack的使用
1.5.5 队列与优先队列的使用
1.5.6 排序sort的使用
习题
第2章 递归算法设计
2.1 概述
2.2 递归算法设计思想
2.2.1 递归定义
2.2.2 递归应用
2.3 递归算法示例与过程分析
2.3.1 汉诺塔问题
2.3.2 逆波兰表达式
2.4 递归转化为非递归
2.4.1 递归转尾递归
2.4.2 递归转非递归
2.5 能力拓展
2.5.1 K数列
2.5.2 猴子爬树
2.5.3 分黑球
习题
第3章 蛮力法
3.1 概述
3.2 蛮力法的主要设计思想
3.2.1 使用蛮力法的几种情况
3.2.2 蛮力法的求解步骤
3.3 蛮力法示例与分析
3.3.1 选择排序
3.3.2 旅行商问题
3.3.3 字符串匹配蛮力解决
3.3.4 0-1背包问题
3.4 能力拓展
3.4.1 连续数和
3.4.2 矩形个数
习题
第4章 分治法
4.1 概述
4.2 分治法设计思路
4.3 分治法应用与过程分析
4.3.1 优选子段和
4.3.2 归并排序
4.3.3 棋盘覆盖问题
4.3.4 最近点对问题
4.4 能力拓展
4.4.1 第k位数
4.4.2 二进制的接近表示
4.4.3 最小违和度
习题
第5章 回溯法
5.1 概述
5.2 回溯法设计思路
5.3 回溯法示例与过程分析
5.3.1 n皇后问题
5.3.2 0-1背包问题
5.3.3 图的m着色问题
5.3.4 批处理作业调度问题
5.4 能力拓展
5.4.1 全排列问题
5.4.2 存在障碍物的迷宫问题
5.4.3 图的m着色问题变种
5.5 习题
第6章 贪心法
6.1 概述
6.2 贪心法设计思路
6.3 贪心法示例与过程分析
6.3.1 部分背包问题
6.3.2 很优装载问题
6.3.3 乘船问题
6.3.4 旅行商问题
6.4 能力拓展
6.4.1 田忌赛马问题
6.4.2 过河问题
习题
第7章 分支限界法
7.1 概述
7.2 分支限界法设计思路
7.3 分支限界法示例与过程分析
7.3.1 0-1背包问题
……