实验报告32014110451余双

《实验报告32014110451余双》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验编号：3四川师大《算法设计与分析》实验报告2016年5月1日计算机科学学院14级4班实验名称：动态规划及其应用姓名：余双学号：2014110451指导老师：__苏菡__实验成绩:_____实验一动态规划及其应用一．实验目的及要求目的要求：（1）理解动态规划算法的概念和基本要素，并能和分治法进行比较。（2）掌握设计动态规划算法的步骤，并编程实现有关算法。（3）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。二．实验内容（1）编程实现矩阵连乘问题的求解。（2）编程实现最大子段和问题的求解（分别采用分治

2、法和动态规划法求解）。（3）编程实现0－1背包问题的求解。（4）设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。（5）编程实现最长公共子序列(LCS)问题的求解。（6）设计算法求解数字三角形问题，并编程实现。（P80算法实现题3－4）（7）设计算法求解独立任务最优调度问题，并编程实现。问题描述：欧诺个2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai>=bi,而对于某些j,j不等于i，有aj

3、讲一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，是的这2台机器处理完这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题完成。主要仪器设备及软件（1）PC机（2）TC、VC++、Java等任一编程语言一．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加

4、附页）（1）编程实现矩阵连乘问题的求解。程序代码：main.cpp#include#include"head.h"usingnamespacestd;intmain(){inti,n,*p;cout<<"请输入矩阵的个数："<>n;p=newint[n+1];cout<<"请输入矩阵的维数(相邻矩阵的行列相等，只输入一次就行！)";for(i=0;i<=n;i++){cin>>p[i];}int**m,**s;m=newint*[n+1];s=newint*[n+1];for(i=1;i<=n;i++)

5、{m[i]=newint[n+1];s[i]=newint[n+1];}MatrixChain(p,n,m,s);TraceBack(1,n,s);return0;}MatrixChain.cpp#include#include"head.h"usingnamespacestd;voidMatrixChain(int*p,intn,int**m,int**s){inti,j,r,k;for(i=1;i<=n;i++){m[i][i]=0;s[i][i]=0;}for(r=2;r<=n;r++){for(i=1;i

6、+){j=i+r-1;if(j<7){m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(k=i+1;k#include"head.h"usingnamespacestd;voidTraceBack(inti,intj,

7、int**s){if(i==j){return;}TraceBack(i,s[i][j],s);TraceBack(s[i][j]+1,j,s);cout<<"MultiplyA"<

8、**s);#endif//HEAD_H_INCLUDED运行结果：（2）编程实现最大子段和问题的求解（分别采用分治法和动态规划法求解）。分治法：main.cpp:#