算法趣学

“算法分析与设计”的课程目标是培养运用数学思维和计算思维分析问题和应用所学专业知识解决问题的能力。通过对理论基础和典型案例的学习，使读者能够掌握算法设计的方法和技巧，为后续数据结构等相关课程的学习及参加各类学科竞赛奠定基础。
在学习本书之前，读者应具备一定的编程基础，能够熟练运用C 、C、Java、Python等至少一门编程语言，无须具备数据结构知识基础。本书是程序设计基础和算法分析与设计之间的过渡，为刚刚学习过程序设计基础的算法入门者量身定制。
本书的主要特点是算法知识“基础化”和分析过程“图表化”。只要求读者具备程序设计基础知识，重在兴趣与入门，不涉及艰深晦涩的内容。以图表方式给出算法的动态分析过程，使读者真正理解和掌握算法的本质，能够根据实际工作设计和优化算法。
全书分9章，各章具体内容如下。
第1章 环境搭建。主要介绍Windows操作系统下学习环境的搭建及注意事项。
第2章 排序算法。介绍冒泡排序、选择排序、插入排序和计数排序等常见排序算法。
第3章 递归算法。分析递归算法的本质特征，并通过递归算法求解汉诺塔、全排列、因数分解和分形图形问题。
第4章 数论基础。介绍数论的基本概念及性质，分析素数和同余两类典型的数论基础问题。
第5章 组合数学基础。介绍组合数学的基本概念和性质，分析排列和组合生成的典型算法。
第6章 贪心算法。介绍结构体类型，分析活动时间安排、装载、可切割背包、删数问题及操作系统内存分配等典型贪心算法案例。
第7章 分治算法。介绍分治算法的基本思想，应用分治思想求解快速排序、归并排序、二分查找、循环赛及大整数乘法问题。
第8章 动态规划算法。介绍动态规划算法的特点和解题过程，利用动态规划算法求解数字三角形、长公共子序列、编辑距离、01背包问题及石子合并问题。
第9章 回溯算法。介绍回溯算法的解题思路，通过图表详细分析八皇后问题、子集和问题、01背包问题、装载问题及任务分配问题的探索和回溯过程。
算法分析与设计的核心是体会和实践，讲授是基础，实践是关键。本书提供各典型案例相关的全部源代码(C和C 版本，在VC 2010、VC 2019及Code::Blocks中调试通过)。
本书是授课教师多年教学经验的总结，但由于作者水平所限，难免存在遗漏和不足之处，敬请读者批评指正，在此表示诚挚谢意。

作者2021年1月

本书系统介绍程序设计中常用的基础算法及典型案例，包括排序算法、递归算法、数论基础、组合数学基础、贪心算法、分治算法、动态规划算法和回溯算法等内容。 全书以图文并茂的方式讲解各种基础算法的分析过程，侧重于基础算法的深入理解与实践，配有大量图表辅助算法的分析过程，适用于有一定程序设计基础、尚未学习数据结构且对算法分析与设计感兴趣的算法初学者。 本书各章节配有典型案例和大量图表，既便于教师课堂讲授，也适合读者自学，可作为高等院校“程序设计基础”课程的延伸和“算法分析与设计”课程的入门教材，也可供程序设计竞赛初学者参考。

英昌盛，男，1979年生，博士，吉林师范大学计算机学院系主任，主要研究方向为云计算及算法分析与设计。教学及科研成果：发表SCI论文2篇，EI论文1篇；主编教材1部，参编教材3部；主持及参与省教改项目2项、省职业与成人教育项目1项、协同育人项目4项；参与并完成吉林省金课1项，作为主要参加人参与申报并成功获批一流专业、一流课程。

第1章环境搭建1
1.1Microsoft Visual C 2010学习版使用1
1.1.1Visual C 2010学习版安装2
1.1.2创建、编辑、编译和运行项目4
1.1.3为什么缺少很多选项8
1.1.4为什么一闪而过9
1.1.5其他配置选项10
1.2Code::Blocks的使用14
1.2.1安装Code::Blocks14
1.2.2创建项目和编辑源代码16
1.2.3调试20

