探究算法与设计课程中最长公共子序列理由教学*

论文导读：tcommonsubsequence;dynamicprogramming;descendingsubsequence;palindromicsequence在算法分析与设计课程中，最长公共子序列理由是一个可用动态规划策略求解的经典最优化理由，它可以描述两个序列之间的“相似度”。该理由是一个十分实用的理由，利用该理由可以有效地求解许多实际理由。该理由描述为：给定两个
摘 要 介绍算法分析与设计课程中最长公共子序列理由的动态规划算法，利用该算法解决最长递减子序列理由和回文词的构造理由，通过这两个理由的求解，有助于学生举一反

三、启发学生思维，以学致用，提高理由求解能力。

关键词 最长公共子序列;动态规划;递减子序列;回文词
1671-489X（2014）24-0109-03
Discussion of Longest Common Subsequence Problem in Course of Analysis and Design of Algorithm//LIU Wen， ZHOU Bo， SANG Haitao， GU Zeyuan， HAN Na
Abstract This paper introduces a dynamic programming algorithm of the longest common subsequence problem in the course of analysis and design of algorithm， by use of which this paper solves the longest descending subsequence problem and the construction of the palindromic sequence problem. By solving the two problems， will help students draw inferences about other cases from one instance， inspire students’ thinking， apply their knowledge to all， improve the ability of problem solving.
Key words longest common subsequence; dynamic programming; descending subsequence; palindromic sequence
在算法分析与设计课程中，最长公共子序列理由是一个可用动态规划策略求解的经典最优化理由，它可以描述两个序列之间的“相似度”。该理由是一个十分实用的理由，利用该理由可以有效地求解许多实际理由。
该理由描述为：给定两个序列X和Y，当另一序列Z既是X的子序列，又是Y的子序列时，称Z是序列X和Y的公共子序列;如果Z是X与Y的公共子序列中长度最大的，则称Z是X和Y的最长公共子序列[1]。例如，序列X={A，B，C，B，D，A，B}，Y={B，D，C，A，B，A}，则序列{B，C，A}和序列{B，C，B，A}都是X与Y的公共子序列，而{B，C，B，A}是X与Y的一个长度为4的最长公共子序列。
可以用穷举法求解该理由，但穷举法的时间复杂度较高，为指数级，效率较低。利用动态规划策略可有效求解该理由，其时间复杂度为多项式级，效率较高。
1 最长公共子序列理由的动态规划算法
下面给出一个定理，该定理表明最长公共子序列理由具有最优化结构性质。
定理1[2] 设序列X={x1，x2，…，xm}，序列Y={y1，y2，…，
yn}，且X与Y的最长公共子序列为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的最长公共子序列。
由此可见，两个序列的最长公共子序列中包括了这两个子序列的前缀的最长公共子序列，因此该理由具有最优子结构性质。
设用c[i][j]保存序列Xi={x1，x2，…，xi}和Yj={y1，y2，…，
yj}的最长公共子序列的长度，则根据定理1可得c[i][j]满足的递推关系式如下[3]：
根据该递推关系式，利用自底向上的计算方式可以设计出求解最长公共子序列理由最优值的算法，算法描述如下：
int c[100][100];
void LCSlength（char x[]， char y[]， int m， int n）
{//动态规划法求最长公共子序列的最优值算法
int i，j;
for（i=0; i<=m; i++）c[i][0]=0;
for（j=0;j<=n;j++） c[0][j]=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;
else if（c[i-1][j]>=c[i][j-1]）c[i][j] = c[i-1][j];
else c[i][j] = c[i][j-1];
}
}
2 利用最长公共子序列求解最长递减子序列
最长递减子序列理由描述 给定由n个整数a1，a2，…，
an构成的序列，在这个序列中随意删除一些元素后可得到一个子序列ai，aj，ak，…，am，其中1≤i≤m≤n，i