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

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

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实验原理动态规划的基本思想：动态规划

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

4、的值6实验结果图6-1 n个矩阵连乘问题图6-2应用顺推实现动态规划求解n行m列边数值矩阵最大的路程图6-3 递推实现动态规划求解序列的最小子段和 图6-4 插入加号求最小值7实验体会通过这次实验加深了我对动态规划算法的理解，通过这五个实验使我熟练掌握动态规划算法，使我对动态规划算法，分治法，贪心算法有了区别的认识，动态规划算法融合了分治法和贪心法的优点，更好的解决问题，实验有利于加深理论的理解，非常实用。附：源程序第一题源程序：#include <stdio.h>void main()int d,n,i,j,k,t,r100,m100100; printf("请输入矩阵

5、的个数n:"); scanf("%d",&n); printf("请输入第1个矩阵的行数:"); scanf("%d",&r1); for(i=1;i<=n-1;i+) printf("请输入第%d个矩阵的列数，也是第%d个矩阵的行数:",i,i+1); scanf("%d",&ri+1); printf("请输入第%d个矩阵的列数:",n); scanf("%d",&rn+1); for(i=1;i<

6、=n;i+) mii=0; for(d=1;d<=n-1;d+) for(i=1;i<=n-d+1;i+)j=i+d; mij=mii+mi+1j+ri*ri+1*rj+1;for(k=i+1;k<j;k+)t=mik+mk+1j+ri*rk+1*rj+1;if(t<mij) mij=t; printf("%d个矩阵连乘的乘法次数的最小值为:%d n",n,m1n);第二题源程序：#include "math.h"#include <stdio.h>void main() int n,i,j,t,s; int a505

7、0,l5050,r5050;char st5050; t=time()%1000;srand(t); printf("请输入数字三角形的行数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+

8、) printf(" . "); printf("nn"); for(j=1;j<=36-4*i;j+) printf(" "); for(j=1;j<=i;j+) lij=rand()/1000+1;printf("%4d",lij); rij=rand()/1000+1;printf("%4d",rij); printf("n"); for(j=1;j<=37-4*(n+1);j+) printf(" "); for(j=1;j<

9、;=n+1;j+) printf(" . "); printf("底边nn");for(i=n;i>=1;i-) for(j=1;j<=i;j+) if(ai+1j+lij<ai+1j+1+rij) aij=ai+1j+lij;stij='l' else aij=ai+1j+1+rij;stij='r' printf("n 最短路程为：%d",l11);printf("n 最短路径为：顶点A ");for(j=1,i=1;i<=n;i+) if(stij=&#

10、39;l') printf("L-%d-",lij); else printf("R-%d-",rij);j+;printf("底边。n");第三道题程序：随机产生一个n行m列的整数矩阵,在整数矩阵中寻找从左上角至右下角,每步可向下(D)或向右(R)或斜向右下(O)的一条数值和最小的路径。应用动态规划，即从右下角逐行反推至左上角。确定n,m后，随机产生的整数二维数组a(n,m)作矩阵输出，同时赋给部分和数组b(n,m)。这里数组b(i,j)为点(i,j)到右下角的最小数值和，stm(i,j)是点(i,j)向右（R）或向下（D）

11、或向右下（O）的路标字符数组。 注意到最后一行与最后一列各数只有一个出口,于是由b(n,m)开始向左逐个推出同行的b(n,j),(j=m-1,.,2,1);向上逐个推出同列的b(i,m),(i=n-1,.,2,1)。 b(i,j)与stc(i,j)(i=n-1,.,2,1,j=m-1,.,2,1)的值由同一列其下面的整数b(i+1,j)与同一行其右边的整数b(i,j+1)或其右下方的b(i+1,j+1)的值决定: 首先,作赋值 b(i,j)=yb+b(i+ 1, j + 1): stc(i, j) = "O".(其中变量yb为原b(i,j)的值)。 然后,求 b(i+1,j

12、) 与 b(i,j+1) 的最小值 min。 如果 b(i+1,j+1)>min ,说明前面为b(i,j)赋值不对,作修改: b(i,j)=yb+min 若min 为 b(i+1,j),则 stc(i,j)="D",否则 stc(i,j)="R" 这样反推所得b(1,1)即为所求的最小路径数字和。 为了打印最小路径,利用c数组从上而下操作:先打印a(1,1),i=1,j=1. 若 stc(i,j)="R" 则j增1,即j=j+1,然后打印 "-R-"与右边整数a(i,j); 若 stc(i,j)="

13、D" 则i增1,即i=i+1,然后打印 "-D-"与下面整数a(i,j); 若 stc(i,j)="O" 则i,j均增1,即i=i+1,j=j+1,然后打印 "-O-"与斜向右下整数a(i,j);依此类推,直至打印到终点a(n,m)。第四道题程序：#include <stdio.h>#include <stdlib.h>#include <time.h>void main() int i,j,k,t,n,s,smin,q1000,a1000; t=time(0)%1000;srand(t)

14、; printf(" 序列中n个正负项,请确定n:"); scanf("%d",&n); printf(" 序列的%d个整数为：n ",n); for(i=1;i<=n;i+) t=rand()%(4*n)+10; if(t%2=1) ai=-1*(t-1)/2; else ai=t/2; printf("%d,",ai); smin=1000;q0=0; for(j=1;j<=n;j+) if(qj-1>=0) qj=aj; else qj=qj-1+aj; if(qj<smin)

15、 smin=qj;k=j;printf("n 最小子段和为：%ldn",smin);for(s=0,i=k;i>=1;i-) s+=ai; if(s=smin) break; printf(" 最小子段从序列的第%d项到第%d项。n",i,k);第五道题程序：#include <stdio.h>#include <string.h>void main() char sr16; int n,i,j,k,u,r,b16,t16,c1616; double f1717,d; printf("请输入整数：");

16、scanf("%s",sr); n=strlen(sr); printf("请输入插入的+号个数r："); scanf("%d",&r); if(n<=r) printf(" 输入的整数位数不够或r太大!n "); return; printf("在整数%s中插入%d个+号，使和最小：n",sr,r); for(d=0,j=0;j<=n-1;j+) bj=srj-48; for(i=1;i<=n;i+) for(j=1;j<=r;j+) fij=1e16;for(d=0,j=1;j<=n;j+) d=d*10+bj-1; fj0=d; for(k=1;k<=r;k+) for(i=k+1;i<=n;i+) for(j=k;j<i;j+) for(d=0,u=j+1;u<=