算法第四章

高一《数据与计算》（必修）第四章《算法及其特征》一、引言在计算机科学领域，算法是指用来解决问题的一系列步骤或方法。

在本章中，我们将学习什么是算法，算法的特征，以及算法设计的基本原则。

二、算法的概念2.1 算法定义算法是对问题求解步骤的一种描述，是指令的有限序列。

算法是基于确定性的、可执行的，并能在有限步骤内完成的。

一个好的算法应具备清晰、无二义性、可行性和有穷性。

2.2 算法的基本特征•输入：算法具有零个或多个输入。

输入是算法从外部获取的数据，用于算法的运行。

•输出：算法具有一个或多个输出。

输出是算法根据输入产生的结果。

•有穷性：算法应该在有限次的执行后终止。

•确定性：算法的每一步都应该明确且无二义性地定义。

•可行性：算法中的每一步都应该是可行的，即能够被计算机执行。

三、算法设计的基本原则在设计算法时，我们需要遵循以下基本原则：3.1 合理性算法应该能够实现给定的问题解决要求。

它需要合理地应对问题的各种情况和输入。

3.2 可读性算法的设计应该易于理解和阅读。

良好的代码注释和适当的命名方式，可以提高算法的可读性。

3.3 健壮性算法应该能够正确地处理各种异常情况，例如无效输入或异常数据。

算法的设计应尽量减少计算的时间。

一个高效的算法应该能够在合理的时间内给出结果。

3.5 空间效率算法的设计应尽量减少需要的存储空间。

一个高效的算法应该能够有效地使用计算机的内存。

四、常见算法在计算机科学中，有许多已经被广泛使用的算法。

下面是一些常见的算法：4.1 排序算法•冒泡排序•插入排序•选择排序•快速排序•归并排序4.2 查找算法•顺序查找•二分查找•哈希查找4.3 图算法•最短路径算法•拓扑排序算法•最小生成树算法4.4 字符串匹配算法•BF算法•KMP算法五、算法的复杂度分析在算法设计中，我们需要对算法的复杂度进行评估。

算法的复杂度分析可以通过对其时间复杂度和空间复杂度进行评估。

时间复杂度描述了算法在运行时所需要的时间。

《数据结构与算法》第四章串知识点及例题精选串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。

4.1 串及其基本运算4.1.1 串的基本概念１．串的定义串是由零个或多个任意字符组成的字符序列。

