实验报告Word格式.docx
《实验报告Word格式.docx》由会员分享，可在线阅读，更多相关《实验报告Word格式.docx（22页珍藏版）》请在冰点文库上搜索。
（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：
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<
iostream>
usingnamespacestd;
voidMerge（intx[],inty[],intl,intm,intr）{
inti=l,
j=m+1,
k=l;
while（（i<
=m）&
&
（j<
=r））{
if（x[i]<
x[j]）
y[k++]=x[i++];
else
y[k++]=x[j++];
}
if（i>
m）{
while（j<
=r）
else{
while（i<
=m）
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+s<
len_x）
Merge（x,y,p,p+s-1,len_x-1）;
y[p]=x[p++];
voidMergeSort（intx[],intlen_x）{
int*y=newint[len_x];
ints=1;
while（s<
len_x）{
MergePass（x,y,len_x,s）;
s+=s;
MergePass（y,x,len_x,s）;
//当s>
len_x/2时，MergePass便只执行while循环外的那一段程序
//所以最后必定能将最后结果复制到x数组
intmain（）{
intlen_x;
cout<
<
"
请输入待排序整数个数：
;
cin>
>
len_x;
int*x=newint[len_x];
请输入待排序整数，以空格隔开！
endl;
for（inti=0;
i<
len_x;
i++）{
x[i];
MergeSort（x,len_x）;
x[i]<
"
return0;
实验一第二题：
/***********************************************/
/*此程序为算法设计与分析实验一第二题*/
/*实现中位数线性选择*/
//交换数组中的两个元素
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]<
x&
i<
r）;
while（a[--j]>
j>
p）;
=j）
break;
Swap（a,i,j）;
returnj;
//冒泡排序
voidBubbleSort（int*a,intp,intr）{
for（inti=p;
=r-1;
for（intj=p;
j<
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];
=（r-p-4）/5;
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<
returnSelect（a,p,i,k）;
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;
14;
intk=Select（a,0,12,i）;
第"
i<
大数为：
k<
实验二第一题：
/******************************************************
*该程序为算法设计与分析实验二第二小题矩阵连乘问题
*此程序遵照书本动态规划思想
*****************************************************/
voidMatrixChain（int*p,intp_len,int**s）{
//创建m二维数组
int**m=newint*[p_len];
p_len;
m[i]=newint[p_len];
i++）
m[i][i]=0;
for（intr=2;
r<
r++）{
p_len-r+1;
intj=i+r-1;
//先计算k=i时
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
//再计算当i<
j时
for（intk=i+1;
k<
j;
k++）{
intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if（t<
m[i][j]）{
m[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）;
MultipyA"
toA"
j<
breakinA"
s[i][j]<
voidMatrix（int*p,intp_len）{
//创建s二维数组
int**s=newint*[p_len];
s[i]=newint[p_len];
MatrixChain（p,p_len,s）;
TraceBack（s,1,p_len-1）;
intp[9]={30,35,25,20,30,5,30,5,25};
Matrix（p,9）;
实验二第二题：
/*************************************************
*此程序为算法分析与设计实验二第二题而写
*依照书本求字符串最长公共子序列动态规划算法
*************************************************/
string.h>
voidLcsLength（char*x,char*y,int**b）{
intm=strlen（x）;
intn=strlen（y）;
int**c=newint*[m+1];
m+1;
c[i]=newint[n+1];
=m;
c[i][0]=0;
=n;
c[0][i]=0;
for（intj=1;
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;
c[i][j]=c[i][j-1];
b[i][j]=3;
voidLcs（inti,intj,char*x,int**b）{
if（i==0||j==0）
if（b[i][j]==1）{
Lcs（i-1,j-1,x,b）;
x[i-1];
elseif（b[i][j]==2）
Lcs（i-1,j,x,b）;
Lcs（i,j-1,x,b）;
voidMostLcs（char*x,char*y）{
int**b=newint*[m+1];
b[i]=newint[n+1];
LcsLength（x,y,b）;
Lcs（m,n,x,b）;
char*x=（char*）"
BCDDACB"
char*y=（char*）"
CDBBAB"
x序列为：
x<
y序列为：
y<
最长公共子序列为：
MostLcs（x,y）;
}
实验三第一题：
/*******************************************************
*此程序为算法分析与设计实验三第一题
*此程序依照书本求单元最短路径的dijkstra算法
******************************************************/
#include<
usingnamespacestd;
constintMAX=100;
voidDijkstra（intv,intnode_num,int**a,int*dist,int*prev）{
intn=node_num-1;
if（v<
0||v>
n）
bool*s=newbool[node_num];
//初始化
dist[i]=a[v][i];
s[i]=false;
if（dist[i]==MAX）
prev[i]=0;
prev[i]=v;
dist[v]=0;
s[v]=true;
n;
inttemp=MAX;
intu=v;
//寻找最短路径节点
if（（!
s[j]）&
（dist[j]<
temp））{
u=j;
temp=dist[j];
s[u]=true;
//更新与u节点相连的节点的dist值
（a[u][j]<
MAX））{
intnewdist=dist[u]+a[u][j];
if（newdist<
dist[j]）{
dist[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];
//输出最短路径
最短路径：
v<
->
node_num-1）
load[++j]<
t<
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}
};
//将邻接矩阵传递给指针数组
12;
pa[i]=a[i];
DijkstraGetLoad（pa,12,0,11）;
八、实验数据及结果分析：
实验一第一题：
九、实验结论：
（1）使用合并排序算法对数列完成了排序。
（2）使用分治法求出了第K小元素。
实验二：
（1）利用动态规划算法解决了矩阵连乘问题。
（2）利
升级会员 