新書推薦：
《
以色列史：应许之地的现代叙事 | 看世界 | 区域国别史
》
售價：HK$
94.6
《
堂吉诃德（插图珍藏版）（全2册）
》
售價：HK$
437.8
《
项目管理一本通（故事版）
》
售價：HK$
74.8
《
甲骨文丛书·法兰西美食一千年
》
售價：HK$
75.9
《
国际工程黄皮书：国际工程发展报告（2024）
》
售價：HK$
217.8
《
计算思维：信息科技跨学科主题学习实践
》
售價：HK$
74.8
《
钩编圆滚滚的瓦尤包袋
》
售價：HK$
65.8
《
日暮途穷：大清覆灭前夕的关键时刻
》
售價：HK$
96.8
|
| 編輯推薦： |
|
《算法设计与分析》是一本集系统性、实用性、思想性于一体的优质书籍。无论你是初涉算法领域的新手，还是寻求突破的专业人士，都能从这本书中汲取知识的养分。希望大家能通过这本书开启算法学习的奇妙之旅，在计算机科学的天空中翱翔。
|
| 內容簡介： |
|
算法在计算机中扮演着重要角色，它对计算机科学的发展起着重要的推动作用。算法可以被看作解决问题的方法，尽管它不是问题的答案，但它是经过准确定义以获得答案的过程，因此特定的算法设计技术可以作为问题求解的有效策略，学习算法可以培养学生分析问题和解决问题的能力。本书主要内容包括算法效率的分析方法，算法工具STL的使用，蛮力法、递归法、分治法、贪心法、动态规划法、回溯法和分支限界法七个核心算法的原理与经典问题的解决对策，学生如果具备了本课程算法设计的基本方法，可进一步学习本课程的图的搜索算法、计算几何算法、随机算法三大专题深入学习。
|
| 關於作者： |
|
高丽伟，本硕毕业于贵州大学计算机专业，已有8年教龄，一直为计算机科学与技术、智能科学与技术、电子商务等本科专业讲授算法设计与分析课程，对于该教材积累了一定的教学和编写经验。
|
| 目錄：
|
目录
第1 章算法设计与分析基础．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 1
1. 1 算法概述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． l
1. 1. 1 什么是算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 1
1. 1. 2 学习算法的重要性．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7
1.2 问题的求解过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8
1. 2. 1 问题及问题的求解过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8
1. 2. 2 算法设计与算法表示．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9
1. 2. 3 算法确认和算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 10
1. 3 数学基础．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 13
1. 3. 1 函数的渐近的界．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 14
1. 3. 2 利用极限求函数的渐近的界．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．．．．． ．．．．．．．．．17
1. 3. 3 常用的求和级数及推导方法…………………………………………… 19
1. 3. 4 基本渐近效率类型．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 21
1. 4 算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2 2
1. 4. 1 算法的时间复杂度分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 22
1. 4. 2 算法的空间复杂度分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 28
1. 4. 3 非递归算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 29
1. 4. 4 递归算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 30
1.5 关千P类、NP类和NPC类问题……………………………………… ……… 33
1. 6 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 34
1. 7 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 35
1.8 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 36
第2章算法工具STL ················································································· 38
2. 1 STL概述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 38
2. 1. 1 什么是STL容器.................................................................. 39
2. 1. 2 什么是STL算法.................................................................. 39
2. 1. 3 什么是STL迭代器............................................................... 40
2. 2 常用的STL容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 41
2. 2. 1 顺序容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 41
2.2. 2 关联容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 49
2. 2. 3 适配器容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 52
2. 3 STL在算法设计中的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 55
2.4 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 67
2. 5 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 68
2. 6 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 69
第3章蛮力法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 72
3. 1 蛮力法概述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 72
3. 1. 1 蛮力法的基本思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 72
3. 1. 2 蛮力法解题格式．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 75
3. 2 蛮力法的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 83
3. 2. 1 百钱百鸡问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 84
3. 2. 2 狱吏问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 85
3. 2. 3 顺序查找．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 88
3.2.4 简单排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 89
3. 2. 5 求解幕集问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 95
3. 2. 6 求解0/1 背包问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 98
3. 2. 7 求解最大连续子序列和问题………………………………………… 102
3. 3 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 104
3. 4 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 105
3. 5 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 105
第4章递归与分治法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 108
，． 急尸··`·
＇ ， ! 2 ; 鱼
． ....，
}，
4. 1 递归算法的思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 108
4. 1. 1 递归算法的特性．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 109
4. 1. 2 递归算法的执行过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 110
4. 1. 3 递归适用场合．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 112
4. 2 递归设计实例．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 117
4. 2. 1 几个简单的递归程序．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 117
4.2.2 排序问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 119
4.2.3 斐波那契数列问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 121
4. 2. 4 n皇后问题........................................................................ 123
4. 2. 5 汉诺塔问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 125
4. 3 分治法的思想化整为零．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 127
4. 4 分治法的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 129
4. 4. 1 二分查找算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 129
4. 4. 2 归并排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 131
4. 4. 3 快速排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 134
4. 4. 4 堆排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 136
4. 4. 5 棋盘覆盖问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 139
4. 4. 6 最大子段和问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 142
4. 5 本章小结．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 144
4. 6 习题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 145
4. 7 实验题．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 145
第5 章贪心法．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 148
5. 1 贪心法概述．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 148
5. 1. 1 问题的提出．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 148
5. 1. 2 贪心法设计思想．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 150
5. 1. 3 贪心法的基本要素．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 150
5. 1. 4 贪心法的求解过程．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 151
5. 2 贪心法的应用．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．． 152
5. 2. 1 活动安排问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 152
5. 2. 2 币种统计问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 159
5. 2. 3 背包问题．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．． 160
5. 2. 4 多机调度问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 163
5. 2. 5 哈夫曼编码．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 165
5. 2. 6 最小生成树．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 172
5. 2. 7 求解流水作业调度问题．．． ．．．．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． 178
5. 2. 8 求解川忌赛马问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 182
5. 3 本章小结．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 185
5. 4 习题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 186
5. 5 实验题．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 187
第6 章动态规划法．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 190
6. 1 动态规划法概述．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 190
6. 1. 1 动态规划法的基本思想．．． ．．．．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． 190
6. 1. 2 动态规划的设计技术．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 192
6. 2 最优决策表．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 195
6.2. 1 0/1 背包问题．．．．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 196
6.2. 2 0/1 背包的相关问题．．．．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 200
6. 3 动态规划法的应用．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．． 202
6. 3. 1 斐波那契数列．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 202
6. 3. 2 排队买票问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 203
6. 3. 3 凑硬币问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 204
6. 3. 4 数字塔问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 207
6. 3. 5 最长公共子序列问题．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 211
6. 3. 6 流水作业调度问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 214
6. 3. 7 资源分配问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 217
6. 3. 8 最短路径问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 220
6. 4 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 225
6. 5 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 225
6. 6 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 227
第7 章回溯法与分支限界法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 233
7. 1 回溯法的设计技术．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 233
7. 1. 1 回溯法的算法思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 234
7. 1. 2 回溯法的算法框架．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 236
7. 1. 3 回溯法的适用条件．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 239
7. 2 回溯法的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 243
7. 2. 1 0/1 背包问题..................................................................... 243
7. 2. 2 n皇后问题........................................................................ 248
7.2.3 旅行商问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 250
7.2.4 图的m着色问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 253
7. 2. 5 求解子集和问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 255
7. 3 分支限界法的设计技术．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 258
7. 3. 1 分支限界法的思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 258
7. 3. 2 分支限界法与回溯法对比．．．．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．．．．． ．．．．．．．．． 258
7. 3. 3 分支限界法解决的关键问题………………………………………… 259
7. 3.4 分支限界法的时间性能．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 262
7. 4 分支限界法的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 262
7. 4. 1 0/1 背包问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 262
7. 4. 2 旅行商问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 269
7. 5 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 282
7. 6 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 283
7. 7 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 284
第8 章图的搜索算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 288
，． 急尸··`·
＇ ， ! 4 ;
鱼
． ....，
}，
8. 1 广度优先搜索．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 288
8. 1. 1 算法描述与分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 288
8. 1. 2 程序实现．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 292
8. 2 深度优先搜索．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 297
8. 2. 1 算法描述与分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 297
8.2.2 程序实现．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 299
8. 3 有向图的强连通分支．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 303
8. 4 无向图的双连通分支．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 307
8. 5 网络流．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 310
8. 5. 1 相关概念．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 310
8. 5. 2 求最大流．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 312
8. 5. 3 割集与割量．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 316
8. 5. 4 求最小费用最大流．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 317
8. 6 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 32 2
8. 7 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 32 2
8. 8 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 323
第9 章计算几何算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 327
9. 1 线段的性质．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 327
9. 2 向量运算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 328
9. 2. 1 向扯加减运算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 329
9. 2. 2 向批点积运算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 330
9. 3 叉积．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 331
9. 3. 1 叉积的计算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 331
9. 3. 2 判断相继两直线段左转或右转……………………………………… 332
9. 3. 3 两个点的距离．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 333
9. 3. 4 点到线段的距离．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 333
9. 4 线段的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 334
9.4. 1 判断一个点是否在一个矩形内……………………………………… 334
9.4. 2 判断一个点是否在一条线段上……………………………………… 335
9.4. 3 判断两条线段是否平行．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 335
9.4. 4 判断两条线段是否相交．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 336
9.4. 5 判断一个点是否在多边形内………………………………………… 336
9.4. 6 求3 个点构成的三角形面积………………………………………… 338
9.4. 7 求一个多边形的面积．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 338
9. 5 求解凸包问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 340
9. 5. 1 卷包裹算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 341
9. 5. 2 葛立恒扫描法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 342
9. 6 求解最近点对问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 344
9. 7 求解最远点对问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 349
9. 8 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 352
9. 9 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 353
9. 10 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 353
第10 章随机算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 356
10.] 同余的概念．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 356
10. 2 随机数．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 358
10. 3 随机算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 360
10. 3. 1 随机算法的概念．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 360
10. 3. 2 随机算法的分类．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 360
10.4 经典随机算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 361
10. 4. 1 蒙特卡罗算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 361
10. 4. 2 舍伍德算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 362
10. 4. 3 拉斯维加斯算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 364
10. 5 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 366
10. 6 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 366
10. 7 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 367
参考文献．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 368
|
| 內容試閱：
|
|
算法在计算机中扮演着重要角色，它对计算机科学的发展起着重要的推动作用。算法可以被看作解决问题的方法，尽管它不是问题的答案，但它是经过准确定义以获得答案的过程，因此特定的算法设计技术可以作为问题求解的有效策略，学习算法可以培养学生分析问题和解决问题的能力。本书主要内容包括算法效率的分析方法，算法工具STL的使用，蛮力法、递归法、分治法、贪心法、动态规划法、回溯法和分支限界法七个核心算法的原理与经典问题的解决对策，学生如果具备了本课程算法设计的基本方法，可进一步学习本课程的图的搜索算法、计算几何算法、随机算法三大专题深入学习。
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
