实验报告.docx
- 文档编号:2002135
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:22
- 大小:145.52KB
实验报告.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+s Merge(x,y,p,p+s-1,len_x-1); else{ while(p y[p]=x[p++]; } } voidMergeSort(intx[],intlen_x){ //intlen_x=strlen(x); int*y=newint[len_x]; ints=1; while(s MergePass(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;i cin>>x[i]; } MergeSort(x,len_x); for(inti=0;i cout< } 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;i m[i]=newint[p_len]; } for(inti=0;i m[i][i]=0; for(intr=2;r for(inti=1;i 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 for(intk=i+1;k intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(t 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); cout<<"MultipyA"< } voidMatrix(int*p,intp_len){ //创建s二维数组 int**s=newint*[p_len]; for(inti=0;i s[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;i c[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;i b[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;i inttemp=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(newdist 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]; } //输出最短路径 cout<<"最短路径: "< while(j cout< 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)利
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 报告