计算机算法设计分析实验2.doc

下载文档 降价啦

4
0
约8.02千字
约 5页
2016-10-17 发布于浙江
举报
版权申诉
保障服务

计算机算法设计分析实验2.doc

1、本文档共5页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

计算机算法设计分析实验2

实验2代码截图和运行结果截图网工二陈衍席25 矩阵连乘代码: #include stdafx.h #include iostream using namespace std; const int L = 7; int LookupChain(int i,int j,int **m,int **s,int *p); int MemoizedMatrixChain(int n,int **m,int **s,int *p); void Traceback(int i,int j,int **s);//构造最优解 int main() { int p[L]={30,35,15,5,10,20,25}; int **s = new int *[L]; int **m = new int *[L]; for(int i=0;iL;i++) { s[i] = new int[L]; m[i] = new int[L]; } cout矩阵的最少计算次数为：MemoizedMatrixChain(6,m,s,p)endl; cout矩阵最优计算次序为：endl; Traceback(1,6,s); return 0; } int MemoizedMatrixChain(int n,int **m,int **s,int *p) { for(int i=1; i=n; i++) { for(int j=1; j=n; j++) { m[i][j]=0; } } return LookupChain(1,n,m,s,p); } int LookupChain(int i,int j,int **m,int **s,int *p) { if(m[i][j]0) { return m[i][j]; } if(i==j) { return 0; } int u = LookupChain(i,i,m,s,p) + LookupChain(i+1,j,m,s,p)+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1; kj; k++) { int t = LookupChain(i,k,m,s,p) + LookupChain(k+1,j,m,s,p) + p[i-1]*p[k]*p[j]; if(tu) { u=t; s[i][j] = k; } } m[i][j] = u; return u; } void Traceback(int i,int j,int **s) { if(i==j) return; Traceback(i,s[i][j],s); Traceback(s[i][j]+1,j,s); coutMultiply Ai,s[i][j]; cout and A(s[i][j]+1),jendl; } 程序运行图： 0-1背包问题代码： #includestdio.h int V[200][200];//前i个物品装入容量为j的背包中获得的最大价值 int max(int a,int b) { if(a=b) return a; else return b; } int KnapSack(int n,int w[],int v[],int x[],int C) { int i,j; for(i=0;i=n;i++) V[i][0]=0; for(j=0;j=C;j++) V[0][j]=0; for(i=0;i=n-1;i++)