算法设计与分析实验报告

1、v1.0可编辑可修改算法设计与分析实验报告指导老师：沙莎学院：信息科学与工程学院班级：计科0508姓名：戚婕学号：10完成日期：2007年12月目录实验一分治法2实验要求2实验内容2核心算法2程序代码4实验结果8实验二贪心法10实验要求10实验内容10核心算法10程序代码12实验结果18实验三动态规划20实验要求20实验内容20核心算法20程序代码21实验结果24实验四深度优先搜索26实验要求26实验内容26核心算法26程序代码2711v1.0可编辑可修改实验结果28实验五回溯法30实验要求30实验内容30核心算法30程序代码31实验结果33实验一分治法一.实验要求1 .了解用分治法求解的问题

2、：当要求解一个输入规模为n,且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<kwn,而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2 .掌握分治法的一般控制流程。DanQp,q)globaln,A1:n;integerm,p,q;验内容1 .编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。2 .输入10组相同的数据，验证排序结果和完成排序的比较次数。3 .与复杂性函数所计算的比较次数比较。4 .用表格列出比较结果。5 .给出文字分析。三.

3、程序算法23v1.0可编辑可修改1 .归并排序算法procedureMERGESORT(low,high)快速排序算法QuickSort(p,q)序代码2 .归并排序#include<>#include<>#include<>#include<>#defineM11typedefintKeyType;typedefintElemType;structrecKeyTypekey;ElemTypedata;typedefrecsqlistM;classguibingpublic:guibing(sqlistb)for(inti=0;i<M;i+

4、)ri=bi;voidoutput(sqlistr,intn)for(inti=0;i<n;i+)cout<<setw(4)<<ri.key;cout<<endl;voidxuanze(sqlistb,intm,intn)inti,j,k;33v1.0可编辑可修改for(i=m;i<n-1;i+)k=i;for(j=i;j<n;j+)if(bk.key>bj.key)k=j;if(k!=i)rectemp=bk;bk=bi；bi=temp;voidmerge(intl,intm,inth,sqlistr2)xuanze(r,l,m);

5、xuanze(r,m,h);output(r,M);inti,j,k;k=i=l;for(j=m;i<m&&j<h;k+)if(ri.key<=rj.key)r2k=ri;i+；elser2止皿j+;output(r2,M);#v1.0可编辑可修改while(j<h)r2k=rj；j+；k+;while(i<=m)r2k=ri；i+；k+;output(r2,M);private:sqlistr;；voidmain()cout<<"guibingfa1运行结果：n"sqlista,b;inti,j=0,k=M/2,n

