实用标准文案电子信息学院实验报告书：算法设计与分析名课程题目：实验六动态则实验类别【设计型】班级：BX1109学号：37姓名：李建辉评语：实验态度：认真（）一般（）较差（）实验结果：正确（）部分正确（）错（）实验理论：掌握（）熟悉（）了解（）生疏（）操作技能：较强（）一般较差（）实验报告：较好（）一般（）较差（）成绩：指导教师：王淮亭实用标准文案1．实验目的（1）初步掌握动态规划算法（2）能够运用动态规划的思想解决实际问题，如矩阵连乘问题等2．实验要求（1）n个矩阵连乘问题。（2）应用顺推实现动态规划求解n行m列边数值矩阵最大的路程，已知n行m列的边数值矩阵，每一个点可向右或向下两个去向，试求左上角顶点到右下角顶点的所经边数值和最大的路程。（3）求解点数值矩阵最小路径，随机产生一个n行m列的整数矩阵,在整数矩阵中寻找从左上角至右下角,每步可向下(D)或向右(R)或斜向右下(O)的一条数值和最小的路径。（4）应用递推实现动态规划求解序列的最小子段和。（5）插入加号求最小值，在一个n位整数a中插入r个加号，将它分成r+1个整数，找出一种加号的插入方法，使得这r+1个整数的和最小。3．实验原理动态规划的基本思想：动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题4．实验设备PC机5．实验步骤（1）刻画最优解的结构特性；（2）递归定义最优解值；（3）以自底向上方式计算最优解值；（4）根据计算得到的信息构造一个最优解。其中，第（1）至（3）步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值6．实验结果精彩文档．实用标准文案图6-1n个矩阵连乘问题图6-2应用顺推实现动态规划求解n行m列边数值矩阵最大的路程图6-3递推实现动态规划求解序列的最小子段和图6-4插入加号求最小值7．实验体会通过这次实验加深了我对动态规划算法的理解，通过这五个实验使我熟练掌握动态规划算法，使我对动态规划算法，分治法，贪心算法有了区别的认识，动态规划算法融合了分治法和贪心法的优点，更好的解决问题，实验有利于加深理论的理解，非常实用。附：源程序第一题源程序：#include<stdio.h>voidmain(){intd,n,i,j,k,t,r[100],m[100][100];瀠楲瑮?请输入矩阵的个数n:);精彩文档．实用标准文案scanf(%d,&n);瀠楲瑮?请输入第1个矩阵的行数:);scanf(%d,&r[1]);for(i=1;i<=n-1;i++)?灻楲瑮?请输入第%d个矩阵的列数，也是第%d个矩阵的行数:,i,i+1);scanf(%d,&r[i+1]);}瀠楲瑮?请输入第%d个矩阵的列数:,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<j;k++){t=m[i][k]+m[k+1][j]+r[i]*r[k+1]*r[j+1];if(t<m[i][j])m[i][j]=t;}}printf(%d个矩阵连乘的乘法次数的最小值为:%d\n,n,m[1][n]);}第二题源程序：#includemath.h#include<stdio.h>voidmain(){intn,i,j,t,s;精彩文档．实用标准文案inta[50][50],l[50][50],r[50][50];charst[50][50];t=time()_x0010_00;srand(t);牰湩晴尨请输入数字三角形的行数n:);scanf(%d,&n);for(i=1;i<n;i++)j=rand();for(j=1;j<=33;j++)printf();printf(A\n);for(i=1;i<=n;i++){for(j=1;j<=37-4*i;j++)printf();for(j=1;j<=i;j++)printf(.);printf(\\n);for(j=1;j<=36-4*i;j++)printf();for(j=1;j<=i;j++){l[i][j]=rand()/1000+1;printf(M,l[i][j]);r[i][j]=rand()/1000+1;printf(M,r[i][j]);}printf(\);}for(j=1;j<=37-4*(n+1);j++)printf();for(j=1;j<=n+1;j++)printf(.);牰湩晴尨底边\n\n);for(i=n;i>=1;i--){for(j=1;j<=i;j++)if(a[i+1][j]+l[i][j]<a[i+1][j+1]+r[i][j]){a[i][j]=a[i+1][j]+l[i][j];st[i][j]='l';}else{a[i][j]=a[i+1][j+1]+r[i][j];st[i]...