BX110937李建辉算法设计实验六文档格式.docx
- 文档编号:5204871
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:10
- 大小:111.67KB
BX110937李建辉算法设计实验六文档格式.docx
《BX110937李建辉算法设计实验六文档格式.docx》由会员分享,可在线阅读,更多相关《BX110937李建辉算法设计实验六文档格式.docx(10页珍藏版)》请在冰点文库上搜索。
)生疏()
操作技能:
较强(
实验报告:
较好(
成绩:
指导教师:
-
王淮亭
批阅时间:
2014年05月05日
《数据库原理及应用》实验报告-1
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.实验结果
图6-1n个矩阵连乘问题
图6-2应用顺推实现动态规划求解n行m列边数值矩阵最大的路程
■十;
\和冈细朗U^\计尊机幫用亘法和齢诒计谋眸\计諒叽氢迭实那D亡匕口熱吕注与宅畑*三.回TbJJ
图6-3递推实现动态规划求解序列的最小子段和
图6-4插入加号求最小值
7•实验体会
通过这次实验加深了我对动态规划算法的理解,通过这五个实验使我熟练掌握动态规划算法,使我对动态规划算法,分治法,贪心算法有了区别的认识,动态规划算法融合了分治法和贪心法的优点,更好的解决问题,实验有利于加深理论的理解,非常实用。
附:
源程序
第一题源程序:
#inelude<
stdio.h>
voidmain()
{intd,n,i,j,k,t,r[1OO],m[1OO][1OO];
printf(”请输入矩阵的个数n:
"
);
scanf("
%d"
&
n);
printf(”请输入第1个矩阵的行数:
r[1]);
for(i=1;
i<
=n_1;
i++)
{printf("
请输入第%d个矩阵的列数,也是第%d个矩阵的行数:
i,i+1);
&
r[i+1]);
}
printf("
请输入第%d个矩阵的列数:
n);
scanf("
r[n+1]);
=n;
m[i][i]=O;
for(d=1;
d<
d++)
=n_d+1;
{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]);
第二题源程序:
#include"
math.h"
#include<
{intn,i,j,t,s;
inta[50][50],l[50][50],r[50][50];
charst[50][50];
t=time()%1000;
srand(t);
请输入数字三角形的行数n:
scanf("
i<
n;
i++)j=rand();
for(j=1;
j<
=33;
j++)printf("
"
printf("
A\n”);
{for(j=1;
=37-4*i;
=i;
."
printf("
\n\n"
=36-4*i;
j++)
{l[i][j]=rand()/1000+1;
%4d"
l[i][j]);
r[i][j]=rand()/1000+1;
r[i][j]);
\n"
=37-4*(n+1);
j++)printf("
=n+1;
."
printf(”底边\n\n”);
for(i=n;
i>
=1;
i--)
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]=T;
else
{a[i][j]=a[i+1][j+1]+r[i][j];
st[i][j]='
r'
;
\n最短路程为:
%d"
l[1][1]);
\n最短路径为:
顶点A"
for(j=1,i=1;
if(st[i][j]==T)
L-%d-"
{printf("
R-%d-"
j++;
底边。
第三道题程序:
随机产生一个n行m列的整数矩阵,在整数矩阵中寻找从左上角至右下角,每步可向下(D)或向右
(R)或斜向右下(0)的一条数值和最小的路径。
应用动态规划,即从右下角逐行反推至左上角。
确定n,m后,随机产生的整数二维数组a(n,m)
作矩阵输出,同时赋给部分和数组b(n,m)。
这里数组b(i,j)为点(i,j)到右下角的最小数值和,
stm(i,j)是点(i,j)向右(R)或向下(D)或向右下(0)的路标字符数组。
注意到最后一行与最后一列各数只有一个出口,于是由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)与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.
依此类推,直至打印到终点a(n,m)。
第四道题程序:
stdlib.h>
time.h>
{inti,j,k,t,n,s,smin,q[1000],a[1000];
t=time(0)%1000;
printf(”序列中n个正负项,请确定n:
序列的%d个整数为:
\n”,n);
{t=rand()%(4*n)+10;
if(t%2==1)a[i]=-1*(t-1)/2;
elsea[i]=t/2;
%d,"
a[i]);
smin=1000;
q[0]=0;
{if(q[j-1]>
=0)q[j]=a[j];
elseq[j]=q[j-1]+a[j];
if(q[j]<
smin)
{smin=q[j];
k=j;
\n最小子段和为:
%ld\n"
smin);
for(s=0,i=k;
{s+=a[i];
if(s==smin)break;
}
最小子段从序列的第%d项到第%d项。
i,k);
第五道题程序:
string.h>
{charsr[16];
intn,i,j,k,u,r,b[16],t[16],c[16][16];
doublef[17][17],d;
请输入整数:
%s"
sr);
n=strlen(sr);
printf(”请输入插入的+号个数r:
r);
if(n<
=r)
输入的整数位数不够或r太大!
\n"
return;
在整数%s中插入%介+号,使和最小:
sr,r);
for(d=0,j=0;
b[j]=sr[j]-48;
=r;
f[i][j]=1e16;
for(d=0,j=1;
{d=d*10+b[j-1];
f[j][0]=d;
for(k=1;
for(i=k+1;
for(j=k;
i;
-8
{for(d=0,u=j+1;
u<
u++)
d=d*10+b[u-1];
if(f[i][k]>
f[j][k-1]+d)
{f[i][k]=f[j][k-1]+d;
c[i][k]=j;
t[r]=c[n][r];
for(k=r-1;
k>
k--)
t[k]=c[t[k+1]][k];
t[0]=0;
t[r+1]=n;
=r+1;
{for(u=t[k-1]+1;
=t[k];
%c"
sr[u-1]);
if(k<
r+1)
+"
=%.0f\n”,f[n][r]);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- BX110937 李建辉 算法 设计 实验