微微陌上矣 - 算法笔记
type: channel
link: http://www.cynthia99.link/index.php/category/Algorithm-Analysis-Design
items: 2014年第五届蓝桥杯省赛试题及详解（Java本科B组)
items: 2013年第四届蓝桥杯省赛试题及详解（Java本科B组)
items: Huffman Codes
items: Searching in Graphs : BFS and DFS
items: 十大排序算法及其分析
items: 回溯法
items: 贪心算法 -背包问题
items: 最长公共子序列

2014年第五届蓝桥杯省赛试题及详解（Java本科B组)
type: item
date: 2022-03-30T22:43:00+08:00
description: 分糖果 /** * @author Wcy * @Date 2022/3/28 17:23 */ import java.util.Arrays; import java.util.Scanner; /** 有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏： 每个小朋友都把自己的糖果分一半给左手边的孩子。 一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。 反复进行这个游戏，直到所有小朋友的糖果数都相同为止。 你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。 【格式要求】 程序首先读入一个整数N(2<N<100)，表示小朋友的人数。 接着是一行用空格分开的N个偶数（每个偶数不大于1000，不小于2） 要求程序输出一个整数，表示老师需要补发的糖果数。 例如：输入 3 2 2 4 程序应该输出： 4 资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。 注意：主类的名字必须是：Main，否则按无效代码处理。 */ public class 分糖果 { public static void main(String[] args) { int add=0; Scanner scanner = new Scanner(System.in); int people=scanner.nextInt(); int[] num=new int[people]; for(int i=0;i<people;i++) num[i]= scanner.nextInt(); while(true){ int fir=num[0]/2; for(int i=0;i<num.length-1;i++){ num[i]=num[i]/2+num[i+1]/2; } num[num.length-1]=num[num.length-1]/2+fir; //2 2 4 2 3 3 // System.out.println(Arrays.toString(num)); for(int i=0;i<num.length;i++) if(num[i]%2!=0) { add++; num[i]=num[i]+1; } // System.out.println(Arrays.toString(num)); boolean judge=true; for(int i=0;i<num.length-1;i++) if(num[i]!=num[i+1]){ judge=false; } if(judge) { System.out.println(add); break; } } } } 切面条 /** * @author Wcy * @Date 2022/3/28 15:20 */ /** * 一根高筋拉面，中间切一刀，可以得到2根面条。 * * 如果先对折1次，中间切一刀，可以得到3根面条。 * * 如果连续对折2次，中间切一刀，可以得到5根面条。 * * 那么，连续对折10次，中间切一刀，会得到多少面条呢？ * * 答案是个整数，请通过浏览器提交答案。不要填写任何多余的内容。 * */ public class 切面条 { /** * n-1:对折次数 * 解析 1=1/2+2^(n-1)*(1/2^n) * n=1时：1=1/2+1/2 * n=2时：1=1/2+1/4+1/4 * n=3时：1=1/2+1/8+1/8+1/8+1/8 * @param args */ public static void main(String[] args) { System.out.println(1+1024); } } 圆周率 /** * @author Wcy * @Date 2022/3/28 15:52 */ /** * 数学发展历史上，圆周率的计算曾有许多有趣甚至是传奇的故事。其中许多方法都涉及无穷级数。 * * 图1.png中所示，就是一种用连分数的形式表示的圆周率求法。 * * 下面的程序实现了该求解方法。实际上数列的收敛对x的初始值 并不敏感。 * * 结果打印出圆周率近似值（保留小数点后4位，并不一定与圆周率真值吻合）。 * * * 4/pai=1+x * * double x = 111; * for(int n = 10000; n>=0; n--){ * int i = 2 * n + 1; * x = 2 + (i*i / x); * } * * * * Sy…

2013年第四届蓝桥杯省赛试题及详解（Java本科B组)
type: item
date: 2022-03-19T22:03:00+08:00
description: 世纪末的星期 /** * 曾有邪教称1999年12月31日是世界末日。当然该谣言已经不攻自破。 * 还有人称今后的某个世纪末的12月31日，如果是星期一则会.... * 有趣的是，任何一个世纪末的年份的12月31日都不可能是星期一!! * 于是，“谣言制造商”又修改为星期日...... * 1999年的12月31日是星期五，请问：未来哪一个离我们最近的一个世纪末年（即xx99年）的12月31日正好是星期天（即星期日）？ * 请回答该年份（只写这个4位整数，不要写12月31等多余信息） */ public class 世纪末的星期 { public static void main(String[] args) { //从2000年开始 int i = 2000; // 0 1 2 3 4 5 6 代表七天 int index = 4; while (true) { int days = 365; if ((i%100!=0 && i%4==0) || i%400==0) days = 366; int yu = days % 7; index = (index + yu) % 7; // System.out.println(i+":"+index); if (i % 100 == 99) if ((index == 6)) { System.out.println(i); break; } i++; } } } 马虎的算式 /** * 小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。 * * 有一次，老师出的题目是：36 x 495 = ? * * 他却给抄成了：396 x 45 = ? * * 但结果却很戏剧性，他的答案竟然是对的！！ * * 因为 36 * 495 = 396 * 45 = 17820 * * 类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54 * * 假设 a b c d e 代表1~9不同的5个数字（注意是各不相同的数字，且不含0） * * 能满足形如： ab * cde = adb * ce 这样的算式一共有多少种呢？ * * 请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。 * * 满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。 * * 答案直接通过浏览器提交。 * 注意：只提交一个表示最终统计种类数的数字，不要提交解答过程或其它多余的内容。 */ public class 马虎的算式 { public static void main(String[] args) { //a>0 c>0 int total=0; for(int a=1;a<10;a++) // a for(int b=1;b<10;b++) //b if(a!=b) for(int c=1;c<10;c++) // c if((b!=c)&&(a!=c)) for(int d=1;d<10;d++) //d if((a!=d)&&(b!=d)&&(c!=d)) for(int e=1;e<10;e++) //e if((a!=e)&&(b!=e)&&(c!=e)&&(d!=e)) // ab * cde = adb * ce if((a*10+b)*(c*100+d*10+e)==(a*100+d*10+b)*(c*10+e)) total++; System.out.println(total); } } 振兴中华 /** * 小明参加了学校的趣味运动会，其中的一个项目是：跳格子。 * * 地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg） * * 从我做起振 * 我做起振兴 * 做起振兴中 * 起振兴中华 * * * 比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。 * * * 要求跳过的路线刚好构成“从我做起振兴中华”这句话。 * * 请你帮助小明算一算他一共有多少种可能的跳跃路线呢？ * * 答案是一个整数，请通过浏览器直接提交该数字。 * 注意：不要提交解答过程，或其它辅助说明类的内容。 */ //35 public class 振兴中华 { public static void main(String[] args) { int[][] dp = new int[6][6]; // 1 2 3 4 5 for(int i=1;i<=5;i++) //预处理 // 实际只用到[4][5] dp[i][1] = dp[1][i] = 1; // 2 3 4 5 即从第二位开始遍历递归 for(int i=2;i<=5;i++) for(int j=2;…

Huffman Codes
type: item
date: 2021-12-14T19:39:23+08:00
description: 先来介绍一下哈夫曼编码吧 哈夫曼树，二叉树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。哈夫曼编码则是根据字符出现频率(权重分布)，用最少的位数来表示。 (字符出现多的，用较短编码；字符出现少的，用较长编码)。 举个例子：好比这个字符串“abcddddddd”，如果用相同长度的编码来表示，4个不同数字则选用2位 (a->00,b->01,c->10,d->11)，那也就是需要 10 2 = 20长度； 而使用哈夫曼编码，则根据权重(a->010,b->011,c->00,d->1)，也就是需要:3+3+2+17 = 15长度。 在这个例子中相比平均编码则少了25%(当然这个例子比较夸张啦哈哈哈。权重分布一般不会这样，在这里主要是想说明哈夫曼编码能起到压缩编码长度的作用),但是在取哈夫曼编码的时候，要避开前缀(有可能某个数的编码刚好是另外某个数的编码前缀)，所以可以通过下面的方法计算出来。 一、基于建哈夫曼树的方法 算法过程： ①将输入的数值，每一个数值，分别都建立成一棵树(只有根节点的树)，就形成了森林。 ②将森林排序( 按权重，从大到小排序，选用插入排序即可，因为之后的排序每一次都只插入一个数值，只需要移动少量即可) ③取出后两棵树n1、n2，新创建一个根节点，然后将n1、n2作为其左右孩子，从而构成一棵新树(由新建根节点+n1(lchild)+n2(rchild)组成)，将这棵新树插入森林中。 ④重复②③，直到森林中只剩下一棵树，此时该树就是所求哈夫曼树。 ⑤遍历每一个叶子(每一个叶子就是输入数值)，根据遍历路径(往lchild则 +‘1’，往rchild 则 + ‘0’)，每一个叶子对应的数值+编码result，即是其哈夫曼编码。

Searching in Graphs : BFS and DFS
type: item
date: 2021-12-14T19:05:50+08:00
description: BFS:Breadth First Search 广度优先搜索 DFS:Depth First Search 深度优先搜索 为了搜索 DFS，我们使用堆栈，为了搜索 BFS，我们使用队列。 广度优先搜索(BFS) 广度优先搜索(BFS):广度优先搜索构建一个广度优先的树，最初只包含它的根，也就是源顶点 s。每当搜索在扫描已经发现的顶点 u 的邻接表的过程中发现一个白色顶点 v 时，顶点 v 和边(u，v)就被添加到树中。我们说 u 是广度优先树中 v 的前 身或母体。因为顶点最多被发现一次，所以它最多有一个父顶点。广度优先树中的祖先和后代关系通常是相对于根 s 定义的:如果 u 在树中从根 s 到顶点 v 的简单路径上，那么 u 是 v 的祖先，v 是 u 的后代 BFS 算法的复杂性，取决于你是如何实现算法的。如果你用邻接矩阵来实现，那么复杂度就是O(n^2).如果你是通过邻接 表实现的，那么复杂度将是O(V+E)，其中E是边的数量。 graph={ 'a':['b','c'], 'b':['a','c','d'], 'c':['a','b','d','e'], 'd':['b','c','e','f'], 'e':['c','d'], 'f':['d'] } def BFS(graph, s): queue = [] queue.append(s) seen = set() seen.add(s) while(len(queue) > 0): v = queue.pop(0) nodes = graph[v] for w in nodes: if w not in seen: queue.append(w) seen.add(w) print(v) BFS(graph, 'a') 深度优先搜索：DFS 与广度优先搜索一样，深度优先搜索在搜索过程中对顶点进行着色，以指示它们的状态。每个顶点最初都是白色的，当在搜索中发现它时，它是灰色的，当它完成时，也就是说，当它的邻接表被完全检查时，它是黑色的。这种技术保证了每个顶点恰好在一个深度优先的树中结束，因此这些树是不相交的。除了创建深度优先的森林，深度优先搜索还会为每个顶点添加时间戳。每个顶点 v 都有两个时间戳:第一个时间戳 v.d 记录了第一次发现 v 的时间(并呈灰色)，第二个时间戳 v.f 记录了搜索完成检查 v 的邻接表的时间(并使 v 变黑)。这些时间戳提供了关于图结构的重要信息，通常有助于推理深度优先搜索的行为。 graph1 = { 'A' : ['B','S'], 'B' : ['A'], 'C' : ['D','E','F','S'], 'D' : ['C'], 'E' : ['C','H'], 'F' : ['C','G'], 'G' : ['F','S'], 'H' : ['E','G'], 'S' : ['A','C','G'] } def dfs(graph, node, visited): if node not in visited: visited.append(node) for n in graph[node]: dfs(graph,n, visited) return visited visited = dfs(graph1,'A', []) print(visited)

十大排序算法及其分析
type: item
date: 2021-12-12T20:09:00+08:00
description: 堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法. 而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。 排序的好处： 1、如果只是简单的进行数字的排序，那么稳定性将毫无意义。 2、如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？） 3、如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。 4、除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。 插入排序算法(insert Sort) 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 算法描述 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下： 从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后； 重复步骤2~5。 void InsertSort(int a[], int n) { for(int i= 1; i<n; i++){ if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入 int j= i-1; int x = a[i]; //复制为哨兵，即存储待排序元素 a[i] = a[i-1]; //先后移一个元素 while(x < a[j]){ //查找在有序表的插入位置 a[j+1] = a[j]; j--; //元素后移 } a[j+1] = x; //插入到正确位置 } print(a,n,i); //打印每趟排序的结果 } } 归并排序（Merge Sord） 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定 性。那么，在短的有序序列合并的过程中，稳定是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 算法描述 把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。 //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] void Merge(ElemType *r,ElemType *rf, int i, int m, int n) { int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k){ if(r[j] < r[i]) rf[k] = r[j++]; else rf[k] = r[i++]; } while(i <= m) rf[k++] = r[i++]; while(j <= n) rf[k++] = r[j++]; print(rf,n+1); } void MergeSort(Ele…

回溯法
type: item
date: 2021-12-12T15:37:00+08:00
description: 找出问题的解集或什么解是满足约束条件的最佳解->回溯法 回溯法:搜索，或避免不必要搜索的穷举式搜索法。适用于解一些组合数相当大的问题。 在解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至任意一点时，先判断该结点是否包含问题的解。 如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 基本思想 回溯法：类似穷举的搜索尝试过程，是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”（即回退），尝试别的路径。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发搜索解空间树。 首先根结点成为活结点（自身已生成但其孩子结点没有全部生成的结点），同时也成为当前的扩展结点（正在产生孩子结点的结点）。 在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。 如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点（由根结点到该结点构成的部分解不满足约束条件，或者其子结点已经搜索完毕）。 此时应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。 回溯法以这种方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。 问题的解空间 •解向量：问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。 •解空间：所有满足约束条件的解向量组构成了问题的解空间。 •解空间树：问题的解空间一般用树形式来组织，也称为解空间树或状态空间，树中的每一个结点确定所求解问题的一个问题状态。 •例如，对于有n种可选择物品的0-1背包问题，当n=3时，其解空间是 {（0,0,0），（0,0,1），（0,1,0），（0,1,1），（1,0,0），（1,0,1），（1,1,0），（1,1,1）} 问题的解空间树 回溯法的解题步骤 根据上面0-1背包问题的例子，我们可以总结出回溯法解题的3大步骤： (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树 • 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。 • 在任何时刻，算法只保存从根结点到当前扩展结点的路径。 • 如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。 • 而显式地存储整个解空间则需要O(2^h(n))或O(h(n)!)内存空间 旅行售货员问题 下面我们用回溯法的3大解题步骤来解旅行售货员问题 •某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。 第一步，定义问题的解空间 旅行售货员问题的解空间是 • 1，2，3，4，1 • 1，2，4，3，1 • 1，3，2，4，1 • 1，3，4，2，1 • 1，4，2，3，1 • 1，4，3，2，1 第二步，确定解空间树 第三步，以深度优先搜索解空间树 回溯法的基本术语 • 活结点是指自身已生成但其孩子结点没有全部生成的结点 • 扩展结点是指正在产生孩子结点的结点 • 死结点是指由根结点到该结点构成的部分解不满足约束条件，或者其子结点已经搜索完毕 回溯法搜索解空间时，采用剪枝函数避免无效搜索，提高回溯的搜索效率: • 用约束函数在扩展结点处剪除不满足约束的子树； • 用限界函数剪去得不到问题解或最优解的子树。 • 子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。 • 排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的 解空间树称为排列树 回溯法的算法框架 非递归回溯框架(迭代回溯) int x[n]; //x存放解向量，全局变量 void Iterativebacktrack(void) //非递归框架 { int t=1; //根结点层次为1 while (t >0) //尚未回溯到头 { if(f(n,t)<=g(n,t)) //当前结点存在子结点 { for (int i=f(n,t);i<=g(n,t);i++) //用i枚举t所有可能的路径 { x[t]=h(i) //产生一个可能的解分量 h(i) if (constraint(t) && bound(t)) //x[i]满足约束条件或限界函数 { if (solution(t)) output(x); //到达叶子结点，输出一个可行解x else t++; //否则深度遍历下一层次 } } } else t…

贪心算法 -背包问题
type: item
date: 2021-12-12T15:12:45+08:00
description: 贪心算法概念 • 贪心算法总是作出在当前看来最好的选择,不从整体最优考虑，在某种意义上的局部最优选择。希望得到的最终结果也是整体最优的。 • 贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路径问题，最小生成树问题等。 • 在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素 • 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。 • 但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质 1、贪心选择性质 • 贪心选择性质：所求问题的整体最优解可通过一系列局部最优的选择，即贪心选择来达到。这是第一个基本要素，也是与动态规划算法的主要区别。 • 动态规划算法：自底向上，贪心算法：自顶向下，迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 • 对于一个具体问题，确定它是否具有贪心选择性质，须证明每一步所作的贪心选择最终导致问题的整体最优解。 2、最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? • 背包问题： 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 用贪心算法解背包问题的基本步骤： • 计算每种物品单位重量的价值Vi/Wi • 依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包 • 若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包 • 依此策略一直地进行下去，直到背包装满为止。 • 具体算法可描述如下页：

最长公共子序列
type: item
date: 2021-12-12T14:24:00+08:00
description: • 最长公共子序列（LCS）的特征： 1、序列可连续，可不连续。 2、序列讲究顺序 3、答案不一定是唯一一个（有可能多个） 例如: X={ABCBDAB} ，Y={ BDCABA } 最长公共子序列有{BCBA}，{BDAB}，{BCAB} 穷举法：求LCS • 若要求两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列，先 取得X，Y的所有子序列，并进行一一比较，共有如下不同的组合： • X共有 个不同子序列， Y共有 个不同子序列， • 共要进行不同的比较：2m+n 次 • 可见穷举法产生指数级的时间复杂度为O(2m+n )，因此，对于长序列，这种方法不可行。 最长公共子序列的结构 设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则 (1)若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。 (2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。 (3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质 子问题的递归结构 由最长公共子序列问题的最优子结构性质建立子问题最优值 的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。 其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。 故此时C[i][j]=0。由最优子结构性质可建立递归关系如下 计算最优值： 由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题， 因此，用动态规划算法自底向上地计算最优值能提高算法的效率 void LCSLength(int m，int n，char *x，char *y，int **c，int **b) { int i，j; for (i = 0; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } 【算法分析】 LCSlength算法中使用了两重循环，所以对于长度分别为m和n的序列，求其最长公共子序列的时间复杂度为O(m×n)。空间复杂度为O(m×n) 构造最长公共子序列 void LCS(int i，int j，char *x，int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1){ LCS(i-1，j-1，x，b); //沿对角线方向，记为"↖ " cout<<x[i]; } //第一个字符存放在x[1]，所以第i个字符存放在x[i]中 else if (b[i][j]== 2) LCS(i-1，j，x，b); //向上记为，记为"↑" else LCS(i，j-1，x，b); //向左记为，记为"←" } 算法的改进 •在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元 素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。 对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。 •如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))