常用算法程序集（C语言描述）（第三版）
清晰PDF版，配完整源代码。
第1章 多项式的计算
1.1 一维多项式求值
1.2 一维多项式多组求值
1.3 二维多项式求值
1.4 复系数多项式求值
1.5 多项式相乘
1.6 复系数多项式相乘
1.7 多项式相除
1.8 复系数多项式相除
第2章 复数运算
2.1 复数乘法
2.2 负数除法
2.3 复数乘幂
2.4 复数的n次方根
2.5 复数指数
2.6 复数对数
2.7 复数正弦
2.8 复数余弦
第3章 随机数的产生
3.1 产生0到1之间均匀分布的一个随机数
3.2 产生0到1之间均匀分布的随机数序列
3.3 产生任意区间内均匀分布的一个随机整数
3.4 产生任意区间内均匀分布的随机整数序列
3.5 产生任意均值与方差的正态分布的一个随机数
3.6 产生任意均值与方差的正态分布的随机数序列
第4章 矩阵运算
4.1 实矩阵相乘
4.2 复矩阵相乘
4.3 一般实矩阵求逆
4.4 一般复矩阵求逆
4.5 对称正定矩阵的求逆
4.6 托伯利兹矩阵求逆的特兰持方法
4.7 求一般行列式的值
4.8 求矩阵的值
4.9 对称正定矩阵的乔里斯基分解与列式求值
4.10 矩阵的三角分解
4.11 一般实矩阵的QR分解
4.12 一般实矩阵的奇异值分解
4.13 求广义逆的奇异值分解法
第5章 矩阵特征值与特征向量的计算
5.1 约化对称矩阵为对称三对角阵的豪斯荷尔德变换法
5.2 求对称三对角阵的全部特征值与特征向量
5.3 约化一般实矩阵为赫申伯格矩阵的初等相似变换法
5.4 求赫身伯格矩阵全部特征的QR方法
5.5 求实对称矩阵特征值与特征向量的雅可比法
5.6 求实对称矩阵特征值与特征向量的雅可比过关法
第6章 线性代数方程组的求解
6.1 求解实系数方程组的全选主元高斯消去法
6.2 求解实系数方程组的全选主元高斯-约当消去法
6.3 求解复系数方程组的全选主元高斯消去法
6.4 求解复系数方程组的全选主元高斯-约当消去法
6.5 求解三对角线方程组的追赶法
6.6 求解一般带型方程组
6.7 求解对称方程组的分解法
6.8 求解对称正定方程组的平方根法
6.9 求解大型系数方程组
6.10 求解托伯利兹方程组的列文逊方法
6.11 高斯-塞德尔失代法
6.12 求解对称正定方程组的共岿梯度法
6.13 求解线性最小二乘文体的豪斯伯尔德变换法
6.14 求解线性最小二乘问题的广义逆法
6.15 求解病态方程组
第7章 非线性方程与方程组的求解
7.1 求非线性方程一个实根的对分法
7.2 求非线性方程一个实根的牛顿法
7.3 求非线性方程一个实根的埃特金矢代法
7.4 求非线性方程一个实根的连分法
7.5 求实系数代数方程全部的QR方法
7.6 求实系数方程全部的牛顿下山法
7.7 求复系数方程的全部根牛顿下山法
7.8 求非线性方程组一组实根的梯度法
7.9 求非线性方程组一组实根的拟牛顿法
7.10 求非线性方程组最小二乘解的广义逆法
7.11 求非线性方程一个实根的蒙特卡洛法
7.12 求实函数或复函数方程一个复根的蒙特卡洛法
7.13 求非线性方程组一组实根的蒙特卡洛法
第8章 插值与逼近
8.1 一元全区间插值
8.2 一元三点插值
8.3 连分式插值
8.4 埃尔米特插值
8.5 特金逐步插值
8.6 光滑插值
8.7 第一种边界条件的三次样条函数插值
8.8 第二种边界条件的三次样条函数插值
8.9 第三种边界条件的三次样条函数插值
8.10 二元三点插值
8.11 二元全区间插值
8.12 最小二乘曲线拟合
8.13 切比雪夫曲线拟合
8.14 最佳一致逼近的里米兹方法
8.15 矩形域的最小二乘曲线拟合
第9章 数值积分
9.1 变补长梯形求积法
9.2 变步长辛卜生求积法
9.3 自适应梯形求积法
9.4 龙贝格求积法
9.5 计算一维积分的连分式法
9.6 高振荡函数求积法
9.7 勒让德-高斯求积法
9.8 拉盖尔-高斯求积法
9.9 埃尔米特-高斯求积法
9.10 切比雪夫求积法
9.11 计算一维积分的蒙特卡洛法
9.12 变步长辛卜生二重积分方法
9.13 计算多重积分的高斯方法
9.14 计算二重积分的连分方式
9.15 计算多重积分的蒙特卡洛法
第10章 常微分方程组的求解
10.1 全区间积分的定步长欧拉方法
10.2 积分一步的变步长欧拉方法
10.3 全区间积分维梯方法
10.4 全区间积分的定步长龙格-库塔方法
10.5 积分一步的变步长龙格-库塔方法
10.6 积分一步的变步长基尔方法
10.7 全区间积分的变步长默森方法
10.8 积分一步的连分方式
10.9 全区间积分的双边法
10.10 全区间积分的阿当姆斯预报校正法
2021-03-16 21:39:15
6.29MB
1
前言 如果我们预挑出计算机科学中那些影响长久的贡献，算法（algorithm）一定位列其中。自从人类发明了可以执行基本数学运算的机器，什么是可以计算的以及如何计算就成为人们一直研究的课题。伴随此项研究，人们发现了大量的重要算法以及设计方法。算法成为计算机科学领域中的一项重要组成部分。本书的目的就是对有关算法的内容精心地组织，从而使得使用本书的同学以及实践者可以设计和分析全新的算法。 一本包含所有已发明的算法的书将会异常冗长。传统的算法书通常只对很少的几个问题领域有深入的阐述。对于每个问题，通常会给出并分析效率最高的算法。这样的做法有一个主要缺点。尽管同学们了解了很多很快的算法并且也掌握了分析算法的工具，但还是对如何设计一个好的算法信心不足。 这里所欠缺的就是没有强调设计（design）技术。设计方面的知识一定可以帮助创造好的算法，没有分析工具则无法判断算法的优劣。这样设计为主分析为辅的关系就自然地延伸为有效的讲授之道：我们将围绕基本的算法设计策略来组织本书。基本的设计策略是相对比较少的。并且大部分读者想要学习的算法可以划分到这些分类中；例如归并排序和快速排序是分治策略的例子，而Kruskal的最小生成树算法和Dijkstra的单源最短路径算法是贪心策略的例子。理解这些策略是掌握设计技能的重要的第一步。 尽管我们深切地认为强调设计以及分析是组织算法学习的正确之路，这里还是要给出一些注意事项。首先，我们并没有包括所有的设计原理。例如线性规划是最成功的技术之一，由于它往往由单独的课程所讲述从而没有包含到本书中。其次，读者不应该死板地学习算法设计，认为每个算法都是由一种技术得到的。事实并不是如此。 本书的主要篇幅，第3～9章，描述了不同的设计策略。每种策略首先描述一个大概。通常给出一个“程序抽象”来描述采用该策略所形成的计算模式的大纲。接着给出一系列的例子来讲述该策略的复杂以及变化。这些例子往往是按照由易到难的次序安排。其复杂的程度可以在不同的方面升高。我们通常先给出一个非常容易理解的例子，所使用的数据结构也仅仅为一维的数组。对这个例子，所用设计策略显而易见可以得到正确的解法。后面的例子可能需要证明基于该设计技术的算法是正确的。也可能是需要更加复杂的数据结构（例如树或者图），并且分析更加复杂。这样组织的主要目的是强调组成和分析算法的艺术。另外还希望能让读者体会好的程序结构以及算法正确性的证明。 第1～12章中的算法都是用C++或者伪C++代码给出。很多是可以直接运行并且已经经过测试的。选择C++是因为它是面向对象的程序语言。C++在计算机业界被广泛接受还有其他的很多理由。选择这种程序语言并不是说不熟悉C++的读者就不能用这本书。因为本书中大部分的算法都是比较短的，用来描述这些算法的代码也足够简单可以被广大读者所理解。第13～15章讲述并行计算。并行计算是一个飞速发展的领域，没有一个被广泛接受的模型或者程序语言。因此，我们选择用伪代码来描述这些算法。第1～12章中也有些简单的算法是用伪代码描述的。这是因为我们认为这些算法的核心思想用伪代码描述更加清晰。如何将这些伪代码转换为C++代码将作为练习留给读者。 另外本书的一大特色是广泛地讨论了随机算法。第13～15章中的很多算法是随机的。其他章节中也包含了一些随机算法。一门学季制的并行算法导论课程可以包含第13～15章，以及其他少量的补充内容。 我们也标出了一些内容（用*号）是适用于高级课程的。这本书的内容可以作为本科高年级学生或者研究生的一门学期制课程，或者两门学季制的课程。它需要学生具备高级语言的编程能力，其余的内容都自完备的。实践上，一门数据结构课也是有帮助的，这样学生具备更成熟的编程能力。如果是学季制的学校，第一个学季可以讲授一些基本的设计技术，例如第3章～第9章中的分治、贪心、动态规划、搜索和遍历、回溯、分治定界以及代数方法（见表Ⅰ）。第二个学季可以讲授第10～15章：下界定理、 D_Dd__________ǒe??_____________ 如果课程是一个学期的，并且学生之前没有接触过数据结构和大O表示，那么第1～7章、第11章以及第13章的内容比较合适（见表Ⅲ）。 如果进度更加紧凑一些可以包含第1～7章、第11章、第13章以及第14章的内容（见表Ⅳ）。 如果学生已经掌握了数据结构和大O表示，可以由第3～11章，以及第13～15章构成一门高级课程（见表Ⅴ）。 表Ⅰ 第一学季 周次 内容 阅读 1 引言 1.1-1.3 2 引言 数据结构 1.4 2.1、2.2 3 数据结构 2.3-2.6 4 分治 第3章 第一次作业 5 贪心算法 第4章 期中考试 6 动态规划 第5章 7 搜索与遍历 第6章 第二次作业 8 回溯 第7章 9 分支定界 第8章 10 代数方法 第9章 第三次作业
2021-03-09 14:42:10
125.37MB
1