bx110937李建辉算法设计实验六 -

《bx110937李建辉算法设计实验六 -》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、电子信息学院实验报告书课程名：算法设计与分析题目：实验六动态规则实验类别【设计型】班级：BX1109学号：37姓名：李建辉评语：实验态度：认真（）一般（）较差（）实验结果：正确（）部分正确（）错（）实验理论：掌握（）熟悉（）了解（）生疏（）操作技能：较强（）一般（）较差（）实验报告：较好（）一般（）较差（）成绩：指导教师：王淮亭批阅时间：2014年05月05日《数据库原理及应用》实验报告-81．实验目的（1）初步掌握动态规划算法（2）能够运用动态规划的思想解决实际问题，如矩阵连乘问题等2．实验要求（1）n个矩阵连乘问题。（2

2、）应用顺推实现动态规划求解n行m列边数值矩阵最大的路程，已知n行m列的边数值矩阵，每一个点可向右或向下两个去向，试求左上角顶点到右下角顶点的所经边数值和最大的路程。（3）求解点数值矩阵最小路径，随机产生一个n行m列的整数矩阵,在整数矩阵中寻找从左上角至右下角,每步可向下(D)或向右(R)或斜向右下(O)的一条数值和最小的路径。（4）应用递推实现动态规划求解序列的最小子段和。（5）插入加号求最小值，在一个n位整数a中插入r个加号，将它分成r+1个整数，找出一种加号的插入方法，使得这r+1个整数的和最小。3．实验原理动态规划的基

3、本思想：动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题4．实验设备PC机5．实验步骤（1）刻画最优解的结构特性；（2）递归定义最优解值；（3）以自底向上方式计算最优解值；（4）根据计算得到的信息构造一个最

4、优解。其中，第（1）至（3）步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值6．实验结果《数据库原理及应用》实验报告-8图6-1n个矩阵连乘问题图6-2应用顺推实现动态规划求解n行m列边数值矩阵最大的路程图6-3递推实现动态规划求解序列的最小子段和图6-4插入加号求最小值7．实验体会通过这次实验加深了我对动态规划算法的理解，通过这五个实验使我熟练掌握动态规划算法，使我对动态规划算法，分治法，贪心算法有了区别的认识，动态规划算法融合了分治法和贪心法的优点，更好的解决问题，实验有利于加深理论的理解，非常实用。附：源程序

5、第一题源程序：#includevoidmain(){intd,n,i,j,k,t,r[100],m[100][100];printf("请输入矩阵的个数n:");《数据库原理及应用》实验报告-8scanf("%d",&n);printf("请输入第1个矩阵的行数:");scanf("%d",&r[1]);for(i=1;i<=n-1;i++){printf("请输入第%d个矩阵的列数，也是第%d个矩阵的行数:",i,i+1);scanf("%d",&r[i+1]);}printf("请输入第%d个矩阵的列数

6、:",n);scanf("%d",&r[n+1]);for(i=1;i<=n;i++)m[i][i]=0;for(d=1;d<=n-1;d++)for(i=1;i<=n-d+1;i++){j=i+d;m[i][j]=m[i][i]+m[i+1][j]+r[i]*r[i+1]*r[j+1];for(k=i+1;k

7、][n]);}第二题源程序：#include"math.h"#includevoidmain(){intn,i,j,t,s;《数据库原理及应用》实验报告-8inta[50][50],l[50][50],r[50][50];charst[50][50];t=time()%1000;srand(t);printf("请输入数字三角形的行数n:");scanf("%d",&n);for(i=1;i

8、for(i=1;i<=n;i++){for(j=1;j<=37-4*i;j++)printf("");for(j=1;j<=i;j++)printf(".");printf("");for(j=1;j<=36-4*i;j++)printf("");for(j=1;j<=i;j++)