6、=M;srand(time(0);for(i=0;i<M;i+)ai.key=rand()%80;bi.key=0;guibinggx(a);cout<<"排序前数组:n"(a,M);cout<<"数组排序过程演示：n"(j,k,n,b);cout<<"排序后数组:n"(b,M);55v1.0可编辑可修改();3 .快速排序#include<>#include<>#include<>#include<>#defineMAXI10typedefin

7、tKeyType;typedefintElemType;structrecKeyTypekey;ElemTypedata;typedefrecsqlistMAXI;classkuaisupublic:kuaisu(sqlista,intm):n(m)for(inti=0;i<n;i+)bi=ai;voidquicksort(ints,intt)inti;if(s<t)i=part(s,t);quicksort(s,i-1);quicksort(i+1,t);elsereturn;intpart(ints,intt)#v1.0可编辑可修改inti,j；recp;i=s/t;p=bs;

8、while(i<j)while(i<j&&bj.key>=j-;bi=bjwhile(i<j&&bi.key<=i+;bj=bi；bi=P；output。；returni;voidoutput。for(inti=0;i<n;i+)cout<<setw(4)<<bi.key;cout<<endl;private:sqlistb;intn;voidmain()cout<<"运行结果:n"sqlista1;inti,n=MAXI,low=0,high=9;srand

9、(time(0);for(i=0;i<n;i+)a1i.key=rand()%80;kuaisupx(a1,n);77v1.0可编辑可修改cout<<"数组排序过程演示：n"(low,high);cout<<"排序后数组:n"()；()；五.实验结果1.归并排序1.F：、算法实畛、分治法'DubuCgirtbingfal-exeguihinqzfal运行结果二熊序施组;232271231364214123632数组排序过程演示二13222323712212341G3642SO0Q0Q00002132100000000

10、313212200000U03132122230Q0Q0Q213212223230B0B021321222323230B0B213212223232341909213212222232241G»02132122232323416364B213212223232341636471排殍后数组，213212223232341心t4712.快速排序8-F二'算法卖药'分丰台法'DubujAkii看:LmuHhI.exe"上一次"4-mkuaisul.cppiST?nTfc:购组排序过程演示二3?222241637764747556222239416

11、377E4747S5622229941G377G474如GG2222394166E474772222394156636475772222394156636474757?2222394156636474757?腓序后数组:2222394156636474757?#v1.0可编辑可修改实验二贪心法一.实验要求1 .优化问题有n输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值（极大或极小）的可行解，称为最优解。2 .贪心法求优化问题算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，

12、都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedycriterion）。3 .一般方法1）根据题意，选取一种量度标准。2）按这种量度标准对这n个输入排序3）依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。procedureGREEDY（A,n）/*贪心法一般控制流程*/验内容1 .编程实现背包问题贪心算法和最小生成树prim算法。通过具体算法理解如何通过局部最优实现全局最优，并验证算法的时间复杂性。2 .输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句

13、。3 .将统计数与复杂性函数所计算的比较次数比较，用表格列出比较结果，给出文字分析。三.程序算法99v1.0可编辑可修改1 .背包问题的贪心算法procedureKNAPSACK(P,WM,X,n)序代码2 .背包问题贪心算法#include<>structgoodinfofloatp;>goodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0;=0;cu=M;>cu)=1;cu=cu-goodsi.w产cu/goodsi.w;lag<goodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;cou

14、t<<"最优解为:"<<endl;for(i=1;i<=n;i+)cout<<"第"<<i<<"件物品要放："；cout<<goodsi.X<<endl;voidmain()cout<<"|运用贪心法解背包问题|"<<endl;cout<<"|"<<endl;#v1.0可编辑可修改intj;intn;floatM;goodinfo*goods;lag=i;co

15、ut<<"请输入第"<<i<<"件物品的重量："；cin>>goodsi.w;cout<<"请输入第"<<i<<"件物品的效益："；cin>>goodsi.p;goodsi.p=goodsi.p/goodsi.w;dj;cout<<""cout<<endl;MiniSpanTree_PRIM(G,'a');voidCreateGraph(MGraph&G

16、)intweigh;inti,j=0,k=0;charhand,tide;cout<<"inputthenumberforvexnumandarcnum:"cin>>>>for(i=0;i<i+)for(j=0;j<j+)ij.adj=88;cout<<endl;cout<<"input"<<<<"charforvexs:"for(i=0;i<i+)cin>>i;cout<<endl;cout<<&

17、quot;input"<<<<"arc(char,char,weigh):"<<endl;j=0;1111v1.0可编辑可修改k=0;for(i=0;i<i+)cout<<i<<":"cin>>hand;cin>>tide;cin>>weigh;while(hand!=j)j+；while(tide!=k)k+;jk.adj=weigh;kj.adj=weigh;j=0;k=0;cout<<endl;voidMiniSpanTree

18、_PRIM(MGraphG,VerTexTypeu)inti,j,k=0;closedgeclose;k=LocateVex(G,u);for(j=0;j<j+)if(j!=k)closej.adjvex=k;closej.lowcost=kj.adj;closej.lowcost=88;closej.adjvex='0'#v1.0可编辑可修改closek.lowcost=0;closek.adjvex=u;for(i=1;i<i+)k=minimum(close);cout<<closek.adjvex;cout<<">&q

19、uot;cout<<k<<""cout<<closek.lowcost<<endl;closek.lowcost=0;for(j=0;j<j+)ifkj.adj<closej.lowcost)closej.adjvex=k;closej.lowcost=kj.adj;intLocateVex(MGraphG,VerTexTypeu)intk=0;whilek+=u)returnk-1;return0;intminimum(closedgeclose)intj1=0,client=88,j2;while(closej

20、1.adjvex!=''0')if(client>closej1.lowcost&&closej1.lowcost!=0)1313v1.0可编辑可修改client=closej1.lowcost;j2=jl；j1+;returnj2;五.实验结果1 .背包问题贪心算法-F门算法实验、能心法）DetniCKGap5ack.eze运用贪心法解背包问题匕入物品的总数量！50人背直的最大容量20D入塞1件物品的重量：14认第1柞枷品的效益;8物品的重量二3枷品的豆需二6入缭3件物品的重量;？入福性物品的效益=10道iS。入塞4件物品的重量二8认亲4性枷品的

21、效益当0人集5件物品的重量二彳 认第5怦枷品的效益二9为二勿品要欣四第4件物品要牧M 75重5件枷品要破门press <L> to Pim agianpi*e£s <0> to exit#v1.0可编辑可修改2 .Prim算法5'F：算法卖牛耳后”inputthenumberforuexnumandarcnum：56inpuc5charforvexs：12345inputtiarc(cJi-ar,cli-ai,weigh);,：1241：13S2:144J：2S74:3S6L：45S88454g848See踹75SBSfiB«£4S

22、B6S8«S8S768S81)24141>353>56PressarvkestocontinueH1515v1.0可编辑可修改实验三动态规划1 .实验要求1 .理解最优子结构的问题。有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（RichardBellman）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法-动态规划。对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采

23、用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。2 .理解分段决策Bellman方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。Us0,*mjUiWj.Us初始值，Uj第j段的最优值。3 .一般方法4 ）找出最优解的性质，并刻画其结构特征；5 ）递归地定义最优值（写出动态规划方程）；6 ）以自底向上的方式计算出最优值；7 ）根据计算最优值时得到的信息，构造一个最优解。步

24、骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略,步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4,步骤3中记录的信息必须足够多以便构造最优解。2 .实验内容1 .编程实现多段图的最短路径问题的动态规划算法。2 .图的数据结构采用邻接表。3 .要求用文件装入5个多段图数据，编写从文件到邻接表的函数。4 .验证算法的时间复杂性。#v1.0可编辑可修改3 .核心算法多段图算法procedureFGRAPH(Ek,n,P)序代码多段图问题#include<>#include<>#include<>#defineMAX

25、_VERTEX_NUM50typedefstructArcNodeintadjvex;ata=m;G->verticesm.firstArc=NULL;for(m=1;m<=a;m+)i=1;printf("输入第原弧：",m);scanf("%d,%d,%d",&t,&h,&v);p=(ArcNode*)malloc(sizeof(ArcNode);p->adjvex=h;p->value=v;p->nextarc=NULL;while(G->verticesi.data!=t)i+;irst

26、Arc)irstArc=p;elseirstArc;q->nextarc;q=q->nextarc);q->nextarc=p;irstArc;printf("%d”,i);while(p)printf("->%d,%d",p->adjvex,p->value);irstArc;min=p->value+costp->adjvex;验结果多段图问题1717v1.0可编辑可修改1818v1.0可编辑可修改实验四深度优先搜索1 .理解深度优先搜索策略：深度优先搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现

27、的顶点v,如果边(v,w)是还未探测的边，则沿(v,w)继续搜索下去。当所有的边(v,w)都己被探寻过，搜索将回溯到发现结点v的顶点。这一过程一直进行到回到源点为止。如果还存在未被发现的顶点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。2 .理解深度优先搜索过程中顶点的三种状态：还未到达的顶点，当前路径上经过的顶点，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，当其邻接表被完全检索之后又被置成黑色。2 .实验内容1 .编程实现深度优先搜索算法。2 .修改算法使之可以找出图的所有树。3 .修改算法使之可以判断图是否为一棵树。4 .修改算法使之可以判断图是否存在一个环。3 .核心算法procedureDFS(G);for每个顶点uCGdocoloru.White;repeatfor每个顶点uCGdoifcoloru=WhitethenDFS_Visit(G,u);end;procedureDFS_Visit(u);coloruGray;for(u,w)CEdo序代码#include<>#d