您所在位置：网站首页 > 行业资料 > 其它行业文档算法分析实验报告

算法分析实验报告

6页

卖家[上传人]：206****923

文档编号：37691619

上传时间：2018-04-21

文档格式：DOC

文档大小：58KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 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 和 Y 的一个公共子序列，它的长度为 4，而且它是 X 和 Y 的一个最长公共子序列，因为 X 和 Y 没有长度大于 4 的公共子序列。最长公共子序列问题就是给定两个序列 X=x1,x2,.xm和 Y=y1,y2,.yn，找出 X 和 Y 的一个最长公共子序列。功能分析：功能分析：输入包含多组测试数据。第一行为一个整数 C，表示有 C 组测试数据，接下来有 C 行数据，每组测试数据占 1

2、行，它由 2 个给定序列的字符串组成，两个字符串之间用空格隔开. 输出应该有 C 行，即每组测试数据的输出占一行，它是计算出的最长公共子序列长度。例如：例如：输入： 1 输出：4ABCBDBA BDCABA 2.2.MinimalMinimal m m SumsSums内容描述：内容描述：给定 n 个整数组成的序列，现在要求将序列分割为 m 段，每段子序列中的数在原序列中连续排列。如何分割才能使这 m 段子序列的和的最大值达到最小？编程任务：给定 n 个整数组成的序列,编程计算该序列的最优 m 段分割，使 m 段子序列的和的最大值达到最小。功能分析：功能分析：输入由多组测试数据组成。每组测试数据输入的第 1 行中有 2 个正整数 n 和 m。正整数 n 是序列的长度；正整数 m 是分割的段数。接下来的一行中有 n 个整数。对应每组输入，输出的每行是计算出的 m 段子序列的和的最大值的最小值。例如：输入：1 1 输出：1010 2、算法过程设计.1.1.最长公共子序列最长公共子序列最长公共子序列问题是通过定义数组和指针来寻找两者的公共子序列，实现对问题的解决。2.Minim

3、al2.Minimal m m SumsSums 这个问题是通过定以一个一维数组和一个二维数组来实现问题的解决。三、程序调试及结果（附截图）.1.1.最长公共子序列最长公共子序列2.Minimal2.Minimal m m SumsSums四、源代码（附源代码）. 1.1.最长公共子序列最长公共子序列 # include # include #define N 100 char 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 = 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

4、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); 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;

《算法分析实验报告》由会员206****923分享，可在线阅读，更多相关《算法分析实验报告》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源