算法复习资料

1、1、算法(Algorithm)：对特定问题求解步骤的一种描述，是指令的有限序列。2、算法的五大特性：输入：一个算法有零个或多个输入。输出：一个算法有一个或多个输出。有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的 输出。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。3、算法的描述方法自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想注意事项：避免写成自然段流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次程序设计语言优点：

2、能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数 伪代码一一算法语言伪代码(Pseudocode)：介于自然语言和程序设计语言之间的方法，它采用某一程序设 计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解使用方法：7 24、算法设计的一般过程1.理解问题2.预测所有可能的输入3.在精确解和近似解间做选择4.确定适当的数据结构5.算法设计技术6.描述算法7.跟踪算法8.分析算法的效率9.根据算法编写代码5、时间复杂性分析的关键：问题规模：输入量的多少；运行算法所需要的时间T是问题规模n的函数，记作T(n)基本语句：执

3、行次数与整个算法的执行时间成正比的语句for (i=1; i=n; i+)问题规模：nfor (j=1; j0 & ri!=k)i-；return i;算法3.1的基本语句是i0和ri!=k，其执行次数为：顼 +%c = 1 (n - i +1)+ 1 (n - i +1) = n +1 = 0(n) .1. 1 1 n . n .算法3.2改进的顺序查找int SeqSearch2(int r , int n, int k) 数组 r1 rn存放查找集合r0=k; i=n;while (ri!=k)i -;return i;算法3.2的基本语句是ri!=k，其执行次数为: TOC o 1-5

4、 h z 1 n +1，p c = ，(n -1 +1) = 0(n).n2BF C+算法i=1i=1int BF(char S , char T) i=1; j=1;while (i=S0 & j=T0 & jT0) return (i-j+1);else return 0;算法3.6选择排序void SelectSort(int r , int n) /数组下标从 1 开始for (i=1; i=n-1; i+)对n个记录进行n-1趟简单选择排序index=i;for (j=i+1; j=n; j+)/在无序区中找最小记录if (rjrindex) index=j;if (index!=i

5、) ri - rindex; /若最小记录不在最终位置则交换该算法的基本语句是内层循环体中的比较语句rjrindex，其执行次数为: 况元况，.、n(n -1) 乙乙 1 =乙(n i) = O(n2)i=1 j=i+1i=1算法3.7起泡排序void BubbleSort(int r , int n)/数组下标从 1 开始for (i=1; i=n-1; i+)for (j=1; jrj+1) rj - rj+1； /如果反序，则交换元素该算法的基本语句是内层循环体中的比较语句rjrj+1，其执行次数为：1 札札,n(n 1)、 乙乙 1 =乙(n i) = O(n 2)i=1 j=1i=1

6、算法3.8改进的起泡排序void BubbleSort(int r , int n)/数组下标从 1 开始exchange=n;/第一趟起泡排序的范围是r1到 rnwhile (exchange)仅当上一趟排序有记录交换才进行本趟排序bound=exchange; exchange=0；for (j=1; jrj+1) rj-rj+1；exchange=j；记录每一次发生记录交换的位置第四章算法4.7最大子段和问题int MaxSum(int a , int left, int right)sum=0;if (left= =right) /如果序列长度为1,直接求解if (aleft0) su

