算法分析与设计实验报告二.docx

《算法分析与设计实验报告二.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华中科技大学算法分析与设计实验报告学生姓名：庞亮系别：软件学院专业与班号：软件工程0805学号：U实验时间：第三周，星期三，晚上实验房间号：软件学院五楼机房[实验名称]作业排程和最长共同子序列算法[实验目的]理解动态规划算法设计思想，利用动态规划算法设计方法解决作业排程和最长共同子序列问题。[实验条件]硬件：计算机软件：计算机程序语言开发平台，如C、C++、Java、Matlab。学生：至少掌握一门计算机程序设计语言，如C、C++、Java、Matlab。[实验内容及要求]?描述并实现动态规划的作业排程算法，并显示

2、下图的排程结果。?描述并实现最长共同子序列动态规划算法，并显示S1=ACCGGTCGAGATGCAG，S2=GTCGTTCGGAATGCAT的最长共同子序列。[实验原理]1.作业排程问题对于生产的每一个环节，它不是从一生产线而来，就是从二生产线而来，而且拥有最优子问题的结构，因此可以列出这个问题的状态转移方程如下图所示。可见每个状态都与前一个状态的数值有关，于是可以由底至上一步一步求得结果。1.最长公共子序列问题LCS问题有最优子结构：设X=和Y=为两个序

3、列，并设Z=为XY的任意一个LCS。1）如果xm=yn，那么zk=xm=yn而且Zk-1是Xm-1和Yn-1的一个LCS；2）如果xm!=yn,那么zk!=xm蕴含Z是Xm-1和Y的一个LCS；3）如果xm!=yn,那么zk!=yn蕴含Z是X和Yn-1的一个LCS.由此得出这个问题的状态转移方程为：[算法具体代码]1.作业排程问题//work_flow.cpp:定义控制台应用程序的入口点。//#include"stdafx.h"intx1,x2;inte1,e2;inta[2][100

4、];intt[2][100];intf[2][100];intpath[2][101];intn;voidinit(){FILE*fin=fopen("in.txt","r");fscanf(fin,"%d",&n);fscanf(fin,"%d%d",&e1,&e2);fscanf(fin,"%d%d",&x1,&x2);for(inti=0;i

5、(inti=0;i

6、ath[0][i]=1;}else{f[0][i]=f[1][i-1]+t[1][i-1]+a[0][i];path[0][i]=2;}if((f[1][i-1]+a[1][i])<(f[0][i-1]+t[0][i-1]+a[1][i])){f[1][i]=f[1][i-1]+a[1][i];path[1][i]=2;}else{f[1][i]=f[0][i-1]+t[0][i-1]+a[1][i];path[1][i]=1;}}if(f[0][n-1]+x1

7、;returnf[0][n-1]+x1;}else{path[n][n]=2;returnf[1][n-1]+x2;}}intprintpath(inta,intb){if(b==0){printf("%d%d",a+1,b+1);return0;}printpath(path[a][b]-1,b-1);printf("%d%d",a+1,b+1);}int_tmain(intargc,_TCHAR*argv[]){init();printf("%d",execute());printpath(path

8、[n][n]-1,n-1);getchar();return0;}2.最长共同子序列问题//LCS.cpp:定义控制台应用程序的入口点。//#include"stdafx.h"#include"string.h"chars1[100];chars2[100];intlcs[100][100];intpath[100][100];intp,q;voidinit