算法分析實(shí)驗(yàn)四報(bào)告.doc

算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告 目 錄1、 實(shí)驗(yàn)內(nèi)容描述和功能分析.2、 算法過(guò)程設(shè)計(jì).3、 程序調(diào)試及結(jié)果（附截圖）.4、 源代碼（附源代碼）.1、 實(shí)驗(yàn)內(nèi)容描述和功能分析.1.最長(zhǎng)公共子序列內(nèi)容描述：一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱(chēng)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è)最長(zhǎng)公共子序列。序列B，C，B，A也是X和Y的一個(gè)公共子序列，它的長(zhǎng)度為4，而且它是X和Y的一個(gè)最長(zhǎng)公共子序列，因?yàn)閄和Y沒(méi)有長(zhǎng)度大于4的公共子序列。 最長(zhǎng)公共子序列問(wèn)題就是給定兩個(gè)序列X=x1,x2,.xm和Y=y1,y2,.yn，找出X和Y的一個(gè)最長(zhǎng)公共子序列。 功能分析：輸入包含多組測(cè)試數(shù)據(jù)。第一行為一個(gè)整數(shù)C，表示有C組測(cè)試數(shù)據(jù)，接下來(lái)有C行數(shù)據(jù)，每組測(cè)試數(shù)據(jù)占1行，它由2個(gè)給定序列的字符串組成，兩個(gè)字符串之間用空格隔開(kāi). 輸出應(yīng)該有C行，即每組測(cè)試數(shù)據(jù)的輸出占一行，它是計(jì)算出的最長(zhǎng)公共子序列長(zhǎng)度。例如：輸入： 1 輸出：4 ABCBDBA BDCABA2. Minimal m Sums內(nèi)容描述：給定n 個(gè)整數(shù)組成的序列，現(xiàn)在要求將序列分割為m 段，每段子序列中的數(shù)在原序列中連續(xù)排列。如何分割才能使這m段子序列的和的最大值達(dá)到最??？ 編程任務(wù)： 給定n 個(gè)整數(shù)組成的序列,編程計(jì)算該序列的最優(yōu)m 段分割，使m 段子序列的和的最大值達(dá)到最小。功能分析：輸入由多組測(cè)試數(shù)據(jù)組成。 每組測(cè)試數(shù)據(jù)輸入的第1行中有2個(gè)正整數(shù)n和m。正整數(shù)n是序列的長(zhǎng)度；正整數(shù)m是分割的段數(shù)。接下來(lái)的一行中有n個(gè)整數(shù)。 對(duì)應(yīng)每組輸入，輸出的每行是計(jì)算出的m段子序列的和的最大值的最小值。例如：輸入：1 1 輸出：10 10 2、 算法過(guò)程設(shè)計(jì).1.最長(zhǎng)公共子序列 最長(zhǎng)公共子序列問(wèn)題是通過(guò)定義數(shù)組和指針來(lái)尋找兩者的公共子序列，實(shí)現(xiàn)對(duì)問(wèn)題的解決。2.Minimal m Sums 這個(gè)問(wèn)題是通過(guò)定以一個(gè)一維數(shù)組和一個(gè)二維數(shù)組來(lái)實(shí)現(xiàn)問(wèn)題的解決。 三、程序調(diào)試及結(jié)果（附截圖）.1.最長(zhǎng)公共子序列2.Minimal m Sums四、源代碼（附源代碼）.1.最長(zhǎng)公共子序列# include # include #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 = 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ì)算并求出長(zhǎng)度，將中間結(jié)果放在c中*/ s k = 0; /*s串的結(jié)束標(biāo)記*/ while( k 0 ) /*開(kāi)始倒推*/ 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); return 0;2.Minimal m Sums #include 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 fkj-1 ? ( fi1 - fk1 ) : fkj-1; if(temp maxt ) temp = maxt ; fij = temp ; int main() int i , n ,