《算法设计与分析(第二版)》课后答案

给大家带来的是关于算法相关的课后习题答案，介绍了关于算法设计、算法分析方面的内容，由伊安怡网友提供，本资源目前已被967人关注，高等院校算法类教材综合评分为：7.8分。

书籍介绍

《算法设计与分析（第2版）》共分四部分：部分是基础知识，包括算法设计基础和算法分析基础；第二部分是基本的算法设计技术，包括蛮力法、分治法、减治法、动态规划法和贪心法；第三部分是基于搜索的算法设计技术，包括回溯法和分支限界法；第四部分是计算的限制，介绍了问题的复杂性、近似算法和概率算法。所有问题都用伪代码给出了算法描述，大多数问题都给出了C++语言的算法实现，并且所有程序均在VC++6.0环境下调试通过。每章均附有一篇阅读材料，以通俗易懂的方式介绍了算法领域的一些新研究成果。

《算法设计与分析（第2版）》内容丰富，深入浅出，结合应用，图例丰富，可作为高等院校计算机专业本科和研究生学习算法设计与分析的教材，也可供工程技术人员和自学者学习参考。

目录

• 基础知识
• 第1章 算法设计基础
• 1．1 算法的基本概念
• 1．1．1 算法及其重要特性
• 1．1．2 算法的描述方法
• 1．1．3 算法设计的一般过程
• 1．2 为什么要学习和研究算法
• 1．2．1 算法在问题求解中的地位
• 1．2．2 算法训练能够提高计算思维能力
• 1．2．3 算法研究是推动计算机技术发展的关键
• 1．3 重要的问题类型
• 1．3．1 查找问题
• 1．3．2 排序问题
• 1．3．3 图问题
• 1．3．4 组合问题
• 1．3．5 几何问题
• 阅读材料——算法研究与图灵奖
• 习题
• 第2章 算法分析基础
• 2．1 算法的时间复杂性分析
• 2．1．1 输入规模与基本语句
• 2．1．2 算法的渐进分析
• 2．1．3 最好、最坏和平均情况
• 2．1．4 非递归算法的时间复杂性分析
• 2．1．5 递归算法的时间复杂性分析222．2 算法的空间复杂性分析
• 2．3 算法
• 2．3．1 问题的计算复杂性下界
• 2．3．2 平凡下界
• 2．3．3 判定树模型
• 阅读材料——算法的实验分析
• 习题
• 第二部分 基本的算法设计技术
• 第3章 蛮力法
• 3．1 概述
• 3．1．1 蛮力法的设计思想
• 3．1．2 一个简单的例子——百元买百鸡问题
• 3．2 查找问题中的蛮力法
• 3．2．1 顺序查找
• 3．2．2 串匹配问题
• 3．3 排序问题中的蛮力法
• 3．3．1 选择排序
• 3．3．2 起泡排序
• 3．4 组合问题中的蛮力法
• 3．4．1 0/1背包问题
• 3．4．2 任务分配问题
• 3．5 图问题中的蛮力法
• 3．5．1 哈密顿回路问题
• 3．5．2 TSP问题
• 3．6 几何问题中的蛮力法
• 3．6．1 最近对问题
• 3．6．2 凸包问题
• 阅读材料——KMP算法中next值的计算
• 习题
• 第4章 分治法
• 4．1 概述
• 4．1．1 分治法的设计思想
• 4．1．2 一个简单的例子——数字旋转方阵
• 4．2 排序问题中的分治法
• 4．2．1 归并排序
• 4．2．2 快速排序
• 4．3 组合问题中的分治法
• 4．3．1 子段和问题
• 4．3．2 棋盘覆盖问题
• 4．4 几何问题中的分治法
• 4．4．1 最近对问题
• 4．4．2 凸包问题
• 阅读材料——递归函数的执行过程
• 习题
• 第5章 减治法
• 5．1 概述
• 5．1．1 减治法的设计思想
• 5．1．2 一个简单的例子——两个序列的中位数
• 5．2 查找问题中的减治法
• 5．2．1 折半查找
• 5．2．2 二叉查找树
• 5．2．3 选择问题
• 5．3 排序问题中的减治法
• 5．3．1 插入排序
• 5．3．2 堆排序
• 5．4 组合问题中的减治法
• 5．4．1 淘汰赛冠军问题
• 5．4．2 问题
• 阅读材料——问题的复杂版本
• 习题
• 第6章 动态规划法
• 6．1 概述
• 6．1．1 多阶段决策过程
• 6．1．2 动态规划法的设计思想
• 6．1．3 一个简单的例子——数塔问题
• 6．2 图问题中的动态规划法
• 6．2．1 多段图的路径问题
• 6．2．2 多源点路径问题
• 6．2．3 TSP问题
• 6．3 组合问题中的动态规划法
• 6．3．1 递增子序列问题
• 6．3．2 公共子序列问题
• 6．3．3 0/1背包问题
• 6．4 查找问题中的动态规划法
• 6．4．1 二叉查找树
• 6．4．2 近似串匹配问题
• 阅读材料——人工神经网络
• 习题
• 第7章 贪心法
• 7．1 概述
• 7．1．1 贪心法的设计思想
• 7．1．2 一个简单的例子——埃及分数
• 7．2 图问题中的贪心法
• 7．2．1 TSP问题
• 7．2．2 图着色问题
• 7．2．3 最小生成树问题
• 7．3 组合问题中的贪心法
• 7．3．1 背包问题
• 7．3．2 活动安排问题
• 7．3．3 多机调度问题
• 阅读材料——贪心法的正确性证明
• 习题
• 第三部分 基于搜索的算法设计技术
• 第8章 回溯法
• 8．1 概述
• 8．1．1 问题的解空间树
• 8．1．2 回溯法的设计思想
• 8．1．3 回溯法的时间性能
• 8．1．4 一个简单的例子——素数环问题
• 8．2 图问题中的回溯法
• 8．2．1 图着色问题
• 8．2．2 哈密顿回路问题
• 8．3 组合问题中的回溯法
• 8．3．1 八皇后问题
• 8．3．2 批处理作业调度问题
• 阅读材料——遗传算法
• 习题
• 第9章 分支限界法
• 9．1 概述
• 9．1．1 分支限界法的设计思想
• 9．1．2 分支限界法的时间性能
• 9．1．3 一个简单的例子——圆排列问题
• 9．2 图问题中的分支限界法
• 9．2．1 TSP问题
• 9．2．2 多段图的路径问题
• 9．3 组合问题中的分支限界法
• 9．3．1 0/1背包问题
• 9．3．2 任务分配问题
• 9．3．3 批处理作业调度问题
• 阅读材料——蚁群算法
• 习题
• 第四部分 计算的限制
• 第10章 问题的复杂性
• 10．1 问题的复杂性分类
• 10．1．1 什么是计算
• 10．1．2 可计算问题与不可计算问题
• 10．1．3 易解问题与难解问题
• 10．2 P类问题和NP类问题
• 10．2．1 判定问题
• 10．2．2 确定性算法与P类问题
• 10．2．3 非确定性算法与NP类问题
• 10．3 NP完全问题
• 10．3．1 问题变换
• 10．3．2 NP完全问题的定义
• 10．3．3 基本的NP完全问题
• 10．3．4 NP完全问题的计算机处理
• 阅读材料——Cook定理
• 习题
• 第11章 近似算法
• 11．1 概述
• 11．1．1 近似算法的设计思想
• 11．1．2 一个简单的例子——求π的近似值
• 11．2 图问题中的近似算法
• 11．2．1 顶点覆盖问题
• 11．2．2 TSP问题
• 11．3 组合问题中的近似算法
• 11．3．1 装箱问题
• 11．3．2 子集和问题
• 阅读材料——粒子群算法
• 习题
• 第12章 概率算法
• 12．1 概述
• 12．1．1 概率算法的设计思想
• 12．1．2 随机数发生器
• 12．2 舍伍德型概率算法
• 12．2．1 舍伍德型概率算法的设计思想
• 12．2．2 快速排序
• 12．2．3 二叉查找树
• 12．3 拉斯维加斯型概率算法
• 12．3．1 拉斯维加斯型概率算法的设计思想
• 12．3．2 八皇后问题
• 12．3．2 整数因子划分问题
• 12．4 蒙特卡罗型概率算法
• 12．4．1 蒙特卡罗型概率算法的设计思想
• 12．4．2 主元素问题
• 12．4．3 素数测试问题
• 阅读材料——模拟淬火算法
• 习题
• 附录A 名词索引237参考文献作者介绍文摘序言部分 基础知识
• 第1章 算法设计基础
• 1．1 算法的基本概念
• 1．1．1 算法及其重要特性
• 1．1．2 算法的描述方法
• 1．1．3 算法设计的一般过程
• 1．2 为什么要学习和研究算法
• 1．2．1 算法在问题求解中的地位
• 1．2．2 算法训练能够提高计算思维能力
• 1．2．3 算法研究是推动计算机技术发展的关键
• 1．3 重要的问题类型
• 1．3．1 查找问题
• 1．3．2 排序问题
• 1．3．3 图问题
• 1．3．4 组合问题
• 1．3．5 几何问题
• 阅读材料——算法研究与图灵奖
• 习题
• 第2章 算法分析基础
• 2．1 算法的时间复杂性分析
• 2．1．1 输入规模与基本语句
• 2．1．2 算法的渐进分析
• 2．1．3 最好、最坏和平均情况
• 2．1．4 非递归算法的时间复杂性分析
• 2．1．5 递归算法的时间复杂性分析222．2 算法的空间复杂性分析
• 2．3 算法
• 2．3．1 问题的计算复杂性下界
• 2．3．2 平凡下界
• 2．3．3 判定树模型
• 阅读材料——算法的实验分析
• 习题
• 第二部分 基本的算法设计技术
• 第3章 蛮力法
• 3．1 概述
• 3．1．1 蛮力法的设计思想
• 3．1．2 一个简单的例子——百元买百鸡问题
• 3．2 查找问题中的蛮力法
• 3．2．1 顺序查找
• 3．2．2 串匹配问题
• 3．3 排序问题中的蛮力法
• 3．3．1 选择排序
• 3．3．2 起泡排序
• 3．4 组合问题中的蛮力法
• 3．4．1 0/1背包问题
• 3．4．2 任务分配问题
• 3．5 图问题中的蛮力法
• 3．5．1 哈密顿回路问题
• 3．5．2 TSP问题
• 3．6 几何问题中的蛮力法
• 3．6．1 最近对问题
• 3．6．2 凸包问题
• 阅读材料——KMP算法中next值的计算
• 习题
• 第4章 分治法
• 4．1 概述
• 4．1．1 分治法的设计思想
• 4．1．2 一个简单的例子——数字旋转方阵
• 4．2 排序问题中的分治法
• 4．2．1 归并排序
• 4．2．2 快速排序
• 4．3 组合问题中的分治法
• 4．3．1 子段和问题
• 4．3．2 棋盘覆盖问题
• 4．4 几何问题中的分治法
• 4．4．1 最近对问题
• 4．4．2 凸包问题
• 阅读材料——递归函数的执行过程
• 习题
• 第5章 减治法
• 5．1 概述
• 5．1．1 减治法的设计思想
• 5．1．2 一个简单的例子——两个序列的中位数
• 5．2 查找问题中的减治法
• 5．2．1 折半查找
• 5．2．2 二叉查找树
• 5．2．3 选择问题
• 5．3 排序问题中的减治法
• 5．3．1 插入排序
• 5．3．2 堆排序
• 5．4 组合问题中的减治法
• 5．4．1 淘汰赛冠军问题
• 5．4．2 问题
• 阅读材料——问题的复杂版本
• 习题
• 第6章 动态规划法
• 6．1 概述
• 6．1．1 多阶段决策过程
• 6．1．2 动态规划法的设计思想
• 6．1．3 一个简单的例子——数塔问题
• 6．2 图问题中的动态规划法
• 6．2．1 多段图的路径问题
• 6．2．2 多源点路径问题
• 6．2．3 TSP问题
• 6．3 组合问题中的动态规划法
• 6．3．1 递增子序列问题
• 6．3．2 公共子序列问题
• 6．3．3 0/1背包问题
• 6．4 查找问题中的动态规划法
• 6．4．1 二叉查找树
• 6．4．2 近似串匹配问题
• 阅读材料——人工神经网络
• 习题
• 第7章 贪心法
• 7．1 概述
• 7．1．1 贪心法的设计思想
• 7．1．2 一个简单的例子——埃及分数
• 7．2 图问题中的贪心法
• 7．2．1 TSP问题
• 7．2．2 图着色问题
• 7．2．3 最小生成树问题
• 7．3 组合问题中的贪心法
• 7．3．1 背包问题
• 7．3．2 活动安排问题
• 7．3．3 多机调度问题
• 阅读材料——贪心法的正确性证明
• 习题
• 第三部分 基于搜索的算法设计技术
• 第8章 回溯法
• 8．1 概述
• 8．1．1 问题的解空间树
• 8．1．2 回溯法的设计思想
• 8．1．3 回溯法的时间性能
• 8．1．4 一个简单的例子——素数环问题
• 8．2 图问题中的回溯法
• 8．2．1 图着色问题
• 8．2．2 哈密顿回路问题
• 8．3 组合问题中的回溯法
• 8．3．1 八皇后问题
• 8．3．2 批处理作业调度问题
• 阅读材料——遗传算法
• 习题
• 第9章 分支限界法
• 9．1 概述
• 9．1．1 分支限界法的设计思想
• 9．1．2 分支限界法的时间性能
• 9．1．3 一个简单的例子——圆排列问题
• 9．2 图问题中的分支限界法
• 9．2．1 TSP问题
• 9．2．2 多段图的路径问题
• 9．3 组合问题中的分支限界法
• 9．3．1 0/1背包问题
• 9．3．2 任务分配问题
• 9．3．3 批处理作业调度问题
• 阅读材料——蚁群算法
• 习题
• 第四部分 计算的限制
• 第10章 问题的复杂性
• 10．1 问题的复杂性分类
• 10．1．1 什么是计算
• 10．1．2 可计算问题与不可计算问题
• 10．1．3 易解问题与难解问题
• 10．2 P类问题和NP类问题
• 10．2．1 判定问题
• 10．2．2 确定性算法与P类问题
• 10．2．3 非确定性算法与NP类问题
• 10．3 NP完全问题
• 10．3．1 问题变换
• 10．3．2 NP完全问题的定义
• 10．3．3 基本的NP完全问题
• 10．3．4 NP完全问题的计算机处理
• 阅读材料——Cook定理
• 习题
• 第11章 近似算法
• 11．1 概述
• 11．1．1 近似算法的设计思想
• 11．1．2 一个简单的例子——求π的近似值
• 11．2 图问题中的近似算法
• 11．2．1 顶点覆盖问题
• 11．2．2 TSP问题
• 11．3 组合问题中的近似算法
• 11．3．1 装箱问题
• 11．3．2 子集和问题
• 阅读材料——粒子群算法
• 习题
• 第12章 概率算法
• 12．1 概述
• 12．1．1 概率算法的设计思想
• 12．1．2 随机数发生器
• 12．2 舍伍德型概率算法
• 12．2．1 舍伍德型概率算法的设计思想
• 12．2．2 快速排序
• 12．2．3 二叉查找树
• 12．3 拉斯维加斯型概率算法
• 12．3．1 拉斯维加斯型概率算法的设计思想
• 12．3．2 八皇后问题
• 12．3．2 整数因子划分问题
• 12．4 蒙特卡罗型概率算法
• 12．4．1 蒙特卡罗型概率算法的设计思想
• 12．4．2 主元素问题
• 12．4．3 素数测试问题
• 阅读材料——模拟淬火算法
• 习题
• 附录A 名词索引237参考文献