7、m=aleft;else sum=0;else center=(left+right)/2;划分leftsum=MaxSum(a, left, center);对应情况，递归求解rightsum=MaxSum(a, center+1, right);对应情况，递归求解s1=0; lefts=0;以下对应情况，先求解s1for (i=center; i=left; i-)lefts+=ai;if (leftss1) s1=lefts;s2=0; rights=0;再求解 s2for (j=center+1; js2) s2=rights;sum=s1+s2;计算情况的最大子段和if (sumle

8、ftsum) sum=leftsum;/合并，在sum、leftsum和rightsum中取较大者 if (sumrightsum) sum=rightsum;return sum;算法4.8一棋盘覆盖void ChessBoard(int tr, int tc, int dr, int dc, int size)/ tr和tc是棋盘左上角的下标，dr和dc是特殊方格的下标，/ size是棋盘的大小，t已初始化为0if (size = = 1) return; /棋盘只有一个方格且是特殊方格t+; / L型骨牌号s = size/2; /划分棋盘/覆盖左上角子棋盘if (dr tr + s &

9、 dc tc + s) /特殊方格在左上角子棋盘中ChessBoard(tr, tc, dr, dc, s);递归处理子棋盘else /用t号L型骨牌覆盖右下角，再递归处理子棋盘boardtr + s - 1tc + s - 1 = t;ChessBoard(tr, tc, tr+s-1, tc+s-1, s);/覆盖右上角子棋盘if (dr = tc + s) /特殊方格在右上角子棋盘中ChessBoard(tr, tc+s, dr, dc, s);/递归处理子棋盘else /用t号L型骨牌覆盖左下角，再递归处理子棋盘boardtr + s - 1tc + s = t;ChessBoard(

10、tr, tc+s, tr+s-1, tc+s, s); /覆盖左下角子棋盘if (dr = tr + s & dc = tr + s & dc = tc + s) /特殊方格在右下角子棋盘中ChessBoard(tr+s, tc+s, dr, dc, s);/递归处理子棋盘else /用t号L型骨牌覆盖左上角，再递归处理子棋盘boardtr + stc + s = t;ChessBoard(tr+s, tc+s, tr+s, tc+s, s); 算法4.9 环赛日程表void GameTable(int k, int a)/ n=2k(kN1)个选手参加比赛，二维数组a表示日程安排，数组下标从

11、1开始n=2;/k=0，2个选手比赛日程可直接求得/求解2个选手比赛日程，得到左上角元素a11=1; a1=2;a21=2; a22=1;for (t=1; tk; t+)迭代处理，依次处理22,2k个选手比赛日程temp=n; n=n*2;/填左下角元素fOr (i=temp+1; i=n; i+ )for (j=1; j=temp; j+)aij=ai-tempj+temp;/佐下角元素和左上角元素的对应关系/；填右上角元素for (i=1; i=temp; i+)for (j=temp+1; j=n; j+) aij=ai+temp(j+temp)% n;/填右下角元素for (i=te

12、mp+1; i=n; i+)for (j=temp+1; j=n; j+)aij=ai-tempj-temp;第五章算法5.1一半查找伪代码：low=1； high=n；设置初始查找区间测试查找区间】low，high是否存在，若不存在，则查找失败；否则取中间点mid=(low+high)/2;比较k与rmid，有以下三种情况：3.1若krmid，则low=mid+1；查找在右半区进行，转2；3.3若k=rmid，则查找成功，返回记录在表中位置mid；判定树一述折半查找的判定过程。长度为n的判定树的构造方法为：当n=0时，判定树为空；当n0时，判定树的根结点是有序表中序号为mid=(n+1)/2

13、的记录，根结点的左子树 是与有序表r1 rmid-1相对应的判定树，根结点的右子树是与rmid+1 rn 相对应的 判定树。动态规划法与分治法类似，当问题不能分解为独立的子问题,但又符合最优化原理(最优子结构性质）时，用动态规划，通过多阶段决策过程从逐步找出子问题的最优解，从而决策出问题 的结果。“分治法”与“动态规划法”都是递归思想的应用之一，是找出大问题与小的子问题之间的关系, 直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。区别在于：分治法所能解决的问题一般具有以下几个特征：1）该问题的规模缩小到一定的程度就可以容易地解决；2）该问题可以分解为若干个规模较小的相同问题，即该问题具有。3）利用该问题分解出的子问题的解可以合并为该问题的解；4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。第一条特征是绝大多数问题都可以满足的；第二条特征是应用分治法的前提，它也是大多数问题可以满足的；第三条特征是关键。第四条特征涉及到分治法的效率。动态规划的实质是分治思想和解决冗余。动态规划法是将问题实例归纳为更小的、相似的子问题，并