算法导论
课程实验
正式题目二最长递增子序列
学号：SG13225146
姓名：张添程
日期：2013.11.28
目录
实验要求： (3)
实验设计与实现 (4)
方案一——使用最长公共子序列算法 (5)
算法描述 (5)
数据预处理 (6)
最长公共子序列（LCS）算法与实现 (7)
构造最长公共子序列（即最长递增子序列） (9)
方案二——改进最长公共子序列算法 (10)
算法描述 (10)
数据预处理 (11)
最长公共子序列（LCS）改进算法与实现 (12)
构造最长公共子序列（即最长递增子序列） (14)
方案三——动态规划方法计算最长递增子序列算法 (15)
算法描述 (15)
动态规划方法的设计与实现 (15)
构造最长递增子序列 (17)
方案四——改进的动态规划方法计算最长递增子序列算法 (18)
算法描述 (18)
动态规划方法的设计与实现 (19)
构造最长递增子序列 (21)
实验结果 (22)
实验总结 (26)
附录——程序源代码 (27)
最长递增子序列.cpp (27)
Link.h (29)
快速排序.cpp (29)
LCS.cpp (30)
LIS.cpp (34)
最长递增子序列
学号：SG13225146 姓名：张添程
实验要求：
随机生成小于等于n的自然数的一个序列，输出其最长递增子序列（任意一个即可）。
n 分别取1000，3000，10000。
例：n=5 随机序列为5 1 4 2 3，正确输出为1 2 3，即长度为3的递增子序列。
提示：参考LCS，思考能否达到时间复杂度（O(nlogn)）
实验报告要点：描述动态规划思想，总结时间和空间复杂度。
实验设计与实现
程序结构上使用while(1)实现无限循环，在输入n = 0时终止，在输入n >= 1且n<=N（N为定义的常量，在此应题目要求设置为10000）时分别调用4个方案实现最长递增子序列，在其他情况显示输入错误。
实验代码参照《高质量C/C++编程指南》标准格式书写。
使用实验三——常见排序算法的实现与性能比较中的随机序列生成方式生成随机序列。
首先使用srand()设置rand()的参数，调用time()，获得这个参数
使用rand()获得一个0到32767的随机数，然后使用1 + (int)(n*(rand() / (RAND_MAX + 1.0)))获得一个1到n的随机数。
通过循环获得一个随机序列a，并将a值赋值到b。
然后使用四种方案获得最长递增子序列。
至此时间复杂度为O(n)。空间复杂度为O(2n)。
方案一——使用最长公共子序列算法
算法描述
LCS的最优子结构：
令A = {a1,a2,…,a m}和B = {b1,b2,…,b n}为两个序列，C = {c1,c2,…,c k}为A和B的任意LCS。
1.如果a m = b n，则c k = a m = b n且C k-1是A m-1和B n-1的一个LCS；
2.如果a m != b n，那么c k != a m意味着C是A m-1和B的一个LCS；
3.如果a m != b n，那么c k != b n意味着C是A和B n-1的一个LCS；
可得到如下公式：
x[i][j]={
x[i?1][j?1]+1 max?{x[i][j?1],x[i?1][j]}
算法伪代码：
LCS1(a, b, m, n)
1 for i <- 0 to m
2 for j <- 0 to n
3 x[i][j] <- 0
4 y[i][j] <- 0
5 for i <- 1 to m
6 for j <- 1 to n
7 if a[i] = b [j]
8 x[i][j] = x[i-1][j-1] + 1
9 y[i][j] = 1
10 else if x[i-1][j] >= x[i][j-1]
11 x[i][j] = x[i-1][j]
12 y[i][j] = 2
13 else x[i][j] = x[i][j-1]
14 y[i][j] = 3
15 return x and y
数据预处理
首先使用实验三——常见排序算法的实现与性能比较中的快速排序对b序列进行排序。
然后扫描b序列，如果b[i]=b[i+1]则将b[i]置0。使b序列中没有大于0的重复元素。
然后在使用快速排序对b序列进行排序。得到一个前面元素为0，后面为大于0的递增的序列，且没有大于0的重复元素。
因为LCS方法结果输出时采用的是递归调用，当n > 1000时递归过多会导致栈的溢出。所以，在主函数中循环设定时当n <= 1000时才会调用方案一与方案二。
至次时间复杂度增加2次快排O(2nlgn)、1次扫描O(n)。
空间复杂度不变为O(2n)。
而a的最长递增子序列即为a与b的最长公共子序列。
最长公共子序列（LCS）算法与实现
参照教材P210上的算法，求解a与b的最长公共子序列。
因为要求的N为10000比较大，而LCS算法要维护2个大小为(N+1)2的二维数组，会导致栈溢出，所以首先要在堆中分配2个大小为(N+1)2的二维数组，并且初始化。
算法伪代码：
LCS1(a, b, m, n)
1 for i <- 0 to m
2 for j <- 0 to n
3 x[i][j] <- 0
4 y[i][j] <- 0
5 for i <- 1 to m
6 for j <- 1 to n
7 if a[i] = b [j]
8 x[i][j] = x[i-1][j-1] + 1
9 y[i][j] = 1
10 else if x[i-1][j] >= x[i][j-1]
11 x[i][j] = x[i-1][j]
12 y[i][j] = 2
13 else x[i][j] = x[i][j-1]
14 y[i][j] = 3
15 return x and y
然后使用教材P210上的算法，求解a与b的最长公共子序列。
至次时间复杂度增加O(n2)，空间复杂度增加O((N+1)2)。
构造最长公共子序列（即最长递增子序列）
参照教材P211上的算法，构造a与b的最长公共子序列。
可以使用LCS1中的表Y构造A和B的一个LCS，只需要冲y[m][n]开始，并按照1、2、3追踪即可。表Y中1表示x[i] = y[i]是LCS的一个元素。按照这种方法可以依次构造出LCS的所有元素。
伪代码：
PrintLCS1(y, a, i, j)
1 if i = 0 or j = 0
2 return
3 if x[i][j] = 1
4 PrintLCS1(y, a, i-1, j-1)
5 print a[i]
6 else if x[i][j] = 2
7 PrintLCS1(y, a, i-1, j)
8 else PrintLCS1(y, a, I, j-1)
至次时间复杂度增加O(2n)，空间复杂度不变。
总的时间复杂度为O(n2)，空间复杂度为O(2(N+1)2+2n)。
方案二——改进最长公共子序列算法
算法描述
在方案一的基础上，根据教材P211的改进思想，去掉表y。
每个表项x[i][j]仅依赖与另外三个x表项：x[i-1,j-1]、x[i-1,j]和x[i][j-1]。
给定x[i][j]的值，可以在O(1)时间内确定这三个值中的哪一个来计算x[i][j]，而不用检测y表。这样可以利用一个类似与PrintLCS的过程在O(2n)时间内即可以重构一个LCS。
LCS的最优子结构：
令A = {a1,a2,…,a m}和B = {b1,b2,…,b n}为两个序列，C = {c1,c2,…,c k}为A和B的任意LCS。
4.如果a m = b n，则c k = a m = b n且C k-1是A m-1和B n-1的一个LCS；
5.如果a m != b n，那么c k != a m意味着C是A m-1和B的一个LCS；
6.如果a m != b n，那么c k != b n意味着C是A和B n-1的一个LCS；
可得到如下公式：
x[i][j]={
x[i?1][j?1]+1 max?{x[i][j?1],x[i?1][j]}
算法伪代码：
LCS1(a, b, m, n)
1 for i <- 0 to m
2 for j <- 0 to n
3 x[i][j] <- 0
4 for i <- 1 to m
5 for j <- 1 to n
6 if a[i] = b [j]
7 x[i][j] = x[i-1][j-1] + 1
8 else if x[i-1][j] >= x[i][j-1]
9 x[i][j] = x[i-1][j]
10 else x[i][j] = x[i][j-1]
11 return x and y
数据预处理
同方案一。
首先使用实验三——常见排序算法的实现与性能比较中的快速排序对b序列进行排序。
然后扫描b序列，如果b[i]=b[i+1]则将b[i]置0。使b序列中没有大于0的重复元素。
然后在使用快速排序对b序列进行排序。得到一个前面元素为0，后面为大于0的递增的序列，且没有大于0的重复元素。
至次时间复杂度增加2次快排O(2nlgn)、1次扫描O(n)。
空间复杂度不变为O(2n)。
而a的最长递增子序列即为a与b的最长公共子序列。
最长公共子序列（LCS）改进算法与实现
参照方案一的算法，求解a与b的最长公共子序列。
因为要求的N为10000比较大，而LCS算法要维护1个大小为(N+1)2的二维数组，会导致栈溢出，所以首先要在堆中分配1个大小为(N+1)2的二维数组，并且初始化。
算法伪代码：
LCS1(a, b, m, n)
1 for i <- 0 to m
2 for j <- 0 to n
3 x[i][j] <- 0
4 for i <- 1 to m
5 for j <- 1 to n
6 if a[i] = b [j]
7 x[i][j] = x[i-1][j-1] + 1
8 else if x[i-1][j] >= x[i][j-1]
9 x[i][j] = x[i-1][j]
10 else x[i][j] = x[i][j-1]
11 return x and y
然后使用方案一上的算法，求解a与b的最长公共子序列。
至次时间复杂度增加O(n2)，空间复杂度增加O((N+1)2)。
构造最长公共子序列（即最长递增子序列）
伪代码如下：
PrintLCS2(x, a, b, i, j)
1 if a[i] = b [j]
2 PrintLCS2(x, a, b, i-1, j-1)
3 print a[i]
4 else if x[i-1][j] >= x[i][j-1]
5 PrintLCS2(x, a, b, i-1, j)
6 else PrintLCS2(x, a, b, I, j-1)
7 end if
8 end if
至次时间复杂度增加O(2n)，空间复杂度不变。
总的时间复杂度为O(n2)，空间复杂度为O((N+1)2+2n)。
方案三——动态规划方法计算最长递增子序列算法
算法描述
求解以a[i]为末元素的最长递增子序列时。
首先、找到所有序号在a[i]前面且小于a[i]的元素a[j]，即j 如果这样的元素存在，那么对于a[j],都有一个以a[j]为末元素的最长递增子序列，长度设为p[j]，把其中最大的p[j]选出来，那么p[i]就等于最大的p[j]加1，即以a[i]为末元素的最长递增子序列，等于以使p[j]最大的那个a[j]为末元素的递增子序列最末再加上a[i]； 如果这样的元素不存在，那么a[i]自身构成一个长度为1的以a[i]为末元素的递增子序列。 动态规划方法的设计与实现 动态规划算法伪代码如下： LIS1(a, n) 1 for i <- 2 to n 2 p[i] <- 1 3 q[i] <- 0 4 for j <- 1 to n 5 if a[j] < a[i] 且 p[j] > p[i] – 1 6 p[i] <- p[j] + 1 7 q[i] <- i 8 end if 9 end for 10 if p[i] = 1 11 q[i] = i 12 end if 13 end for 14 for i <- 1 to n 15 if k < p[i] 16 k <- p[i] 17 l <- i 18 end if 19 end for 其中p[i]为以a[i]为末元素的最长递增子序列长度，q[i] 为以a[i]为末元素的最长递增子序列的a[i]前面一个点a[j]的序号，k为序列中最长公共子序列的长度，l为序列中最长公共子序列末元素位置。 代码如下 因为对于i每次都需要扫描钱i-1个元素，共扫描n-1次，所以时间复杂度为O(n2)。 至次时间复杂度增加O(n2)，空间复杂度增加O(2n)。 构造最长递增子序列 由于有p[i]为以a[i]为末元素的最长递增子序列长度，q[i] 为以a[i]为末元素的最长递增子序列的a[i]前面一个点a[j]的序号，k为序列中最长公共子序列的长度，l为序列中最长公共子序列末元素位置。 我们可以根据k与l确定最长公共子序列长度和末元素，根据q[i]的一次到最长公共子序列的前一个元素，直到p[i]为1时即构造出最长递增子序列。 构造最长递增子序列的伪代码： PrintLIS1(a, p, q, i) 1 if p[i] = 1 2 print a[i] 3 else 4 print a[i] 5 PrintLIS1(a, p, q, q[i]) 代码如下： 共递归k次，每次O(1),所以时间复杂度为O(n)。 至次时间复杂度增加O(n)，空间复杂度不变。 总的时间复杂度为O(n2)，空间复杂度为O(3n)。 方案四——改进的动态规划方法计算最长递增子序列算法 算法描述 首先看下方案三的算法描述。 求解以a[i]为末元素的最长递增子序列时。 首先、找到所有序号在a[i]前面且小于a[i]的元素a[j]，即j 如果这样的元素存在，那么对于a[j],都有一个以a[j]为末元素的最长递增子序列，长度设为p[j]，把其中最大的p[j]选出来，那么p[i]就等于最大的p[j]加1，即以a[i]为末元素的最长递增子序列，等于以使p[j]最大的那个a[j]为末元素的递增子序列最末再加上a[i]； 如果这样的元素不存在，那么a[i]自身构成一个长度为1的以a[i]为末元素的递增子序列。 在方案三的这个算法中“首先、找到所有序号在a[i]前面且小于a[i]的元素a[j]，即j 循环次数无法改变的情况下，可以考虑改进扫描算法。因为a[i]值的无序性我难以更改，这就需要寻找一个标准在不增加额外操作的情况下对a[i]排序的方法。我对a[i]前的序列a[1]到a[i-1]看作一个排好序的序列F，F的小标为a[1]到a[i-1]的值，每次循环查询a[1]到a[i-1]时，把他看作是查询F，F是按照A的值排序的，对F使用二分查找，可以使得每次查询的代价在O(lgi)，使得总的时间复杂度为O(nlgn)。 虽然，此种方法可以解决求解LIS问题的时间，但是这使得方案三中的p[i]为以a[i]为末元素的最长递增子序列长度，q[i] 为以a[i]为末元素的最长递增子序列的a[i]前面一个点a[j]的序号，k为序列中最长公共子序列的长度，l 为序列中最长公共子序列末元素位置，中的q[i]无法得出，使得标准的迭代输出最长递增子序列的方式无法实现，这就需要另一种方案来实现构造最长递增子序列，且他的时间复杂度不可以超过O(nlgn)。 经过了一段时间的思考与论证，PrintLCS2新鲜出炉，使用的方式是依次扫描p中元素，在遇到第一个p[j] = p[i] -1的序列停下，继续下一次迭代。表面上看是一个2重循环，时间复杂度为O(n2)，但是实际上只执行了n次判断，因为对于内层循环，只找到第一个符合条件的就停止，对于外层循环的下一次扫描是从这次扫描结束的位置开始的，所以就只执行了n次，时间复杂度为O(n)。 动态规划方法的设计与实现 改进的动态规划的算法的伪代码如下： LIS2(a, n) 1 f[0] <- 0 2 f[1] <- a[0] 3 p[0] <- 0 4 for I <- 1 to n-1 5 r <- 0 6 s <- k 7 while r <= s 8 m <- (r + s) / 2 9 if f[m] < a[i] 10 r <- m + 1 11 else s <- m – 1 12 end if 13 f[r] <- a[i] 14 p[i] <- r 15 if r > k 16 k <- k + 1 17 l <- i 18 f[r] <- a[i] 19 return p 其中p[i]为以a[i]为末元素的最长递增子序列长度，k为序列中最长公共子序列的长度，l为序列中最长公共子序列末元素位置。 代码如下： 至此时间复杂度增加O(nlgn)，空间复杂度增加O(n) 算法作业： LCS 问 题 作业要求：设计一个算法求出两个序列的所有LCS ，分析最坏情况，用“会计方法”证明利用b[i][j]求出 所有LCS 的算法在最坏情况下时间复杂度为)(m m n C O + 1、 算法思路： 根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构性质，采用动态规划法求解问题。设X={x 1, x 2, … , x n }, Y={y 1, y 2, … , y m }, 首先引入二维数组C[i][j]记录X i 和Y j 的LCS 的长度，定义C[i][j]如下： { j i j y i 且x ,i,j ]][j C[i j y i x j i j i C j i C j i C 00001110,]},1][[],][1[max{]][[===>+--≠>--=或，且 为了构造出LCS ，还需要使用一个二维数组b[m][n]，b[i][j]记录C[i][j]是通过哪个子问题的值求得 的，以决定搜索的方向，欲求出所有的LCS ，定义数组b 如下： 设1-对角线方向;2-向上;3-向左;4-向上或向左 若X[i]=Y[j],b[i][j] = 1, 若C[i-1][j] 《面向对象编程技术》试卷 注：1）请将答案写在答题纸上，写在试卷上不算分。答题纸在试卷的最后页。 2）交卷时,试卷和答题纸一起交。 一、单选题 (每小题1.5分，共30分) 1. C++中，以下有关构造函数的叙述不正确的是 ______ 。 A. 构造函数名必须和类名一致 B. 构造函数在定义对象时自动执行 C. 构造函数无任何函数类型 D. 在一个类中构造函数有且仅有一个 2．以下叙述不正确的是 ______ 。 A. 在类的定义中，通常是成员变量描述对象的属性；用成员函数描述对象的行为 B. 类的一个成员只能具有一种访问控制属性 C. 构造函数和析构函数是特殊的成员函数，因此不允许重载 D. 通过对象只能访问类的公有成员 3. 以下关于虚函数的叙述不正确的是 ______ 。 A. 虚函数属于成员函数 B. 虚函数不允许说明成静态的 C. 凡是虚函数必须用virtual说明 D. 虚函数可以被继承 4. cout是I0流库预定义的______ 。 A．类 B. 对象 C. 包含文件 D. 常量 5．面向对象程序设计中的数据隐藏指的是______ 。 A．输入数据必须输入保密口令 B．数据经过加密处理 C. 对象内部数据结构上建有防火墙D．对象内部数据结构的不可访问性6．拷贝（复制）构造函数的作用是______ 。 A．进行数据类型的转换 B．用对象调用成员函数 C．用对象初始化对象D．用一般类型的数据初始化对象 7. 下列不是描述类的成员函数的是______ 。 A.构造函数 B.析构函数 C.友元函数 D.拷贝构造函数 8. 如果类A被说明成类B的友元，则______ 。 A. 类A的成员即类B的成员 B. 类B的成员即类A的成员 C. 类A的成员函数不得访问类B的成员 D. 类B不一定是类A的友元 9. 对于任何一个类，析构函数最多有______ 个。 A. 0 B. 1 C. 2 D. n 10. 下列特性中，C与C++共有的是______ 。 A.继承 B.封装 C.多态性 D.函数定义不能嵌套 11. 在公有继承的情况下，基类公有和保护成员在派生类中的访问权限______ 。 A. 受限制 B. 保持不变 C. 受保护 D. 不受保护 12. 通过______ 调用虚函数时，采用动态束定。 A. 对象指针 B. 对象名 C. 成员名限定 D. 派生类名 13. C++ 类体系中，不能被派生类继承的有______ 。 A. 成员转换函数 B. 构造函数 C. 虚函数 D. 静态成员函数 14. 假定 ab 为一个类，则执行 ab x；语句时将自动调用该类的______ 。 A. 有参构造函数 B. 无参构造函数 C. 拷贝构造函数 D. 赋值构造函数 15. 静态成员函数不能说明为______ 。 A. 整型函数 B. 浮点函数 C. 虚函数 D. 字符型函数 16. 在 C++ 中，数据封装要解决的问题是______ 。 A. 数据规范化排列 B. 数据高速转换 C. 避免数据丢失 D. 保证数据完整性 一、概念题： （1）排序算法时间复杂度： 排序算法最好最坏平均 插入O(n)O(n2)O(n2) 归并O(nlogn)O(nlogn)O(nlogn) 快排O(nlogn)O(n2)O(nlogn)排序算法空间复杂度： 1、所有简单排序和堆排序都是0(1) 2、快速排序为0(logn)，要为递归程序执行过程栈所需的辅助空间 3、归并排序和基数排序所需辅助空间最多，为O(n) （2）渐近记号 1、渐近确界：Θ(g(n))={f(n):存在正常数c1和c2和n0，使对所有的n>= n0，都有0<=c1g(n)<=f(n)<=c2g(n)}。大Θ记号给出函数的渐进确界。 2、渐近下界：Ω(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=cg(n)<=f(n)}。大Ω记号给出函数的渐进下界。 3、渐近上界：O(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=f(n)<=cg(n)}。大O记号给出函数的渐进上界。 （3）二叉查找树： 执行基本操作的时间与树的高度成正比。搜索、插入、删除的复杂度等于树高，期望O(lgn)，最坏O(n)（数列有序，树退化成线性表） （4）红黑树： 1、时间复杂度： 基本动态集合操作：O(log n)，n是树中元素的数目。 2、性质： 1)节点是红色或黑色。 2)根节点是黑色。 3)每个叶节点（NIL节点）是黑色的。 4)如果一个结点是红的，则它的两个儿子都是黑的（不能有两个连续 红结点） 5)从任一节点到其子孙结点的所有路径都包含相同数目的黑色节点。 3、相关概念，定理： 1）黑高度：从某个结点出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度，bh(x)。红黑树的黑高度定义为其根节点的黑高度。 2）一颗有n个内结点的红黑树的高度至多为2lg(n+1)。(用2-3-4树理解) 3）在一颗黑高度为K的红黑树中，总结点数最多有22k+1-1，此时内结点 一、给定关系 R(A,B) 和 S(B,C) ，将下面的关系代数表达式转换为相应的SQL语句： π (attribute-list) [ (condition) [ R ? S ] ] 二、Megatron 747 磁盘具有以下特性： 1）有8个盘面和8192个柱面 2）盘面直径为英寸，内圈直径为英寸 3）每磁道平均有256个扇区，每个扇区512字节 4）每个磁道10％被用于间隙 5）磁盘转速为 7200 RPM 6）磁头启动到停止需要1ms，每移动500个柱面另加1ms 回答下列有关Megatron 747的问题（要求写出式子并且计算出结果，精确到小数点后两位）： 1）磁盘容量是多少GB 2）如果一个块是8KB，那么一个块的传输时间是多少ms 3）平均寻道时间是多少ms 4）平均旋转等待时间是多少ms 三、下面是一个数据库系统开始运行后的undo/redo日志记录，该数据库系统支持simple checkpoint （1）（2）（3） 1) 河北地质大学课程设计报告 (学院)系: 信息工程学院 专业: 计算机科学与技术 姓名: 李义 班级: 二班 学号: 515109030227 指导教师: 王培崇 2016年11月26 日 算法课程设计报告 姓名李义学号515109030227 日期2016/11/10-2016/12/1 实验室152 指导教师王培崇设备编号08 设计题目求最长公共子序列 一、设计内容 求最长公共子序列，如输入字符串str1=adadsda，str2=sadasfda。 则求出的最长公共子序列是adasda。 二、设计目的 掌握动态规划思想，对使用求最长公共子序列加深理解。 三、设计过程 1.算法设计 1. for i ←0 to n 2. L[i,0] ←0 3. end for 4. for j ←0 to m 5. L[0,j] ←0 6. end for 7. for i ←1 to n 8. for j ←1 to m 9. if ai=bj then L[i,j]←L[i-1,j-1]+1 10. else L[i,j]←max {L[i,j-1], L[i-1,j] } 11. end if 12. end for 13. end for 14. return L[n,m] 2.流程图 开始结束 输入I=0，j=0 i<=n L[I,0]=0 i++ Y L[0,j]=0 N j<=n j++ Y i=1 to n J=1 to m ai=bj L[i,j]=L[i-1,j-1]+1 L[i,j]=max{L[i-1,j ],L[i,j-1]} Y J++i++ N 图1.Lcs 算法 3.数据结构 str1=adadsda str2=sadasfda 四、程序实现及运行结果 动态规划解最长公共子序列问题 动态规划主要针对最优化问题,它的决策是全面考虑不同的情况分别进行决策,,最后通过多阶段决策逐步找出问题的最终解.当各个阶段采取决策后,会不断决策出新的数据,直到找到最优解.每次决策依赖于当前状态,又随机引起状态的转移.一个决策序列就是在变化的状态中产生出来的,故有”动态”的含义.所以,这种多阶段最优化决策解决问题的过程称为动态规划. 一问题的描述与分析 字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干字符(可能一个也不去掉)后形成的字符序列..令给定的字符序列X=”x0,x1,x2,…xm-1”,序列Y=”y0,y1,…yk-1”是X的子序列，存在X的一个严格递增下标序列i=i0,i1,i2,…ik-1,使得对所有的j=0,1,2,…k-1,有xi=yi。例如X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。 给定两个序列A和B,称序列Z是A和B公共子序列，是指Z同是A和B的子序列。求最长公共子序列。 若A的长度为m,B的长度为n,则A的子序列有2*m-1个，B的子序列有2*n-1个。采用枚举法分别对A和B的所以子序列一一检查，最终求出最长公共子序列。如此比较次数（2*2n）接近指数阶，当n较大时，算法太耗时，不可取。所以要全面考虑不同的情况分别进行决策,,最后通过多阶段决策逐步找出问题的最终解.当各个阶段采取决策后,会不断决策出新的数据,直到找到最优解。 二、算法设计（或算法步骤） A=”a0,a1,a2,……am-1”,B=”b0,b1,b2,……bn-1”,且Z=”z0,z1,z2……zk-1”,为她们的最长公共子序列。不难证明有一下结论： （1）如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,z2,……zk-2”是“a0,a1,a2,…… am-2”和“b0,b1,b2,……bn-2”的一个最长公共子序列； （2）如果am-1!=bn-1,则若zk-1!=am-1,则“z0,z1,z2,……zk-1”是“a0,a1,a2,…… am-2”和”b0,b1,b2,……bn-1”的一个最长公共子序列。 （3）如果am-1!=bn-1,则若zk-1!=bn-1,则“z0,z1,z2,……zk-1”是“a0,a1,a2,…… am-1”和“b0,b1,b2,……bn-2”的一个最长公共子序列。 如此找到了原问题与其子问题的递归关系。 基本存储结构是存储两个字符串及其最长公共子序列的3个一位数组。当然要找出最长公共子序列，要存储当前最长公共子序列的长度和当前公共子序列的长度，而若只存储当前信息，最后只能求解最长公共子序列的长度，却不能找到最长公共子序列本身。因此需建立一个（n+1）*(m+1)的二维数组c,c[i][j]存储序列“a0,a1,a2……ai-2”和“b0,b1,……bj-1”的最长公共子序列长度，由上递推关系分析，计算c[i][j]可递归的表述如下： (1)c[i][j]=0 如果i=0或j=0; 1.ipv4 的替代方案； 2.单链表原地逆向转置； 3.折半查找算法 4.简述操作系统中系统调用过程； 5.在数据库中什么是关系，它和普通二维表啥区别； 6.什么是原子操作； 7.路由协议有哪些； 8.进程的三种状态，以及之间转换的过程； 9.快速排序的基本过程； 10.什么叫视图？视图在数据库的第几层； 11.二叉树的搜索； 12.什么叫冲突？解决冲突的办法都有哪些； 13.java 与 C++区别； 14.深度、广度搜索的过程； 15.迪杰斯克拉算法的过程； 16.关系模式和关系； 17.数据链路停发协议，就是流量控制； 18.虚拟存储器及相关算法；段存储器； 19.进程线程树图； 20.传输等待协议； 21.堆栈排序及其与快速排序的不同； 22.386 的保护模式是什么； 23.页表； 24.ER图； 25.关系范式 26.链表查询某个元素，平均时间复杂度是多少； 27.路由协议有哪些； 28.网络服务质量包括哪些方面； 29.并发控制是为了保证事务的？； 30.什么是 DMA； 31.两个时钟不同步的设备怎么通信； 32.操作系统的调度算法有哪些； 33.单链表的原地逆置算法 34.数据库的两级模式以及它们的关系和作用（貌似是这样） 35.操作系统的进程调度算法有哪些，并介绍其中两种 36.计算机的一条指令有几个机器周期，为什么 37.原子操作， pv 操作的要点和注意事项 38.内核、芯片（记不清了） 39.DMA控制器的组成和工作原理 40.简述最短路径的迪杰斯特拉算法 41.什么是 P 操作与 V 操作。 42.一个深度为 N的满二叉树有多少个结点。 43.实现一个队列的方法 44.折半查找调节与时间复杂度 2.3最长公共子序列问题 和前面讲的有所区别，这个问题的不涉及走向。很经典的动态规划问题。 例题16 最长公共子序列 (lcs.pas/c/cpp) 【问题描述】 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列< i1, i2,…, ik>，使得对于所有j=1,2,…,k有Xij=Zj 例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X 和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。 给定两个序列X= < x1, x2, …, xm>和Y= < y1, y2, … , yn>，要求找出X和Y的一个最长公共子序列。 【输入文件】 输入文件共有两行，每行为一个由大写字母构成的长度不超过200的字符串，表示序列X和Y。 【输出文件】 输出文件第一行为一个非负整数，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出文件仅有一行输出一个整数0，否则在输出文件的第二行输出所求得的最长公共子序列(也用一个大写字母组成的字符串表示。 【输入样例】 ABCBDAB BDCBA 【输出样例】 4 BCBA 【问题分析】 这个问题也是相当经典的。。 这个题目的阶段很不明显，所以初看这个题目没什么头绪，不像前面讲的有很明显的上一步，上一层之类的东西，只是两个字符串而且互相没什么关联。 但仔细分析发现还是有入手点的： 既然说是动态规划，那我们首先要考虑的就是怎么划分子问题，一般对于前面讲到的街道问题和数塔问题涉及走向的，考虑子问题时当然是想上一步是什么？但这个问题没有涉及走向，也没有所谓的上一步，该怎么办呢？ 既然是求公共子序列，也就有第一个序列的第i个字符和第二个序列的第j个字符相等的情况。 那么我们枚第一个序列（X）的字符，和第二个序列（Y）的字符。 显然如果X[i]=Y[j]那么起点是1（下面说的子序列都是起点为1的），长度为i的子序列和长度为j的子序列的最长公共子序列就是长度为i-1和长度为j-1 的子序列中最长的公共子 中科大考博辅导班：2019中科大软件学院考博难度解析及经验分享中国科学院大学2019年博士研究生招生统一实行网上报名。报考者须符合《中国科学院大学2019年招收攻读博士学位研究生简章》规定的报考条件。考生在报考前请联系所报考的研究所(指招收博士生的中科院各研究院、所、中心、园、台、站)或校部相关院系，了解具体的报考规定。 下面是启道考博辅导班整理的关于中国科学技术大学软件学院考博相关内容。 一、院系简介 中国科学技术大学是中国科学院直属的唯一院校，是一所以前沿科学和高新技术为主、科技人文与科技管理兼备的综合性全国名校，为国家教育重点建设的9所世界知名高水平研究型大学之一，在国际上享有较高的声誉。学校力争在2018年建校60周年前后，把学校建设成为“规模适度、质量优异、结构合理、特色鲜明”的世界知名的高水平研究型大学。目前，校本部共有10个学院、25个系和少年班，43个本科专业；一级学科博士学位授权点17个，国家重点学科19个，二级学科博士学位授权点89个，二级学科硕士学位授权点105个，有工商管理（MBA）、公共管理（MPA）和工程硕士3个专业硕士学位授权点；17个博士后流动站，45个博士后流动站专业，具备培养学士、硕士、博士的完整教育体系。其严谨务实的学风、创新探索的精神、高水平级的成果、国际化办学的追求，都使得这所年轻的研究型大学受到国际社会越来越强的关注 二、招生信息 中国科学技术大学软件学院博士招生专业有1个： 085271电子与信息 研究方向：不区分研究方向 三、报考条件 （1）中华人民共和国公民；拥护中国共产党的领导，愿意为祖国社会主义现代化建设服务；品德良好，遵纪守法，学风端正，无任何考试作弊、学术剽窃及其它违法违纪行为； （2）身体健康状况符合我校规定的体检要求，心理正常； （3）申请者原则上应来自国内重点院校或所在高校学习专业为重点学科； （4）专业基础好、科研能力强，在某一领域或某些方面有特殊学术专长及突出学术成果； （5）对学术研究有浓厚的兴趣，有较强的创新意识、创新能力和专业能力； 实验三最长公共子序列问题 1.实验环境 本实验采用 java 语言编写实现，环境：，编译器： eclipse 2.实验目的 通过最长公共子序列问题，巩固并详细分析动态规划思想和解题 步骤。 3.设计思路 最长公共子序列的定义为：设有两个序列S[1..m]和9[仁n],需要寻找它们之间的一个最长公共子序列。 例如,假定有两个序列： S1： I N T H E B E G I N N I N G S2： A L L T H I N G S A R E L O S T 则S i和S的一个最长公共子序列为 THING又比如： S1： A B C B D A B S2： B D C A B A 则它们的一个最长公共子序列为 BCBA。 这里需要注意的是,一个子序列不一定必须是连续的,即中间可被其他字符分开,单它们的顺序必须是正确的。另外,最长公共子序列不一定只有一个,而我们需要寻找的是其中一个。 当然，如果要求子序列里面的元素必须连成一片也是可以的。实际上，连成一片的版本比这里实现的更容易。 4.过程 我们可以通过蛮力策略解决这个问题，步骤如下： 1.检查S1[1..m]里面每一个子序列。 2.看看其是否也是S2[1..n]里的子序列。 3.在每一步记录当前找到的子序列里面最长的子序列。 这种方法的效率十分低下。因此本实验采用动态规划的方法实现该算法。 利用动态规划寻找最长公共子序列步骤如下： 1.寻找最长公共子序列的长度。 2.扩展寻找长度的算法来获取最长公共子序列。 策略：考虑序列S1和S2的前缀序列。 设 c[i，j] = |LCS (S1[1..i],S2[1..j])，则有 c[m, n] = |LCS(S1 S2)| 所以有 c[ i -1 , j -1 ] + 1, 如要 S1[i] = S2[j] c[i, j]= max{ c [ i - 1, j ], c[ i , j -1 ] }, 如果 S1[i]工S2[j] 然后回溯输出最长公共子序列过程: 最长公共子序列问题 一．实验目的： 1.加深对最长公共子序列问题算法的理解，实现最长公共子序列问题的求解算法； 2.通过本次试验掌握将算法转换为上机操作； 3.加深对动态规划思想的理解，并利用其解决生活中的问题。 二．实验内容： 1.编写算法：实现两个字符串的最长公共子序列的求解； 2.将输入与输出数据保存在文件之中，包括运行时间和运行结果； 3.对实验结果进行分析。 三．实验操作： 1.最长公共子序列求解： 将两个字符串放到两个字符型数组中，characterString1和characterString2，当characterString1[m]= characterString2[m]时，找出这两个字符串m之前的最长公共子序列，然后在其尾部加上characterString1[m]，即可得到最长公共子序列。当characterString1[m] ≠characterString2[m]时，需要解决两个子问题：即找出characterString1(m-1)和characterString2的一个最长公共子序列及characterString1和characterString2(m-1)的一个最长公共子序列，这两个公共子序列中较长者即为characterString1和characterString2的一个最长公共子序列。 2.动态规划算法的思想求解： 动态规划算法是自底向上的计算最优值。 计算最长公共子序列长度的动态规划算法LCS-Length以characterString1和characterString2作为输入，输出两个数组result和judge1，其中result存储最长公共子序列的长度，judge1记录指示result的值是由那个子问题解答得到的，最后将最终的最长公共子序列的长度记录到result中。 以LCS-Length计算得到的数组judge1可用于快速构造序列最长公共子序列。首先从judge1的最后开始，对judge1进行配对。当遇到“↖”时，表示最长公共子序列是由characterString1(i-1)和characterString2(j-1)的最长公共子序列在尾部加上characterString1(i)得到的子序列；当遇到“↑”时，表示最长公共子序列和characterString1(i-1)与characterString2(j)的最长公共子序列相同；当遇到“←”时，表示最长公共子序列和characterString1(i)与characterString2(j-1)的最长公共子序列相同。 如图所示： 第一次实验报告 1、实验任务 根据下面的需求描述，使用Sybase Power Designer设计相应的数据库概念模型，并转换成Oracle或MS SQL Server上的物理数据库结构： 某银行准备开发一个银行业务管理系统，通过调查，得到以下的主要需求： 银行有多个支行。各个支行位于某个城市，每个支行有唯一的名字。银行要监控每个支行的资产。银行的客户通过其身份证号来标识。银行存储每个客户的姓名及其居住的街道和城市。客户可以有帐户，并且可以贷款。客户可能和某个银行员工发生联系，该员工是此客户的贷款负责人或银行帐户负责人。银行员工也通过身份证号来标识。员工分为部门经理和普通员工，每个部门经理都负责领导其所在部门的员工，并且每个员工只允许在一个部门内工作。每个支行的管理机构存储每个员工的姓名、电话号码、家庭地址及其经理的身份证号。银行还需知道每个员工开始工作的日期，由此日期可以推知员工的雇佣期。银行提供两类帐户——储蓄帐户和支票帐户。帐户可以由2个或2个以上客户所共有，一个客户也可有两个或两个以上的帐户。每个帐户被赋以唯一的帐户号。银行记录每个帐户的余额、开户的支行以及每个帐户所有者访问该帐户的最近日期。另外，每个储蓄帐户有其利率，且每个支票帐户有其透支额。每笔贷款由某个分支机构发放，能被一个或多个客户所共有。每笔贷款用唯一的贷款号标识。银行需要知道每笔贷款所贷金额以及逐次支付的情况（银行将贷款分几次付给客户）。虽然贷款号不能唯一标识银行所有为贷款所付的款项，但可以唯一标识为某贷款所付的款项。对每次的付款需要记录日期和金额。 2、实验过程 （1）确定实体和属性 由上面的需求描述我们可以很容易得出以下几个实体: ●员工（身份证号，姓名，电话号码，家庭地址，开始工作日 期） ●存储账户（账户号，余额，利率） ●支票账户（账户号，余额，透支额） ●客户（身份证号，姓名，街道，城市） ●支行（支行名称，城市，资产） ●贷款（贷款号，总额） ●支付（日期，金额） 图1 PS: 1、在此ER图中我没有设计账户类，然后派生出存储账户和支票账户，因为在客户的需求中，只有两种账户类型，除了支票账户类型就是存储账户类型，没有所谓的“一般的账户”，所以就不 Chapter21 Michelle Bodnar,Andrew Lohr April12,2016 Exercise21.1-1 EdgeP rocessed initial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j} (g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j} (b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j} (a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j} (i,j){a,h}{b,d,i,g,j}{c}{e}{f,k} (d,k){a,h}{b,d,i,g,j,f,k}{c}{e} (b,j){a,h}{b,d,i,g,j,f,k}{c}{e} (d,f){a,h}{b,d,i,g,j,f,k}{c}{e} (g,j){a,h}{b,d,i,g,j,f,k}{c}{e} (a,e){a,h,e}{b,d,i,g,j,f,k}{c} So,the connected that we are left with are{a,h,e},{b,d,i,g,j,f,k}, and{c}. Exercise21.1-2 First suppose that two vertices are in the same connected component.Then there exists a path of edges connecting them.If two vertices are connected by a single edge,then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed,so all vertices on the path will be in the same set,including the endpoints.Now suppose two vertices u and v wind up in the same set.Since every vertex starts o?in its own set,some sequence of edges in G must have resulted in eventually combining the sets containing u and v.From among these,there must be a path of edges from u to v,implying that u and v are in the same connected component. Exercise21.1-3 Find set is called twice on line4,this is run once per edge in the graph,so, we have that?nd set is run2|E|times.Since we start with|V|sets,at the end 1 公共子序列问题徐康123183 一．算法设计 假设有两个序列X和Y，假设X和Y分别有m和n个元素，则建立一个二维数组C[(m+1)*(n+1)]，记录X i与Y j的LCS的长度。将C[i,j]分为三种情况： 若i =0 或j =0时，C[i,j]=0； 若i,j>0且X[i]=Y[j]，C[i,j]=C[i-1,j-1]+1； 若i,j>0且X[i] Y[j],C[i,j]=max{C[i-1,j],C[i,j-1]}。 再使用一个m*n的二维数组b，b[i,j]记录C[i,j]的来向: 若X[i]=Y[j]，则B[i,j]中记入“↖”，记此时b[i,j] = 1； 若X[i] Y[j]且C[i-1,j] > C[i,j-1]，则b[i,j]中记入“↑”，记此时B[i,j] = 2； 若X[i] Y[j]且C[i-1,j] < C[i,j-1]，则b[i,j]中记入“←”，记此时B[i,j] = 3； 若X[i]Y[j]且C[i-1,j] = C[i,j-1]，则b[i,j]中记入“↑”或“←”，记此时B[i,j] = 4； 得到了两个数组C[]和B[]，设计递归输出LCS(X,Y)的算法： LCS_Output(Direction[][], X[], i, j, len,LCS[]){ If i=0 or j=0 将LCS[]保存至集合LCS_SET中 then return; If b[i,j]=1 then /*X[i]=Y[j]*/ {LCS_Output(b,X,i-1,j-1)； 将X[i]保存至LCS[len-i]；} else if b[i,j]=2 then /*X[i]Y[j]且C[i-1,j]>C[i,j-1]*/ LCS_Output(b,X,i-1,j) else if b[i,j]=3 then /*X[i]Y[j]且C[i-1,j] Chapter6 Michelle Bodnar,Andrew Lohr December31,2016 Exercise6.1-1 At least2h and at most2h+1?1.Can be seen because a complete binary tree of depth h?1hasΣh?1 i=02i=2h?1elements,and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive. Exercise6.1-2 Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these k leaves,which must have length m.It is clear from the way we de?ned m that m= lg n . Exercise6.1-3 If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtree Exercise6.1-4 The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5 Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1 动态规划 一、问题描述 用动态规划法求两个字符串A=‘xzyzzyx’和B=‘zxyyzxz’的最长公共子序列 二、算法分析 (1)、若xm=yn,则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共自序列； (2)、若xm≠yn,且zk≠xm，则Zk是Xm-1和Yn的最长公共自序列； (3)、若xm≠yn,且zk≠yn，则Zk是Xm和Yn-1的最长公共自序列；设L(m,n)表示序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列的长度 L表示已经决策的长度 S表示每个决策的状态 L(0,0)=L(0,j)=0 1≤i≤m, 1≤j≤n L(i-1,j-1)+1 xi=yi,i≥1,j≥1 L(i,j)= max{L(i,j-1),(L(i-1,j)} xi≠yi,i≥1,j≥1 1 xi=yi S(i,j)= 2 xi≠yi 且L(i,j-1)≥L(i-1,j) 3 xi≠yi 且L(i,j-1)< L(i-1,j) 长度矩阵L 三、源代码 #include int arr[50][50] ={{0,0}}; int i = 0; int j = 0; for(i = 1; i <= x_len; i++) { for(j = 1; j <= y_len; j++) { if(str1[i - 1] == str2[j - 1]) { arr[i][j] = arr[i - 1][j - 1] + 1; } else if(arr[i][j - 1] >= arr[i - 1][j]) arr[i][j] = arr[i][j - 1]; else arr[i][j] = arr[i -1][j]; } } for(i = 0 ; i <= x_len; i++) { Chapter7 Michelle Bodnar,Andrew Lohr April12,2016 Exercise7.1-1 13199512874212611 13199512874212611 13199512874212611 91913512874212611 95131912874212611 95131912874212611 95819121374212611 95871213194212611 95874131912212611 95874131912212611 95874219122113611 95874261221131911 95874261121131912 Exercise7.1-2 If all elements in the array have the same value,PARTITION returns r.To make PARTITION return q= (p+r)/2 when all elements have the same value,modify line4of the algorithm to say this:if A[j]≤x and j(mod2)= (p+1)(mod2).This causes the algorithm to treat half of the instances of the same value to count as less than,and the other half to count as greater than. Exercise7.1-3 The for loop makes exactly r?p iterations,each of which takes at most constant time.The part outside the for loop takes at most constant time.Since r?p is the size of the subarray,PARTITION takes at most time proportional to the size of the subarray it is called on. Exercise7.1-4 To modify QUICKSORT to run in non-increasing order we need only modify line4of PARTITION,changing≤to≥. 1最长公共子序列问题(最)
中科大软件学院C+考试试卷
中科大软件学院算法复习概念综合题
中科大软院数据库考试题
最长公共子序列实验报告
动态规划解最长公共子序列问题
(完整版)中科大软院常见复试题目.doc
最长公共子序列问题
中科大考博辅导班：2019中科大软件学院考博难度解析及经验分享
最长公共子序列问题
最长公共子序列实验报告
中科大软院金老师的数据库实验一
算法导论 第三版 第21章 答案 英
动态规划法求解最长公共子序列(含Java代码)
算法导论 第三版 第六章 答案 英
最长公共子序列
算法导论 第三版 第七章 答案 英
相关主题
文本预览