《实验报告余双.docx》由会员分享，可在线阅读，更多相关《实验报告余双.docx（25页珍藏版）》请在三一文库上搜索。
1、实验报告余双实验报告余双 实验编号：3 四川师大算法设计与分析实验报告 xxxx 年5月1日 计算机科学学院14 级4班 实验名称：动态规划及其应用姓名：余双 学号：xxxx110451 指导老师：_苏菡_ 实验成绩:_实验一 动态规划及其应用实验目的及要求目的要求：（1）理解动态规划算法的概念和基本要素，并能和分治法进行比较。（2）掌握设计动态规划算法的步骤，并编程实现有关算法。（3）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。实验内容编程实现矩阵连乘问题的求解。（2）编程实现最大子段和问题的求解（分别采用分治法和动态规划法求解）。（3）编程实现
2、01背包问题的求解。（4）设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。（5）编程实现最长公共子序列(LCS)问题的求解。（6）设计算法求解数字三角形问题，并编程实现。（P80算法实现题34）（7）设计算法求解独立任务最优调度问题，并编程实现。问题描述：欧诺个2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai=bi,而对于某些j,j不等于i，有ajbj.既不能讲一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，是的这2台
3、机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总时间）。研究一个实例：（a1，a2，a3，a4，a5，a6）=（2,5,7,10,5,2）；（b1,b2,b3,b4,b5,b6）=（3,8,4,11,3,4）如：（8）设计算法求解最少硬币问题，并编程实现。注：至少选择其中3题完成。主要仪器设备及软件PC机TC、VC+、Java等任一编程语言实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现矩阵连乘问题的求解。程序代码：main.cpp#include iostream#include head.husing namespace st
4、d;int main() int i,n,*p; cout请输入矩阵的个数：endl; cinn; p=new intn+1; cout请输入矩阵的维数(相邻矩阵的行列相等，只输入一次就行！); for(i=0;i=n;i+) cinpi; int *m,*s; m=new int*n+1; s=new int*n+1; for(i=1;i=n;i+) mi=new intn+1; si=new intn+1; MatrixChain(p,n,m,s); TraceBack(1,n,s); return 0; MatrixChain.cpp#include iostream#include h
5、ead.husing namespace std;void MatrixChain(int *p,int n,int *m,int *s) int i,j,r,k; for(i=1;i=n;i+) mii=0; sii=0; for(r=2;r=n;r+) for(i=1;in;i+) j=i+r-1; if(j7) mij=mii+mi+1j+pi-1*pi*pj; sij=i; for(k=i+1;kj;k+) int temp; temp=mik+mk+1j+pi-1*pk*pj; if(tempmij) mij=temp; sij=k; TraceBack.cpp#include io
6、stream#include head.husing namespace std;void TraceBack(int i,int j,int *s) if(i=j) return ; TraceBack(i,sij,s); TraceBack(sij+1,j,s); coutMultiply Ai,sij and Multiply Asij+1,jendl; head.h:#ifndef HEAD_H_INCLUDED#define HEAD_H_INCLUDEDvoid MatrixChain(int *p,int n,int *m,int *s);void TraceBack(int i
7、,int j,int *s);#endif / HEAD_H_INCLUDED运行结果：（2）编程实现最大子段和问题的求解（分别采用分治法和动态规划法求解）。分治法：main.cpp:#include iostream#include head.husing namespace std;int main()int n,i,*a;cout请输入序列长度：endl;cinn;a=new intn+1;cout请输入该序列具体的数：;for(i=1;i=n;i+)cinai; int sum=MaxSubSum(1,n,a); cout该序列的最大字段和为：sumendl;MaxSubSum.cpp
8、:#include iostream#include head.hint MaxSubSum(int left,int right,int *a)int sum=0;if(left=right) sum=aleft0? aleft:0; else int center=(left+right)/2; int leftsum =MaxSubSum(left,center,a);int rightsum =MaxSubSum(center+1,right,a);int s1=0;int lefts=0;for(int i=center;i=left;i-)lefts+=ai;if(leftss1)
9、s1=lefts;int s2=0;int rights=0;for(int j=center+1;j=right;j+)rights+=aj;if(rightss2)s2=rights;sum=s1+s2;if(leftsumsum) sum=leftsum;if(rightsumsum) sum=rightsum;return sum;head.h:#ifndef H#define Hint MaxSubSum(int left,int right,int *a);#endif运行结果：动态规划法：main.cpp#include iostream#include head.husing
10、namespace std;int main()int n,i,*a;cout请输入序列长度：endl;cinn;a=new intn+1;cout请输入该序列具体的数：;for(i=1;i=n;i+)cinai; int sum=MaxSubSum(n,a); cout该序列的最大字段和为：sumendl;MaxSubSum.cpp#include iostream#include head.husing namespace std;int MaxSubSum(int n,int *a)int sum=0,b=0;for(int i=1;i=n;i+)if(b0) b+=ai;else b=
11、ai;if(bsum) sum=b; return sum; head.h:#ifndef H#define Hint MaxSubSum(int n,int *a);#endif运行结果：（3）编程实现01背包问题的求解main.cpp:#include iostream#include head.husing namespace std;int main()int i,n,c,*v,*w,*m;cout请输入物品个数：endl;cinn;cout请输入背包总容量：endl;cinc;v=new int n+1; w=new int n+1; cout请输入每个物品的价值：endl; for
12、(i=1;i=n;i+)cinvi;cout请输入每个物品的重量：endl;for(i=1;i=n;i+)cinwi;m=new int* n+1;for(i=0;i=n;i+)mi=new int n+1; package(n,c,v,w,m); cout物品装入背包的情况如下：（0表示该物品未放入背包，1表示该物品放入了背包）endl;traceBack(1,c,w,m,n);package.cpp:#include iostream#include head.husing namespace std;void package(int n,int c,int *v,int *w,int *
13、m) int i,j; for(i=0;i=n;i+)mi0=0; for(j=0;j=c;j+) m0j=0;if(wnj)mnj=0;elsemnj=vn;for(i=n-1;i0;i-)for(j=c;j0;j-)if(wij) mij=mi+1j; else if(mi+1jvi+mi+1j-wi) mij=vi+mi+1j-wi; else mij=mi+1j; traceBack.cpp:#include iostream#include head.husing namespace std;void traceBack(int i,int j,int *w,int *m,int n
14、)if(i=n)if(wi=j)cout物品i:1endl;elsecout物品i:0endl;return ;if(mij=mi+1j)cout物品i:0endl;i+;traceBack(i,j,w,m,n);else cout物品i:1endl; j-=wi;i+;traceBack(i,j,w,m,n);head.h:#ifndef H#define Hvoid package(int n,int c,int *v,int *w,int *m);void traceBack(int i,int j,int *w,int *m,int n);#endif运行结果：（4）设计一个O(n2)
15、时间的算法，找出由n个数组成的序列的最长单调递增子序列。程序代码：main.cpp:#include iostream#include Sub.husing namespace std;int main()int n,*a,*b,*c,i;cout请输入序列长度：endl;cinn;a=new intn+1; b=new intn+1; c=new intn+1;cout请输入该序列的每一个数:endl;for(i=1;i=n;i+)cinai;bn=1; Sub(n,a,b,c); int temp=b1,j=1;for(i=1;i=n;i+) if(tempbi) temp=bi;j=i;
16、cout最长单调递增子序列长度为temp,如下所示：endl;while(cj!=j) coutaj ; j=cj; coutajendl;sub.cpp:#include iostream#include Sub.husing namespace std;int Sub(int n,int *a,int *b,int *c) int i,k,j,temp,temp2; for(i=n;i0;i-) temp=ai;j=0;temp2=0;bi=1; for(k=i+1;k=n;k+) if(aiakbktemp2) j=k;temp=ak;temp2=bk;if(temp=ai) bi=1;
17、 ci=i; elsebi=1+temp2;ci=j;return 0;sub.h:#ifndef H#define Hint Sub(int n,int *a,int *b,int *c);#endif运行结果：（5）编程实现最长公共子序列(LCS)问题的求解程序代码：main.cpp:#include iostream#include head.husing namespace std;int main()char *x,*y;int m,n;cout请输入第一个序列的长度:endl;cinm;x=new charm+1;cout请输入第一个序列:endl;for(int i=1;i=m;
18、i+)cinxi;cout请输入第二个数序列长度:endl;cinn; y=new charn+1; cout请输入第二个序列:endl;for(int j=1;j=n;j+)cinyj;int *c,*b;c=new int*m+1; b=new int*m+1; for(int k=0;k=m;k+) ck=new int n+1;bk=new int n+1;LCSLegth(m,n,x,y,c,b);char * z=new char cmn+1; LCS(m,n,x,b,z,cmn); cout最长公共子序列如下：endl; for(i=1;i=cmn;i+) coutzi;cout
19、endl; return 0; LCS.cpp:#include iostream#include head.husing namespace std;int LCS(int i,int j,char * x,int *b,char * z,int k)if(i=0|j=0)return 0;else if(bij=1) zk=xi; i-; j-; LCS(i,j,x,b,z,k-1); elseif(bij=2)i-; LCS(i,j,x,b,z,k); elsej-;LCS(i,j,x,b,z,k);LCSLegth.cpp:#include iostream#include head.
20、husing namespace std;int LCSLegth(int m, int n, char *x, char *y,int* c,int *b)int i,j; for(i=0;i=m;i+) ci0=0;for(j=0;j=n;j+)c0j=0;for(i=1;i=m;i+)for(j=1;j=n;j+)if(xi=yj)cij=ci-1j-1+1;bij=1;elseif(ci-1j=cij-1)cij=ci-1j;bij=2;else cij=cij-1; bij=3;return 0;head.h:#ifndef H#define Hint LCSLegth(int m,
21、 int n, char *x, char *y,int* c,int *b);int LCS(int i,int j,char * ,int *b,char * z,int k);#endif运行结果：设计算法求解数字三角形问题，并编程实现。（P80算法实现题34）程序代码：#include iostream#include cstdiousing namespace std;int n,*d;int MaxSum(int i,int j) if(i=n-1) return dij;elseint Sum1=MaxSum(i+1,j);int Sum2=MaxSum(i+1,j+1);if(
22、Sum1Sum2)return Sum1+dij;elsereturn Sum2+dij;int main()/freopen(D:VCMicrosoft Visual StudioMyProjectsexperiment_3Data3input.txt,r,stdin);/freopen(D:VCMicrosoft Visual StudioMyProjectsexperiment_3Data3output.txt,w,stdout);int i,j;cout请输入数字三角形的行数：endl;cinn; d=new int*n; for(i=0;in;i+)di=new intn;cout请输入每一个数：endl;for(i=0;in;i+) for(j=0;j=i;j+) cindij; int max=MaxSum(0,0);cout求得的最大路径的和值为：maxendl;运行结果：四：实验结果的分析与评价（该部分如不够填写，请另加附页）注：实验成绩等级分为（90100分）优，（8089分）良，(70-79分)中，（6069分）及格，（59分）不及格。 下载文档 收藏 分享 赏 0