3寻找最长公共子序列(动态规划)

1、 天津商业大学学生实验报告 开课实验室： 403 机房 开课时间 2015年 3 月 1日 实验报告 2015年 6月 1 日 学院名称信息工程学院年级、专业、班计科1303班学号20134390姓名吴雪婷同组姓名 无课程名称算法分析与设计实验项目名称寻找最长公共子序列（动态规划）指导教师杨亮实验类型 验证 综合 设计 创新成绩实验报告内容一般包括以下几个内容：1、目的要求 2、仪器用具及材料（仪器名称及主要规格、用具名称） 3、实验内容及原理（简单但要抓住要点，写出依据原理） 4、操作方法与实验步骤 5、数据图表格（照片） 6、实验过程原始记录 7数据处理及结果（按实验要求处理数据、结论）

2、8、讨论（对实验中存在的问题、进一步的想法等进行讨论）一、实验目的通过对最长公共子序列的编程实现，增强对动态规划方法的了解。二、实验内容编程用动态规划的自底向上的方法求解两个序列的最长公共子序列问题（要求粘贴代码和实验结果截图）。三、实验步骤和过程在最优化问题的求解过程中，通常会出现大量重复计算问题，当遇到此类问题的时候，如果我们又可以容易的找到它的最优子结构，那么就可以尝试使用动态规划方法求解，动态规划方法中可以使用自底向上法和自顶向下记录法两种方法来减少重复的运算量，从而达到提高运算效率的目的。实验代码：#include <stdio.h>#define SIZE 5int p

3、SIZE+1 =20,100,5,30,500,1000;int dataSIZESIZE;int dirSIZESIZE;void multiple();int main(int argc,char* argv)multiple();printf("The minimiu eperation is %dn",data0SIZE-1);printf("Hello World!n");return 0;void multiple()int i,j,k,q,r,minm,index,temp;for(i=0;i<SIZE;i+) dataii = 0;

4、for(j=1;j<SIZE;j+)for(k=0;k<SIZE-j;k+)q = k + j; minm=10000000000;index = 0; for(r=k;r<q;r+)temp = datakr + datar+1q + pk*pr+1*pq+1;if(temp< minm)minm =temp;index =r; datakq = minm;dirkq = index;printf("The %d iteration n",j);for (i=0;i<SIZE;i+)for(k=0;k<SIZE;k+)printf(" %5d ",dataik);printf("n");printf("The direction matrix is n",j);for (i=0;i<SIZE;i+)for(k=0;k<SIZE;k+)printf(" %5d ",dirik);printf("n");注1.每个实验项目一份实验报告。2.实验报告第一页学生必须使用规定的实验报告纸书写，附页用实验报告附页纸或A4