算法分析實驗四報告.doc

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