1、（一）最長公共子序列一、實(shí)驗(yàn)內(nèi)容描述和功能分析一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。例如，若X=A，B，C，B，D，B，A，Y=B，D，C，A，B，A，則序列B，C，A是X和Y的一個(gè)公共子序列，但它不是X和Y的一個(gè)最長公共子序列。序列B，C，B，A也是X和Y的一個(gè)公共子序列，它的長度為4，而且它是X和Y的一個(gè)最長公共子序列，因?yàn)閄和Y沒有長度大于4的公共子序列。 最長公共子序列問題就是給定兩個(gè)序列X=x1,x2,.xm和Y=y1,y2,.yn，找出X和Y的一個(gè)最長公共子序列。 In

2、put 輸入包含多組測試數(shù)據(jù)。第一行為一個(gè)整數(shù)C，表示有C組測試數(shù)據(jù)，接下來有C行數(shù)據(jù)，每組測試數(shù)據(jù)占1行，它由2個(gè)給定序列的字符串組成，兩個(gè)字符串之間用空格隔開. Output 你的輸出應(yīng)該有C行，即每組測試數(shù)據(jù)的輸出占一行，它是計(jì)算出的最長公共子序列長度。Sample Input 1ABCBDBA BDCABASample Output 4二、算法過程設(shè)計(jì)最長公共子序列的結(jié)構(gòu)：設(shè)X =  x1 , . , xm ,Y =  y1 , . , 

3、yn 及它們的最長子序列Z =  z1 , . , zk 則1、若 xm = yn ， 則 zk = xm = yn，且Zk-1 是 Xm-1 和 Yn-1 的最長公共子序列2、若 xm != yn ，且 zk != xm , 則 Z 是 

4、Xm-1 和 Y 的最長公共子序列3、若 xm != yn , 且 zk != yn , 則 Z 是 Yn-1 和 X 的最長公共子序列子問題的遞歸結(jié)構(gòu)：當(dāng) i = 0 , j = 0 時(shí) , cij = 0當(dāng) i , j > 0&#

5、160; xi = yi 時(shí) , cij = ci-1j-1 + 1當(dāng) i , j > 0  xi != yi 時(shí) , cij = max  cij-1 , ci-1j 三、程序調(diào)試及結(jié)果（附截圖）運(yùn)行結(jié)果：四、源代碼（附源代碼）# include <stdio.h># include &l

6、t;string.h>#define N 100char a N , b N , str N ;int lcs_len( char *a, char *b, int c N ) int m = strlen( a ), n = strlen( b ), i, j; for( i = 0; i <= m; i+ ) c i 0 = 0; for( j = 1; j <= n; j+ ) c 0 j = 0; for( i = 1; i <= m; i+ ) for( j = 1; j <= n; j+ ) if( a i - 1 = b j - 1 ) c i j

7、= 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 ; return c m n ;char *build_lcs( char s, char *a, char *b ) int k, i = strlen( a ), j = strlen( b ), c N N ; k = lcs_len( a, b, c );/*將c傳給lcs_len()計(jì)算并求出長度，將中間結(jié)果放在c中*/ s k = '0'/*s串的結(jié)束標(biāo)記*/ while

8、( k > 0 )/*開始倒推*/ if( c i j = c i - 1 j ) i -; else if( c i j = c i j -1 ) j-; else s -k = a i - 1 ;/*將一個(gè)公共字符存入s中*/ i-; j-; return s;int main() int n,m; scanf("%d",&m); getchar(); while(m-) scanf( "%s%s", a,b ); n=strlen(build_lcs( str, a, b ); printf("%dn",n); r

9、eturn 0;（二）Minimal m Sums一、實(shí)驗(yàn)內(nèi)容描述和功能分析給定n 個(gè)整數(shù)組成的序列，現(xiàn)在要求將序列分割為m 段，每段子序列中的數(shù)在原序列中連續(xù)排列。如何分割才能使這m段子序列的和的最大值達(dá)到最小？ 編程任務(wù)： 給定n 個(gè)整數(shù)組成的序列,編程計(jì)算該序列的最優(yōu)m 段分割，使m 段子序列的和的最大值達(dá)到最小。Input 輸入由多組測試數(shù)據(jù)組成。 每組測試數(shù)據(jù)輸入的第1行中有2個(gè)正整數(shù)n和m。正整數(shù)n是序列的長度；正整數(shù)m是分割的段數(shù)。接下來的一行中有n個(gè)整數(shù)。 Output 對應(yīng)每組輸入，輸出的每行是計(jì)算出的m段子序列的和的最大值的最小值。Sample Input 1 110Sam

10、ple Output 10二、算法過程設(shè)計(jì)數(shù)據(jù)輸入：     由文件sum*.in提供輸入數(shù)據(jù)。文件的第1行中有2個(gè)正整數(shù)n和m。正整數(shù)n是序列的長度；正整數(shù)m是分割的段數(shù)。接下來的一行是n個(gè)數(shù)據(jù)。  三、程序調(diào)試及結(jié)果（附截圖）運(yùn)行結(jié)果：四、源代碼（附源代碼）#include <iostream> using namespace std; int t100; int f100100 ; void s(int n , int m ) int i , j , k , temp , maxt ; for ( i = 1 ; i <= n ; i + ) fi1 = fi-11 + ti ; for ( j = 2 ; j <= m ; j + ) for(i = j ; i <= n ; i + ) for ( k = 1 , temp = 99999999 ; k < i ; k + ) maxt = (fi1 - fk1) > fkj-1 ? ( fi1 - fk1 ) : fkj-1; if(temp > maxt ) temp = maxt ; fij = temp ; int main() int i , n , m ; cin >> n &g