第2章排序算法23
2.1冒泡排序24
2.1.1冒泡排序的基本思想24
2.1.2冒泡排序过程分析24
2.1.3冒泡排序代码分析26
2.2选择排序28
2.2.1选择排序的基本思想28
2.2.2选择排序过程分析28
2.2.3选择排序代码分析30
2.3插入排序31
2.3.1插入排序的基本思想31
2.3.2插入排序过程分析32
2.3.3插入排序代码分析33
2.4计数排序35
2.4.1计数排序的基本思想35
2.4.2计数排序过程分析35
2.4.3计数排序代码分析37
2.4.4统计句子中字母出现次数39

第3章递归算法42
3.1汉诺塔问题42
3.1.1汉诺塔问题解题思路分析42
3.1.2汉诺塔问题代码分析44
3.2全排列问题45
3.2.1无重复元素的全排列46
3.2.2有重复元素的全排列48
3.3因数分解问题50
3.3.1因子递增方式递归求解51
3.3.2子问题分解方式递归求解52
3.3.3分解因数问题代码分析52
3.4分形图形54
3.4.1盒分形思路分析54
3.4.2盒分形代码分析55

第4章数论基础58
4.1余数和公约数58
4.1.1余数58
4.1.2公约数61
4.1.3欧几里得算法61
4.2素数问题62
4.2.1素数的概念63
4.2.2素数相关的定理63
4.2.3筛选法求素数64
4.3同余问题71
4.3.1同余及其性质71
4.3.2线性同余72

第5章组合数学基础90
5.1排列生成算法90
5.1.1序数生成法91
5.1.2字典序生成法94
5.1.3“火星人”问题95
5.2组合生成算法97
5.2.1基于字典序的组合生成算法98
5.2.2基于格雷码的组合生成算法102第6章贪心算法111
6.1结构体111
6.2贪心算法概述113
6.3活动时间安排114
6.3.1活动安排过程分析115
6.3.2活动安排代码分析117
6.4装载问题119
6.4.1装载问题过程分析119
6.4.2装载问题代码分析120
6.5可切割背包问题122
6.5.1可切割背包问题分析122
6.5.2可切割背包代码分析124
6.6删数问题126
6.7操作系统内存分配128
6.7.1First Fit内存分配130
6.7.2Best Fit内存分配131
6.7.3Worst Fit内存分配133

第7章分治算法135
7.1快速排序136
7.1.1快速排序过程分析136
7.1.2快速排序代码分析138
7.2归并排序139
7.2.1归并排序过程分析140
7.2.2归并排序代码分析140
7.3二分查找142
7.3.1二分查找过程分析142
7.3.2二分查找代码分析143
7.4循环赛145
7.4.12k循环赛日程表145
7.4.2奇偶循环赛日程表149
7.5大整数乘法153
7.5.1大整数乘法过程分析154
7.5.2大整数乘法代码分析155

第8章动态规划算法159
8.1数字三角形159
8.1.1使用朴素递归求解数字三角形问题160
8.1.2使用动态规划算法求解数字三角形问题161
8.2长公共子序列168
8.2.1长公共子序列问题过程分析168
8.2.2长公共子序列问题代码分析169
8.3编辑距离172
8.3.1编辑距离的正向生成172
8.3.2操作序列的逆向回溯174
8.401背包问题（一）178
8.4.101背包问题过程分析179
8.4.201背包问题代码分析180
8.5石子合并183
8.5.1石子合并问题过程分析184
8.5.2石子合并问题代码分析185

第9章回溯算法193
9.1八皇后问题193
9.1.1八皇后问题过程分析193
9.1.2八皇后问题代码分析195
9.2子集和问题198
9.2.1子集和问题过程分析198
9.2.2子集和问题代码分析199
9.301背包问题（二）202
9.3.101背包问题过程分析202
9.3.201背包问题代码分析204
9.4装载问题206
9.4.1装载问题过程分析206
9.4.2装载问题代码分析207
9.5任务分配问题209
9.5.1任务分配问题过程分析209
9.5.2任务分配问题代码分析210

参考文献213