电子信息学院
实验报告书
评语:
实验态度:认真（）一般（）较差（)
实验结果:正确（）部分止确（）错（)
实验理论:掌握（）熟悉（）了解（）生疏（）操作技能:较强（）一般（）较差（)
实验报告:较好（）一般（）较差（)
成绩：指导教师：-王淮亭
批阅时间：2014年05月05日
1. 实验目的
(1) 初步掌握动态规划算法
(2)
能够运用动态规划的思想解决实际问题，如矩阵连乘问题等
2. 实验要求
(1)
n 个矩阵连乘问题。
(2) 应用顺推实现动态规划求解 n 行m 列边数值矩阵最大的路程，已知n 行m 列的边数值矩阵, 每一个点
可向右或向下两个去向，试求左上角顶点到右下角顶点的所经边数值和最大的路程。 (3)
求解点数值矩阵最小路径，随机产生一个
n 行m 列的整数矩阵，在整数矩阵中寻找从左上
角至右下角,每步可向下(D)或向右(R)或斜向右下(0)的一条数值和最小的路径。 (4) 应用递推实现动态规划求解序列的最小子段和。 (5)
插入加号求最小值
，在一个n 位整数a 中插入r 个加号，将它分成r+1个整数，找出一
种加号的插入方法，使得这 r+1个整数的和最小。
3. 实验原理
动态规划的基本思想：动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上 它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题 被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这 在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个 问题的最优解，动态规划则可以处理不具备贪心准则的问题
4. 实验设备
PC 机
5. 实验步骤
(1) 刻画最优解的结构特性； (2) 递归定义最优解值；
(3) 以自底向上方式计算最优解值； (4)
根据计算得到的信息构造一个最优解。
其中，第(1 )至(3)步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值
6. 实验结果
“
行劇
法加 P
白白白白詞 1
巨巨巨巨民
旳戈买BB^f ¥
胆2LX
證
序年
入入
入
辎0
前前前融淨
■十；\和冈细朗U^\计尊机幫用亘法和齢诒计谋眸\计諒叽氢迭实那D 亡匕口熱吕注与宅畑*
三.回
TbJJ
7 •实验体会
通过这次实验加深了我对动态规划算法的理解，通过这五个实验使我熟练掌握动态规划算法， 使我对动态规划算法，分治法，贪心算法有了区别的认识，动态规划算法融合了分治法和贪心法的 优点，更好的解决问题，实验有利于加深理论的理解，非常实用。
附：源程序
第一题源程序： #in elude void mai n()
{in t d,n ,i,j,k,t,r[1OO],m[1OO][1OO]; printf (”
请输入矩阵的个数 n:");
2
1
确
请4
自
c
-&
列0 整28
九序yt 丁4,亦ke -2
巖
y 需。子子an
个2--- Press
图6-1 n 个矩阵连乘问题
图6-2应用顺推实现动态规划求解
n 行m 列边数值矩阵最大的路程
4
24,
图6-3递推实现动态规划求解序列的最小子段和
图6-4插入加号求最小值
int a[50][50],l[50][50],r[50][50];char st[50][50]; t=time()%1000;sra nd(t);
prin tf(" 请输入数字三角形的行数n:"); sca nf("%d",&n);
for(i=1;i for(j=1;j<=33;j++) pri ntf(" ");pri ntf(" A \n ”);
for(i=1;i<=n ;i++)
{for(j=1;j<=37-4*i;j++) pri ntf("");
for(j=1;j<=i;j++) pri ntf(" . "); prin tf("\n\n");
for(j=1;j<=36-4*i;j++) pri ntf("");
for(j=1;j<=i;j++)
{l[i][j]=ra nd()/1000+1;pri ntf("%4d",l[i][j]);
r[i][j]=ra nd()/1000+1;pri ntf("%4d",r[i][j]);} prin tf("\n");}
for(j=1;j<=37-4*(n+1);j++) printf("");
for(j=1;j<=n+1;j++) printf(".");
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][j]=a[i+1][j]+l[i][j];st[i][j]=T;}
else
{a[i][j]=a[i+1][j+1]+r[i][j];st[i][j]='r';}
}
prin tf("\n 最短路程为：%d",l[1][1]);
prin tf("\n 最短路径为：顶点A ");
