实验报告.docx
《实验报告.docx》由会员分享，可在线阅读，更多相关《实验报告.docx（22页珍藏版）》请在冰点文库上搜索。
实验报告
电子科技大学示范性软件学院
标准实验报告
（实验）课程名称算法分析与设计
电子科技大学教务处制表
电子科技大学
实验报告
学生姓名：
学号：
指导教师：
一、实验室名称：
主楼A2-412实验室
二、实验项目名称：
实验项目一：
分治和递归算法实现
实验项目二：
动态规划算法实现
实验项目三：
贪心算法实现
三、实验原理：
实验项目一：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。
然后再把有序子序列合并为整体有序序列。
在求解一个输入规模为n，而n的取值又很大的问题时，直接求解往往非常困难。
这时，可以先分析问题本身所具有的某些特性，然后从这些特性出发，选择某些适当的设计策略来求解。
这种方法，就是所谓的分治法。
实验项目二：
动态规划的基本模型如下：
（1）确定问题的决策对象。
（2）对决策过程划分阶段。
（3）对各阶段确定状态变量。
（4）根据状态变量确定费用函数和目标函数。
（5）建立各阶段状态变量的转移过程，确定状态转移方程。
实验项目三：
贪婪算法及贪婪算法可解决的问题通常大部分都有如下的特性:
（1）有一个以最优方式来解决的问题。
为了构造问题的解决方案,有一个候选的对象的集合：
比如不同面值的硬币。
（2）随着算法的进行,将积累起其它两个集合：
一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。
（3）有一个函数来检查一个候选对象的集合是否提供了问题的解答。
该函数不考虑此时的解决方法是否最优。
（4）还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。
和上一个函数一样,此时不考虑解决方法的最优性。
（5）选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
（6）最后,目标函数给出解的值。
为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法一步一步的进行。
起初,算法选出的候选对象的集合为空。
接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。
如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。
每一次都扩充集合，并检查该集合是否构成解。
如果贪婪算法正确工作，那么找到的第一个解通常是最优的
四、实验目的：
实验项目一：
加深对分治和递归算法原理及实现过程的理解。
实验项目二：
加深对动态规划算法原理及实现过程的理解。
实验项目三：
加深对贪心算法原理及实现过程的理解。
五、实验内容：
实验项目一：
（1）利用合并排序算法对字符数组a[]={12,1,8,5,6,4,5}从小到大排序。
（2）用分治算法实现元素选择。
使用分治算法编程，求解线性序列中第k小元素。
A．给定线形序列集中n个元素和一个整数k，1<=k<=n。
输出这n个元素中第k小元素的值及其位置。
B．简述该算法的原理，步骤。
对该算法与直接排序查找进行比较。
C．编写并调试程序
测试要求：
元素个数不少于10，分三种情况：
k=1,k=n;k=中位数
实验项目二：
用动态规划实现矩阵链乘法问题；用动态规划算法求解最长公共子序列问题。
（1）现在要求计算一个由8个矩阵组成的乘法，A1*A2*A3*A4*A5*A6*A7*A8。
已知矩阵的维数如下，要求给矩阵添上七个括号使得基本乘法运算次数最少，并给出其运算次数。
A1：
30*35
A2：
35*25
A3：
25*20
A4：
20*30
A5：
30*5
A6：
5*30
A7：
30*5
A8：
5*25
（2）若给定序列
，则另一序列
，是X的子序列是指在一个严格递增下标序列｛i1,i2,…,ik｝使得对于所有j=1,2,…,k有;zj=xij。
例如Z={B,C,D,B}是序列X=｛A,B,C,B,D,A,B｝的子序列，相应的递增下标序列为{2,3,5,7}.给定2个序列X,Y，当另序列Z即是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
给定2个序列X=｛B,C,D,D,A,C,B｝,Y={C,D,B,B,A,B},编写动态规划算法找出X,Y的最长公共子序列。
实验项目三：
（1）理解Dijkstra算法的原理，用Dijkstra算法编程找出从s到t的最短路径，图中每条边旁边的数字为此边的长度。
（2）根据给定的N个权值构造一棵哈夫曼树，要求输出每个节点的权值、父节点编号和左右孩子的编号，并输出相应的哈夫曼编码。
哈夫曼树，即最优树，是带权路径长度最短的树。
有着广泛的应用。
在解决某些判定问题上，及字符编码上，有着重要的价值。
哈夫曼最早给出如下算法，称为哈夫曼算法：
1）根据给定的N个权值 W1，W2，W3，……，Wn ，构成N棵二叉树的集合F= T1，T2，T3，……，Tn ，其中每棵二叉树T1只有一个带权为WI的根结点，其左右子树均空。
2）在F中选出两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左右子树上的根结点的权值之和。
3）在F中删除这两棵树，同时将新得到的加到F之中。
重复
（2）和（3），直至F中只剩一个为止。
（3）设有n个独立的作业｛1，2，…n｝，由m台相同的机器进行加工处理。
作业i所需时间为ti.现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。
任何作业不能拆分成更小的子作业。
多机调度问题要求给出一种作业调度方案，使得所给的n个作业在尽可能3的时间内由m台机器加工处理完成。
六、实验器材（设备、元器件）：
硬件：
PC机一台
软件：
VC++2005
七、实验步骤：
实验一：
第1题：
/********************************************/
/*此程序为算法分析与设计课程实验一第一题*/
/*此合并排序乃遵照课本中消除递归后的合并方式*/
/********************************************/
#include
usingnamespacestd;
voidMerge（intx[],inty[],intl,intm,intr）{
inti=l,
j=m+1,
k=l;
while（（i<=m）&&（j<=r））{
if（x[i]y[k++]=x[i++];
else
y[k++]=x[j++];
}
if（i>m）{
while（j<=r）
y[k++]=x[j++];
}
else{
while（i<=m）
y[k++]=x[i++];
}
}
voidMergePass（intx[],inty[],intlen_x,ints）{
intp=0;
//intlen_x=strlen（x）;
//此循环先合并再增加i值，故先预留2*s个字符
while（p<=（len_x-2*s-1））{
Merge（x,y,p,p+s-1,p+2*s-1）;
p+=（2*s）;
}
//i值最后一次加2*s后，剩余字符必定小于2*s个
//但还需检验是否小于s个
if（p+sMerge（x,y,p,p+s-1,len_x-1）;
else{
while（py[p]=x[p++];
}
}
voidMergeSort（intx[],intlen_x）{
//intlen_x=strlen（x）;
int*y=newint[len_x];
ints=1;
while（sMergePass（x,y,len_x,s）;
s+=s;
MergePass（y,x,len_x,s）;
s+=s;
//当s>len_x/2时，MergePass便只执行while循环外的那一段程序
//所以最后必定能将最后结果复制到x数组
}
}
intmain（）{
intlen_x;
cout<<"请输入待排序整数个数：
";
cin>>len_x;
int*x=newint[len_x];
cout<<"请输入待排序整数，以空格隔开！
"<for（inti=0;icin>>x[i];
}
MergeSort（x,len_x）;
for（inti=0;icout<}
cout<return0;
}
实验一第二题：
/***********************************************/
/*此程序为算法设计与分析实验一第二题*/
/*实现中位数线性选择*/
/***********************************************/
#include
usingnamespacestd;
//交换数组中的两个元素
voidSwap（int*a,inti,intj）{
inttemp=a[i];
a[i]=a[j];
a[j]=temp;
}
//以x为轴划分数组
intPartition（int*a,intp,intr,intx）{
inti=p-1;
intj=r+1;
while
（1）{
while（a[++i]while（a[--j]>x&&j>p）;
if（i>=j）
break;
Swap（a,i,j）;
}
returnj;
}
//冒泡排序
voidBubbleSort（int*a,intp,intr）{
for（inti=p;i<=r-1;i++）{
for（intj=p;j<=r-1;j++）{
if（a[j]>a[j+1]）
Swap（a,j,j+1）;
}
}
}
//核心部分，选择第k小元素
intSelect（int*a,intp,intr,intk）{
if（r-p<5）{
BubbleSort（a,p,r）;
returna[p+k-1];
}
for（inti=0;i<=（r-p-4）/5;i++）{
ints=p+5*i;
BubbleSort（a,s,s+4）;
Swap（a,p+i,s+2）;
}
//选择中位数中的中位数
intx=Select（a,p,p+（r-p-4）/5,（r-p+6）/10）;
inti=Partition（a,p,r,x）;
intj=i-p+1;//计算划分后子数组元素个数
if（k<=j）
returnSelect（a,p,i,k）;
else
returnSelect（a,i+1,r,k-j）;
}
intmain（）{
inta[13]={5,4,3,2,1,8,9,10,6,7,12,13,11};
for（inti=1;i<14;i++）{
intk=Select（a,0,12,i）;
cout<<"第"<"<}
return0;
}
实验二第一题：
/******************************************************
*该程序为算法设计与分析实验二第二小题矩阵连乘问题
*此程序遵照书本动态规划思想
*****************************************************/
#include
usingnamespacestd;
voidMatrixChain（int*p,intp_len,int**s）{
//创建m二维数组
int**m=newint*[p_len];
for（inti=0;im[i]=newint[p_len];
}
for（inti=0;im[i][i]=0;
for（intr=2;rfor（inti=1;iintj=i+r-1;
//先计算k=i时
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
//再计算当ifor（intk=i+1;kintt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if（tm[i][j]=t;
s[i][j]=k;
}
}
}
}
}
voidTraceBack（int**s,inti,intj）{
//cout<<"traceback"<if（i==j）
return;
TraceBack（s,i,s[i][j]）;
TraceBack（s,s[i][j]+1,j）;
cout<<"MultipyA"<}
voidMatrix（int*p,intp_len）{
//创建s二维数组
int**s=newint*[p_len];
for（inti=0;is[i]=newint[p_len];
}
MatrixChain（p,p_len,s）;
TraceBack（s,1,p_len-1）;
}
intmain（）{
intp[9]={30,35,25,20,30,5,30,5,25};
Matrix（p,9）;
return0;
}
实验二第二题：
/*************************************************
*此程序为算法分析与设计实验二第二题而写
*依照书本求字符串最长公共子序列动态规划算法
*************************************************/
#include
#include
usingnamespacestd;
voidLcsLength（char*x,char*y,int**b）{
intm=strlen（x）;
intn=strlen（y）;
int**c=newint*[m+1];
for（inti=0;ic[i]=newint[n+1];
}
for（inti=1;i<=m;i++）
c[i][0]=0;
for（inti=1;i<=n;i++）
c[0][i]=0;
for（inti=1;i<=m;i++）{
for（intj=1;j<=n;j++）{
if（x[i-1]==y[j-1]）{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
elseif（c[i-1][j]>=c[i][j-1]）{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
}
voidLcs（inti,intj,char*x,int**b）{
if（i==0||j==0）
return;
if（b[i][j]==1）{
Lcs（i-1,j-1,x,b）;
cout<}
elseif（b[i][j]==2）
Lcs（i-1,j,x,b）;
else
Lcs（i,j-1,x,b）;
}
voidMostLcs（char*x,char*y）{
intm=strlen（x）;
intn=strlen（y）;
int**b=newint*[m+1];
for（inti=0;ib[i]=newint[n+1];
}
LcsLength（x,y,b）;
Lcs（m,n,x,b）;
}
intmain（）{
char*x=（char*）"BCDDACB";
char*y=（char*）"CDBBAB";
cout<<"x序列为：
"<cout<<"y序列为：
"<cout<<"最长公共子序列为：
";
MostLcs（x,y）;
cout<return0;
}
实验三第一题：
/*******************************************************
*此程序为算法分析与设计实验三第一题
*此程序依照书本求单元最短路径的dijkstra算法
******************************************************/
#include
usingnamespacestd;
constintMAX=100;
voidDijkstra（intv,intnode_num,int**a,int*dist,int*prev）{
intn=node_num-1;
if（v<0||v>n）
return;
bool*s=newbool[node_num];
//初始化
for（inti=1;i<=n;i++）{
dist[i]=a[v][i];
s[i]=false;
if（dist[i]==MAX）
prev[i]=0;
else
prev[i]=v;
}
dist[v]=0;
s[v]=true;
for（inti=1;iinttemp=MAX;
intu=v;
//寻找最短路径节点
for（intj=1;j<=n;j++）{
if（（!
s[j]）&&（dist[j]u=j;
temp=dist[j];
}
}
s[u]=true;
//更新与u节点相连的节点的dist值
for（intj=1;j<=n;j++）{
if（（!
s[j]）&&（a[u][j]intnewdist=dist[u]+a[u][j];
if（newdistdist[j]=newdist;
prev[j]=u;
}
}
}
}
}
//该函数由于获取从v到t的最短路径
voidDijkstraGetLoad（int**a,intnode_num,intv,intt）{
int*dist=newint[node_num];
int*prev=newint[node_num];
Dijkstra（v,node_num,a,dist,prev）;
按倒序将节点存入数组
inti=t,j=node_num-1;
//存储最短路径节点
int*load=newint[node_num];
while（prev[i]!
=v）{
load[j--]=prev[i];
i=prev[i];
}
//输出最短路径
cout<<"最短路径：
"<";
while（jcout<";
cout<}
intmain（）{
int*pa[12];
//创建邻接矩阵
inta[12][12]={
{0,15,4,7,MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX},
{15,0,7,MAX,15,12,MAX,MAX,MAX,MAX,MAX,MAX},
{4,7,0,16,MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX},
{7,MAX,0,MAX,8,MAX,MAX,MAX,26,MAX,MAX,MAX},
{MAX,15,16,8,0,20,18,MAX,30,MAX,MAX,MAX},
{MAX,12,MAX,MAX,20,0,MAX,MAX,MAX,30,MAX,MAX},
{MAX,MAX,MAX,MAX,18,MAX,0,3,MAX,16,MAX,MAX},
{MAX,MAX,MAX,MAX,MAX,MAX,3,0,7,MAX,MAX,MAX},
{MAX,MAX,MAX,26,30,MAX,MAX,7,0,5,15,MAX},
{MAX,MAX,MAX,MAX,MAX,MAX,16,MAX,5,0,MAX,20},
{MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX,15,MAX,0,9},
{MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX,20,9,MAX}
};
//将邻接矩阵传递给指针数组
for（inti=0;i<12;i++）{
pa[i]=a[i];
}
DijkstraGetLoad（pa,12,0,11）;
return0;
}
八、实验数据及结果分析：
实验一第一题：
实验一第二题：
实验二第一题：
实验二第二题：
实验三第一题：
九、实验结论：
实验一：
（1）使用合并排序算法对数列完成了排序。
（2）使用分治法求出了第K小元素。
实验二：
（1）利用动态规划算法解决了矩阵连乘问题。
（2）利
升级会员 