下载文档原格式
最长公共子序列问题一．实验目的：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进行配对。
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，否则在输出文件的第二行输出所求得的最长公共子序列(也用一个大写字母组成的字符串表示。
【输入样例】ABCBDABBDCBA【输出样例】4BCBA【问题分析】这个问题也是相当经典的。
这个题目的阶段很不明显，所以初看这个题目没什么头绪，不像前面讲的有很明显的上一步，上一层之类的东西，只是两个字符串而且互相没什么关联。
但仔细分析发现还是有入手点的：既然说是动态规划，那我们首先要考虑的就是怎么划分子问题，一般对于前面讲到的街道问题和数塔问题涉及走向的，考虑子问题时当然是想上一步是什么？但这个问题没有涉及走向，也没有所谓的上一步，该怎么办呢？既然是求公共子序列，也就有第一个序列的第i个字符和第二个序列的第j个字符相等的情况。
第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。
为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。
二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。
1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。
（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。
- 对每种算法进行时间复杂度和空间复杂度的分析。
- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。
（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。
- 编写三种排序算法的代码。
- 分析代码的时间复杂度和空间复杂度。
- 编写测试程序，生成随机测试数据，测试三种算法的性能。
- 比较三种算法的运行时间和内存占用。
2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。
（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。
- 分析贪心算法的正确性，并证明其最优性。
（3）实验步骤：- 分析活动选择问题的贪心策略。
- 编写贪心算法的代码。
- 分析贪心算法的正确性，并证明其最优性。
- 编写测试程序，验证贪心算法的正确性。
3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。
（2）实验内容：- 实现一个动态规划算法问题，如背包问题。
- 分析动态规划算法的正确性，并证明其最优性。
（3）实验步骤：- 分析背包问题的动态规划策略。
- 编写动态规划算法的代码。
- 分析动态规划算法的正确性，并证明其最优性。
- 编写测试程序，验证动态规划算法的正确性。
三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。
实验报告一、实验目的写出你认为比较重要的实验目的1．理解动态规划的基本思想,了解最优子结构性质和子问题的重叠性质。
2．熟练掌握典型的动态规划问题。
掌握动态规划思想分析问题的一般方法,对较简单的问题能正确分析,并设计出动态规划算法,并能够用程序实现。
二、实验内容简短明确地写出实验的内容（选作题目）动态规划寻找最长公共子序列三、实验环境操作系统、调试软件名称、版本号，上机地点，机器台号Win10、dev-cpp5.2.0、dreamweaver cs6四、问题分析（1）分析要解决的问题，给出你的思路，可以借助图表等辅助表达。
当一个问题具有最优子结构时，我们就可以考虑使用动态规划法去实现，因此首先刻画最长公共子序列的最优子结构：设X=x1x2…xm和Y=y1y2…yn是两个序列，Z=z1z2…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的一个最长公共子序列。
从上面我们可以看出如果xm=yn，那么我们应该求解Xm-1，Yn-1的一个LCS，并且将xm=yn加入到这个LCS的末尾，这样得到的一个新的LCS就是所求。
如果xm≠yn，分别求Xm-1，Y的一个LCS和X，Yn-1的一个LCS。
其中较长者就是X和Y的一个LCS。
c[m][n]=c[m-1][n-1]+1;c[m][n]=max(c[m-1][n],c[m][m-1]);（2）分析利用你的想法解决该问题可能会有怎样的时空复杂度。
建立c[m][n]的过程中时间复杂度是Ο（mn），空间复杂度是Ο（mn）。
（3）其它（你认为需要在此说明的）五、问题解决（1）根据对问题的分析，写出解决办法。
计算最长公共子序列长度的动态规划算法LCSLength以x[]和y[]作为输入，输出两个数组b[][]和c[][]，其中c[][]存储最长公共子序列的长度，b[][]记录指示c[][]的值是由那个子问题解答得到的，最后将最终的最长公共子序列的长度记录到c[][]中。
最长公共子序列的研究报告在计算机科学和数学领域中，最长公共子序列（Longest Common Subsequence，简称LCS）问题是一个经典且具有重要意义的研究课题。
它不仅在理论研究方面具有深厚的价值，还在实际应用中发挥着关键作用。
最长公共子序列问题的定义相对简单直观。
给定两个序列，我们要找出它们之间最长的公共部分，这个公共部分中的元素顺序保持不变。
例如，对于序列“ABCDGH”和“AEDFHR”，它们的最长公共子序列是“ADH”。
那么，为什么我们要研究最长公共子序列问题呢？这主要是因为它在很多实际场景中都有应用。
在生物信息学中，比较 DNA 序列或蛋白质序列的相似性时，最长公共子序列可以帮助我们了解物种之间的进化关系。
在文件比较和版本控制方面，通过找出两个文本文件的最长公共子序列，可以快速确定它们之间的差异和相似之处，从而提高工作效率。
在自然语言处理中，分析句子结构和语义的相似性时，最长公共子序列也能提供有价值的信息。
接下来，让我们探讨一下如何求解最长公共子序列问题。
最常见的方法是动态规划。
动态规划是一种通过将复杂问题分解为子问题，并保存子问题的解来避免重复计算的方法。
假设我们有两个序列 X 和 Y，长度分别为 m 和 n。
我们创建一个二维数组 dpm ＋ 1n ＋ 1来保存中间计算的结果。
dpij表示序列 X 的前 i 个元素和序列 Y 的前 j 个元素的最长公共子序列的长度。
初始化时，dp 的第一行和第一列都为 0，因为当一个序列为空时，最长公共子序列的长度为 0。
然后，我们通过以下递推公式来填充 dp 数组：如果 Xi 1 ＝＝ Yj 1，那么 dpij ＝ dpi 1j 1 ＋ 1。
这意味着如果当前两个元素相等，那么它们构成了公共子序列的一部分，长度在前一个状态的基础上加 1。
如果 Xi 1!＝ Yj 1，那么 dpij ＝ max(dpi 1j, dpij 1)。
这表示如果当前两个元素不相等，那么最长公共子序列的长度要么是只考虑 X 序列前 i 1 个元素和 Y 序列前 j 个元素的最长公共子序列的长度，要么是只考虑 X 序列前 i 个元素和 Y 序列前 j 1 个元素的最长公共子序列的长度，取两者中的最大值。
目录1 前言02 需求分析12.1 任务和要求12.2 运行环境12.3 开发工具13 分析和设计13.1 系统分析及设计思路13.2 主要数据结构及算法23.3 函数流程图24 具体代码实现35 课程设计总结135.1 程序运行结果或预期运行结果135.2 设计结论13参考文献14致谢141 前言若给定序列X={x1,x2,…,x m}，则另一序列Z={z1,z2,…,z k}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y 的子序列时，称Z是序列X和Y的公共子序列。
请使用C语言编程，设计一个有效的算法解决下述问题：给定2个序列X={x1,x2,…,x m}和Y={y1,y2,…,y n}，找出X和Y 的最长公共子序列。
2 需求分析2.1任务和要求使用C语言编程，设计一个有效的算法解决下述问题：给定2个序列X={x1,x2,…,x m}和Y={y1,y2,…,y n}，找出X和Y的最长公共子序列。
2.2运行环境（1）WINDOWS2000/XP系统（2）Visual C++ 6.0编译环境或TC编译环境2.3开发工具C语言3 分析和设计3.1 系统分析及设计思路设序列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个序列的前缀的最长公共子序列。
第1篇一、实验背景随着计算机科学的不断发展，算法在各个领域都扮演着至关重要的角色。
为了更好地理解和掌握算法设计与应用，我们进行了本次算法实验。
本次实验旨在通过实际操作，加深对常见算法的理解，提高算法设计与分析能力。
二、实验目的1. 掌握常见算法的基本原理和实现方法。
2. 熟悉算法的时间复杂度和空间复杂度分析。
3. 培养团队协作精神和实验操作能力。
三、实验内容本次实验主要涉及以下算法：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。
2. 查找算法：顺序查找、二分查找、斐波那契查找。
3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最短路径算法（Dijkstra算法、Floyd算法）。
四、实验过程1. 熟悉实验环境，安装必要的开发工具和库。
2. 分析每个算法的基本原理，编写代码实现。
3. 对每个算法进行时间复杂度和空间复杂度分析。
4. 对比不同算法的优缺点，总结适用场景。
5. 编写实验报告，总结实验心得。
五、实验结果与分析1. 排序算法（1）冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)，适用于小规模数据排序。
（2）选择排序：时间复杂度O(n^2)，空间复杂度O(1)，适用于小规模数据排序。
（3）插入排序：时间复杂度O(n^2)，空间复杂度O(1)，适用于部分有序数据排序。
（4）快速排序：时间复杂度O(nlogn)，空间复杂度O(logn)，适用于大规模数据排序。
（5）归并排序：时间复杂度O(nlogn)，空间复杂度O(n)，适用于大规模数据排序。
（6）堆排序：时间复杂度O(nlogn)，空间复杂度O(1)，适用于大规模数据排序。
2. 查找算法（1）顺序查找：时间复杂度O(n)，空间复杂度O(1)，适用于数据量较小的查找。
（2）二分查找：时间复杂度O(logn)，空间复杂度O(1)，适用于有序数据查找。
（3）斐波那契查找：时间复杂度O(logn)，空间复杂度O(1)，适用于有序数据查找。
最长公共子序列实验报告公司内部档案编码：[OPPTR-OPPT28-OPPTL98-OPPNN08]最长公共子序列问题一．实验目的：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可用于快速构造序列最长公共子序列。
课程名称算法分析与设计实验实验项目实验一实验时间__2011__ 年_5___月__ 16 日实验指导老师曹霑懋实验评分院系：计算机学院实验课程：算法分析与设计实验实验项目：实验一（动态规划法算法）指导老师：曹霑懋开课时间：2010 ～ 2011年度第 2学期专业：计算机科学与技术师范类班级：09级 2 班学生：程毅学号： 20092101056华南师范大学教务处课程名称算法分析与设计实验实验项目实验一实验时间__2011__ 年_5___月__ 16 日实验指导老师曹霑懋实验评分实验名称：动态规划算法（综合性实验）实验目标：使用动态规划法和回溯法生成两个长字符串的最优化比对结果。
实验任务：把两个字符串放在一个二维矩阵中，把相同的字符尽最大可能放入同一列（使得整个的比对总计分最大）。
字符串S1，S2 分别放在二维矩阵的第一行和第2行，不可错行。
字符可以在行内移动，通过插入空格使得共同的片段置于共同的列。
实验步骤：1.明确实验目标和实验任务2.理解实验所涉及到的最长公共子序列的算法3.编写程序实现求两个字符串的最长公共子序列的长度。
4.设计实验数据数据并运行程序，记录运行的结果程序代码:#include<iostream>#include<string>#include<iomanip>using namespace std;int dp[1000][1000];string str1,str2,s1,s2;int max(int a,int b,int c){if(a>b && a>c)return a;if(b>a && b>c)return b;if(c>a && c>b)return c;}int lcs(int len1,int len2){memset(dp,0,sizeof(dp));int i,j,x;课程名称算法分析与设计实验实验项目实验一实验时间__2011__ 年_5___月__ 16 日实验指导老师曹霑懋实验评分dp[0][1]=0;dp[1][0]=0;dp[1][1]=0;dp[0][0]=0;for(i=2;i<len1+2;i++){dp[i][1]=-2*(i-1);}for(j=2;j<len2+2;j++){dp[1][j]=-2*(j-1);}for(j=2;j<len2+2;j++){for(i=2;i<len1+2;i++){if(str1[i-2]==str2[j-2])x=dp[i-1][j-1]+5;elsex=dp[i-1][j-1]-1;dp[i][j]=max(x,dp[i-1][j]-2,dp[i][j-1]-2);}}return dp[i-1][j-1];}void print(int len1,int len2){int i,j;i=len1+1;j=len2+1;while(i>1 && j>1){if(dp[i][j]+2==dp[i-1][j]){s2=s2+'_';s1=s1+str1[i-2];i--;continue;课程名称算法分析与设计实验实验项目实验一实验时间__2011__ 年_5___月__ 16 日实验指导老师曹霑懋实验评分}if(dp[i][j]+2==dp[i][j-1]){s1=s1+'_';s2=s2+str2[j-2];j--;continue;}if(dp[i][j]+1==dp[i-1][j-1] || dp[i][j]-5==dp[i-1][j-1]){s1=s1+str1[i-2];s2=s2+str2[j-2];j--;i--;continue;}}for(i=len1-1;i>=0;i--){cout<<s1[i];}cout<<endl;for(j=len1-1;j>=0;j--){cout<<s2[j];}cout<<endl;}int main(){int len1,len2;while(cin>>str1>>str2){len1=str1.size();len2=str2.size();cout<<lcs(len1,len2)<<endl;课程名称算法分析与设计实验实验项目实验一实验时间__2011__ 年_5___月__ 16 日实验指导老师曹霑懋实验评分for(int i=1;i<=len1+1;i++){for(int j=1;j<=len2+1;j++){cout<<setw(5)<<dp[i][j]<<" ";}cout<<endl;}print(len1,len2);}return 0;}数据测试：实验小结：通过这次实验，对动态规划法求最长公共子序列有更深的理解。
《算法设计与分析》实验报告实验序号：实验项目名称:编程实现动态规划的算法最长公共子序列：Import java.io.BufferedReader; Import java.io.IOException; Import java.io.InputStreamReader; Import java.util.ArrayList; Import java.util.Scanner;Import java.util.List;/***动态规划法解最长公共子系列。
*@author蓝冠恒*/Public class LcsLength {publicstaticList<Character> resultList =New ArrayList<Character>(); /***计算最优值*@paramx*字符系列数组*@paramy*字符系列数组*@paramc*存储x和y最长公共子系列长度数组*@paramb*记录c中元素对应子问题的解的数组*/publicstaticvoid lcsLength( charx[],chary[],int[][] c,int[][] b) {intm = x. length- 1;intn = y.length- 1;resultList.clear();for(inti = 1; i <= m; i++) {c[i][0] = 0;}forinti = 1; i <= n; i++) {c[0][i] = 0;}for(inti = 1; i <= m; i++) {for(intj = 1; j <= n; j++) {if(x[i] == y[j]) {c[i][j] = c[i - 1][j - 1] + 1;b[i][j] = 1;}elseif(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;}}}}publicstaticvoidlcs(inti,intj,charx[],int[][] b) {if(i == 0 || j == 0) {return;}if(b[i][j] == 1) {lcs(i - 1, j - 1, x, b);resultList.add(x[i]);}elseif(b[i][j] == 2) {lcs(i - 1, j, x, b);}else{lcs(i, j - 1, x, b);}}publicstaticvoidmain(String arg[]) {String a;String input;char[] x;char[] y;Scanner scan=New Scanner(System.in);BufferedReader in = New BufferedReader(New InputStreamReader(System.in)); do{try{do{System.out.println("请输入第一串字符系列");input = in.readLine().trim();}while(input.equals(""));input = "S" + input;x = input.toCharArray();do{System.out.println("请输入第二串字符系列");input = in.readLine().trim();}while (input.equals(""));input = "S" + input;y = input.toCharArray();int[][] b = newint[x.length][y.length];int[][] c = New int[x.length][y.length];lcsLength(x, y, c, b);// 计算最优值lcs(x.length- 1, y.length- 1, x, b);// 构造最长公共子系列intsize = resultList.size();System.out.print("最长公共子系列为:");for(inti = 0; i < size; i++) {System.out.print(resultList.get(i));}System.out.println("\n");}catch(IOException e) {e.printStackTrace();}System.out.print("继续输入请按y。
第五次实验报告——最长公共子序列的生成算法1.1算法应用背景最长公共子序列是一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。
而最长公共子串(要求连续)和最长公共子序列是不同的。
最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。
对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。
简而言之，百度知道、百度百科都用得上。
1.2算法原理若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
例：∑= {x, y, z} ，A = x y z y x z x zx x x 是长度为3 的子序列x z y z x 是长度为5 的子序列例：A = x y z y x z x z，B = x z y x x y z xx x x是长度为3 的公共子序列x z y z 是长度为4 的公共子序列x z y x x z 是长度为6 的最长公共子序列1.3算法描述记L n,m为序列A n和B m的最长公共子序列长度，则L i,j为序列A i和Bj的最长公共子序列的长度。
根据最长公共子序列的性质，则得到：阶段的划分和最长公共子序列长度的获取第一阶段：计算A1和Bj的最长公共子序列的长度L1,j ,j=1,2,…m第二阶段：计算A2和B j的最长公共子序列的长度L2,j, j=1,2,…m第n 阶段：计算A n和B j的最长公共子序列的长度L n,j, j=1,2,…m第n 阶段的L m,n便是序列A n和B m的最长公共子序列的长度为了得到A n和B m最长公共子序列，设置一个二维的状态字数组s i，j，在上述每一个阶段计算L n,j过程中，根据公共子序列的性质则有按照如下方法把搜索状态登记于状态字s i，j中：s i，j =1 a i=b js i，j =2 a i≠b j L i-1,j>= L i,j-1s i，j =3 a i≠b j L i-1,j< L i,j-1设L n,m=k,S k=c1c2……c k是序列A n和B m的长度为k的最长公共子序列。
矿产资源开发利用方案编写内容要求及审查大纲
矿产资源开发利用方案编写内容要求及《矿产资源开发利用方案》审查大纲一、概述
㈠矿区位置、隶属关系和企业性质。
如为改扩建矿山, 应说明矿山现状、
特点及存在的主要问题。
㈡编制依据
(1简述项目前期工作进展情况及与有关方面对项目的意向性协议情况。
(2 列出开发利用方案编制所依据的主要基础性资料的名称。
如经储量管理部门认定的矿区地质勘探报告、选矿试验报告、加工利用试验报告、工程地质初评资料、矿区水文资料和供水资料等。
对改、扩建矿山应有生产实际资料, 如矿山总平面现状图、矿床开拓系统图、采场现状图和主要采选设备清单等。
二、矿产品需求现状和预测
㈠该矿产在国内需求情况和市场供应情况
1、矿产品现状及加工利用趋向。
2、国内近、远期的需求量及主要销向预测。
㈡产品价格分析
1、国内矿产品价格现状。
2、矿产品价格稳定性及变化趋势。
三、矿产资源概况
㈠矿区总体概况
1、矿区总体规划情况。
2、矿区矿产资源概况。
3、该设计与矿区总体开发的关系。
㈡该设计项目的资源概况
1、矿床地质及构造特征。
2、矿床开采技术条件及水文地质条件。
一、算法分析最长公共子序列问题为动态规划算法的一个具体应用。
动态规划算法思想的实质为分治思想和解决冗余。
其与分治思想不同之处在于经分解的子问题往往不是互相独立的，而分治思想分解出的子问题是互相独立，各自求解。
动态规划问题子问题的解由子子问题的解组成，因此使用一种存储结构建立一个存储表用来记录所有已解子问题的值。
相对应的代价是增加了空间复杂度，以换取问题求解时间的减少。
最长公共子序列问题按动态规划算法的执行步骤求解。
1.找出最优解的性质，刻画其结构特征。
设两个序列为X(x1,x2…..xm)，Y(y1,y2……yn)。
最优子结构特征可以刻画为Z(z1,z2……zk)。
可以分为三种情况：Xm=Yn、Xm>Yn、Xm<Yn。
第一种情况下可断定Zk=Xm=Yn。
第二种情况可将原问题转化为求解Xm-1与Yn的LCS。
第三种情况可将原问题转化为求解Xm与Yn-1的LCS。
2.递归地定义最优值(写出动态规划方程)。
由1中情况可得出递归解的递归过程。
初始条件可判定为C[i][0]、C[0][j]的值为0。
其意义为X或Y有一个序列为0时，最长公共子序列长度为0。
3.以自底向上的方式计算出最优值。
由i=0或j=0的情况向上计算，直到C[m][n]。
4.根据计算最优值时记录的信息，构造最优解。
二、算法实现算法实现可分为三个步骤：1.数据结构选取本次实验采用的数据结构为数组。
二维数组C[i][j]用于判断最优解的构造顺序以及计算最优解的长度。
二维数组B[i][j]用于记录最优解的构造顺序，在打印最优解时做一个索引。
X[i]、Y[i]用于存储输入的两个子序列。
2.LCS长度求解函数函数名为LCS_length。
实现方法参照分析步骤二和三。
3.LCS值输出函数函数名为Print_LCS。
实现方法为自底向上判断记录符号，并输出符合条件的Xi或Yj。
三、实验结果实验进行三次。
第一次为X与Y等长的情况，第二次为X长度小于Y的情况，第三次为X长度大于Y的情况。
矿产资源开发利用方案编写内容要求及审查大纲
矿产资源开发利用方案编写内容要求及《矿产资源开发利用方案》审查大纲一、概述
㈠矿区位置、隶属关系和企业性质。
如为改扩建矿山, 应说明矿山现状、
特点及存在的主要问题。
㈡编制依据
(1简述项目前期工作进展情况及与有关方面对项目的意向性协议情况。
(2 列出开发利用方案编制所依据的主要基础性资料的名称。
如经储量管理部门认定的矿区地质勘探报告、选矿试验报告、加工利用试验报告、工程地质初评资料、矿区水文资料和供水资料等。
对改、扩建矿山应有生产实际资料, 如矿山总平面现状图、矿床开拓系统图、采场现状图和主要采选设备清单等。
二、矿产品需求现状和预测
㈠该矿产在国内需求情况和市场供应情况
1、矿产品现状及加工利用趋向。
2、国内近、远期的需求量及主要销向预测。
㈡产品价格分析
1、国内矿产品价格现状。
2、矿产品价格稳定性及变化趋势。
三、矿产资源概况
㈠矿区总体概况
1、矿区总体规划情况。
2、矿区矿产资源概况。
3、该设计与矿区总体开发的关系。
㈡该设计项目的资源概况
1、矿床地质及构造特征。
2、矿床开采技术条件及水文地质条件。