一般记作：s=＂s1 s2 … s n＂＂其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；a i(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。

２．几个术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。

包含子串的串相应地称为主串。

子串的位置：子串的第一个字符在主串中的序号称为子串的位置。

串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。

4.2 串的定长顺序存储及基本运算因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。

4.2.1 串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256char s[MAXSIZE];则串的最大长度不能超过256。

如何标识实际长度？1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct{ char data[MAXSIZE];int curlen;} SeqString;定义一个串变量：SeqString s;这种存储方式可以直接得到串的长度：s.curlen+1。

如图4.1所示。

s.dataMAXSIZE-1图4.1 串的顺序存储方式12. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。

算法设计与分析第三版第四章课后习题答案4.1 线性时间选择问题习题4.1问题描述：给定一个长度为n的无序数组A和一个整数k，设计一个算法，找出数组A中第k小的元素。

算法思路：本题可以使用快速选择算法来解决。

快速选择算法是基于快速排序算法的思想，通过递归地划分数组来找到第k小的元素。

具体步骤如下： 1. 选择数组A的一个随机元素x作为枢纽元。

2. 使用x将数组划分为两个子数组A1和A2，其中A1中的元素小于等于x，A2中的元素大于x。

3. 如果k等于A1的长度，那么x就是第k小的元素，返回x。

4. 如果k小于A1的长度，那么第k小的元素在A1中，递归地在A1中寻找第k小的元素。

5. 如果k大于A1的长度，那么第k小的元素在A2中，递归地在A2中寻找第k-A1的长度小的元素。

6. 递归地重复上述步骤，直到找到第k小的元素。

算法实现：public class LinearTimeSelection {public static int select(int[] A, int k) { return selectHelper(A, 0, A.length - 1, k);}private static int selectHelper(int[] A, int left, int right, int k) {if (left == right) {return A[left];}int pivotIndex = partition(A, left, righ t);int length = pivotIndex - left + 1;if (k == length) {return A[pivotIndex];} else if (k < length) {return selectHelper(A, left, pivotInd ex - 1, k);} else {return selectHelper(A, pivotIndex + 1, right, k - length);}}private static int partition(int[] A, int lef t, int right) {int pivotIndex = left + (right - left) / 2;int pivotValue = A[pivotIndex];int i = left;int j = right;while (i <= j) {while (A[i] < pivotValue) {i++;}while (A[j] > pivotValue) {j--;}if (i <= j) {swap(A, i, j);i++;j--;}}return i - 1;}private static void swap(int[] A, int i, int j) {int temp = A[i];A[i] = A[j];A[j] = temp;}}算法分析：快速选择算法的平均复杂度为O(n)，最坏情况下的复杂度为O(n^2)。

第四章 共轭梯度法§4.1 共轭方向法共轭方向法是无约束最优化问题的一类重要算法。

它一方面克服了最速下降法中，迭代点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共轭方向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。

一、共轭方向定义4.1 设G 是n n ⨯对称正定矩阵，1d ，2d 是n 维非零向量，若120T d Gd = （4.1）则称1d ，2d 是G －共轭的。

类似地，设1,,m d d 是nR 中一组非零向量。

若0T i j d Gd =()i j ≠ （4.2）则称向量组1,,m d d 是G －共轭的。

注：(1) 当G I =时，共轭性就变为正交性，故共轭是正交概念的推广。

(2) 若1,,m d d G －共轭，则它们必线性无关。

二、共轭方向法共轭方向法就是按照一组彼此共轭方向依次搜索。

模式算法：1）给出初始点0x ，计算00()g g x =，计算0d ，使000Td g <，:0k = （初始共轭方向）； 2）计算k α和1k x +，使得0()min ()k k k k k f x d f x d ααα≥+=+，令1k k k k x x d α+=+；3）计算1k d +，使10Tk j d Gd +=，0,1,,j k = ，令:1k k =+，转2）。

三、共轭方向法的基本定理共轭方向法最重要的性质就是：当算法用于正定二次函数时，可以在有限多次迭代后终止，得到最优解（当然要执行精确一维搜索）。

定理4.2 对于正定二次函数，共轭方向法至多经过n 步精确搜索终止；且对每个1i x +，都是()f x 在线性流形00,i j j j j x x x d αα=⎧⎫⎪⎪=+∀⎨⎬⎪⎪⎩⎭∑中的极小点。

证明：首先证明对所有的1i n ≤-，都有10T i j g d +=，0,1,,j i = （即每个迭代点处的梯度与以前的搜索方向均正交）事实上，由于目标函数是二次函数，因而有()11k k k k k k g g G x x Gd α++-=-=1）当j i <时， ()1111iTT Ti j j jk k j k j g d gd gg d +++=+=+-∑ 110iTT j j kkj k j gd dGd α+=+=+=∑2）当j i =时，由精确搜索性质知：10T i j g d +=综上所述，有 10Ti j g d += (0,1,,)j i = 。

第四章作业 部分参考答案1． 设有n 个顾客同时等待一项服务。

顾客i 需要的服务时间为n i t i ≤≤1,。

应该如何安排n 个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。

试给出你的做法的理由（证明）。

策略：对 1i t i n ≤≤进行排序，,21n i i i t t t ≤≤≤ 然后按照递增顺序依次服务12,,...,ni i i 即可。

解析：设得到服务的顾客的顺序为12,,...,n j j j ，则总等待时间为,2)1(121n n j j j j t t t n nt T +++-+=- 则在总等待时间T 中1j t 的权重最大，jn t 的权重最小。

故让所需时间少的顾客先得到服务可以减少总等待时间。

证明：设,21n i i i t t t ≤≤≤ ，下证明当按照不减顺序依次服务时，为最优策略。

记按照n i i i 21次序服务时，等待时间为T ，下证明任意互换两者的次序，T都不减。

即假设互换j i ,)(j i <两位顾客的次序，互换后等待总时间为T ~，则有.~T T ≥由于,))(())(()2)(2()1)(1(21n j i i i i i i t j t j n i t i n t n t n T +--++--++--+--=,))(())(()2)(2()1)(1(~21n i j i i i i i t j t j n i t i n t n t n T +--++--++--+--=则有.0))((~≥--=-i j i i t t i j T T同理可证其它次序，都可以由n i i i 21经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而n i i i 21为最优策略。

2． 字符h a ~出现的频率分布恰好是前8个Fibonacci 数，它们的Huffman 编码是什么？将结果推广到n 个字符的频率分布恰好是前n 个Fibonacci 数的情形。

第四章蚁群算法习题与答案1.填空题（1） _________________________ 蚁群算法的缩写是_____________ ,它模拟了自然界中_________________________ 过程而提出，可以解决_______________ 问题。

（2） __________________________________________ 蚁群算法需要一个记忆空间，称为__________________________________________ ,表示已经过的路径。

判断选择城市的主要依据有 ___________ 和_________ ，前者代表__________ 愿望, 后者代表_________ 愿望，反映了问题求解过程中经验的积累。

解释：本题考查蚁群算法的基础知识。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：（1）ACO,蚂蚁觅食，组合优化（2）禁忌列表，能见度，虚拟信息素，启发式，获知式2.考虑如下情形：分头沿着两条长度不同的路径去食物源，当到达食物源时哪条路径会以较高的概率被其选择？论证你的答案。

解释：本题考查蚁群算法中信息素的特点与作用。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：路径长度短的会以较高的概率被选择。

具体论证如下：单位时间内通过路径短的蚂蚁数量大于通过路径长的蚂蚁数量，这意味着短路径上遗留的信息素浓度比较髙，山于蚂蚁倾向于朝着信息素浓度高的方向移动, 所以到后期选择短路径的蚂蚁会越来越多。

于是，蚁群的集体行为表现出一种信息正反馈现象，即最短路径上走过的蚂蚁越多，信息素浓度也就越高，后来的蚂蚁选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息的交流寻找食物和蚁穴之间最短路径的。

3.探讨在信息素释放公式中遗忘因子的重要性。

解释：本题考查蚁群算法中信息素挥发因子的作用。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：参数Q表示信息素挥发因子，p的大小从另一个侧面反映了蚂蚁群体中个体间相互影响的强弱，它直接关系到蚁群算法的全局搜索能力及收敛速度；参数1-Q表示信息素残留因子，反映了蚂蚁个体之间相互影响的强弱。