《算法分析实验报告》由会员分享，可在线阅读，更多相关《算法分析实验报告（6页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析实验报告目目 录录1、实验内容描述和功能分析.2、算法过程设计.3、程序调试及结果（附截图）.4、源代码（附源代码）.1、实验内容描述和功能分析.1.1.最长公共子序列最长公共子序列内容描述：内容描述：一个给定序列的子序列是在该序列中删去若干元素后得 到的序列。给定两个序列 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 和
2、 Y 的一个公共子序列，它 的长度为 4，而且它是 X 和 Y 的一个最长公共子序列，因为 X 和 Y 没有长度大于 4 的公共子序列。 最长公共子序列问题就是给定两个 序列 X=x1,x2,.xm和 Y=y1,y2,.yn，找出 X 和 Y 的一个最长 公共子序列。 功能分析：功能分析：输入包含多组测试数据。第一行为一个整数 C，表示有 C 组测试数据，接下来有 C 行数据，每组测试数据占 1 行，它由 2 个给定序列的字符串组成，两个字符串之间用空格隔开. 输出应该有 C 行，即每组测试数据的输出占一行，它是计算出的最 长公共子序列长度。例如：例如：输入： 1 输出：4ABCBDBA BD
3、CABA 2.2.MinimalMinimal m m SumsSums内容描述：内容描述：给定 n 个整数组成的序列，现在要求将序列分割为 m 段，每段子序列中的数在原序列中连续排列。如何分割才能使这 m 段子序列的和的最大值达到最小？ 编程任务： 给定 n 个整数组成的序列,编程计算该序列的最优 m 段分割，使 m 段子序列的和的最大值达到最小。功能分析：功能分析：输入由多组测试数据组成。 每组测试数据输入的第 1 行中有 2 个正整数 n 和 m。正整数 n 是序 列的长度；正整数 m 是分割的段数。接下来的一行中有 n 个整数。 对应每组输入，输出的每行是计算出的 m 段子序列的和的最
4、大值的 最小值。例如：输入：1 1 输出：1010 2、算法过程设计.1.1.最长公共子序列最长公共子序列最长公共子序列问题是通过定义数组和指针来寻找两者的公共子序列，实现对问题的解决。2.Minimal2.Minimal m m SumsSums 这个问题是通过定以一个一维数组和一个二维数组来实现问题 的解决。 三、程序调试及结果（附截图）.1.1.最长公共子序列最长公共子序列2.Minimal2.Minimal m m SumsSums四、源代码（附源代码）. 1.1.最长公共子序列最长公共子序列 # include # include #define N 100 char a N ,b
5、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 = 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 传给 l
6、cs_len()计算并求出长度，将中间结果放在 c中*/s k = 0; /*s 串的结束标记*/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“,getchar();while(m-)scanf( “%s%s“, a,b );n=strlen(build_lcs( str, a, b );printf(“%dn“,n
7、); return 0; 2.Minimal2.Minimal m m SumsSums#include using namespace std;int t100;int f100100 ;void s(int n , int m ) int i , j , k , temp , maxt ;for ( i = 1 ; i fkj-1 ? ( fi1 - fk1 ) : fkj-1;if(temp maxt ) temp = maxt ;fij = temp ; int main() int i , n , m ;cin n m ;if( (n ti;s(n,m);coutfnmendl;return 0;
