算法设计与分析实验报告

1、算法设计与分析实验报告指导老师：沙莎学院：信息科学与工程学院班级：计科0508姓名：戚婕学号：10完成日期：2007年12月目录TOCo1-5hz实验一分治法2实验要求2实验内容2核心算法2程序代码4实验结果8实验二贪心法10实验要求10实验内容10核心算法10程序代码12实验结果18实验三动态规划20实验要求20实验内容20核心算法20程序代码21实验结果24实验四深度优先搜索26实验要求26实验内容26核心算法26程序代码27实验结果28实验五回溯法30实验要求30实验内容30核心算法30程序代码31实验结果33实验一分治法实验要求了解用分治法求解的问题：当要求解一个输入规模为n,且n的取

2、值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn,而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。那末,对于这类问题分治法是十分有效的。掌握分治法的一般控制流程。DanC(p,q)globaln,A1:n;integerm,p,q;/1pqnifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);/pm0个待排序的元素/,/求这个集合的分割点/,mid)/将一个子集合排序/,high)/将另一个子集合排序integerlow,high；iflowhigh；thenmidJcallMERGESO

3、RT(lowcallMERGESORT(mid+1callMERGE(low,mid,high)/归并两个已排序的子集合/endifendMERGESORT归并两个已排序的集合procedureMERGE(low，mid，high)/A(low：high)是一个全程数组/辅助数组B(low；high)/integerh，i，j，k；hjlow;ijlow;jjmid+1;whilehmidandjmidthenforkjjtohighdo/处理剩余的元素/B(i)jA(k)；iji+1repeatelseforkjhtomiddoB(i)jA(k)；iji+1repeatendif将已归并的集

4、合复制到AendMERGE快速排序算法QuickSort(p,q)/将数组A1:n中的元素Ap,Ap+1,?,Aq按不降次序排列，并假定An+1是一个确定的、且大于A1:n中所有的数。/intp,q;globaln,A1:n;ifpvrepeat/ilooppJp-1untilA(p)wvrepeat/pifipthencallINTERCHANGE(A(i)，A(p)/A(i)由左向右移/由右向左移/和A(p)换位/endifrepeatA(m)JA(p)；A(p)Jv/划分元素在位置p/EndPARTITION程序代码归并排序#include#include#include#include

5、#defineM11typedefintKeyType;typedefintElemType;structrecKeyTypekey;ElemTypedata;typedefrecsqlistM;classguibingpublic:guibing(sqlistb)for(inti=0;iM;i+)ri=bi;voidoutput(sqlistr,intn)for(inti=0;in;i+)coutsetw(4)ri.key;coutendl;voidxuanze(sqlistb,intm,intn)inti,j,k;for(i=m;in-1;i+)k=i;for(j=i;jbj.key)k=

6、j;if(k!=i)rectemp=bk;bk=bi;bi=temp;voidmerge(intl,intm,inth,sqlistr2)xuanze(r,l,m);xuanze(r,m,h);output(r,M);inti,j,k;k=i=l;for(j=m;im&jh;k+)if(ri.key=rj.key)r2k=ri;i+;elser2k=rj;j+;output(r2,M);while(jh)r2k=rj;j+;k+;while(i=m)r2k=ri;i+;k+;output(r2,M);private:sqlistr;voidmain()coutguibingfa1运行结果:n;

7、sqlista,b;inti,j=0,k=M/2,n=M;srand(time(0);for(i=0;iM;i+)ai.key=rand()%80;bi.key=0;guibinggx(a);cout排序前数组:n;gx.output(a,M);cout数组排序过程演示:n;gx.merge(j,k,n,b);cout排序后数组:n;gx.output(b,M);cin.get();快速排序#include#include#include#include#defineMAXI10typedefintKeyType;typedefintElemType;structrecKeyTypekey;E

8、lemTypedata;typedefrecsqlistMAXI;classkuaisupublic:kuaisu(sqlista,intm):n(m)for(inti=0;in;i+)bi=ai;voidquicksort(ints,intt)inti;if(st)i=part(s,t);quicksort(s,i-1);quicksort(i+1,t);elsereturn;intpart(ints,intt)inti,j;recp;i=s;j=t;p=bs;while(ij)while(i=p.key)j-;bi=bj;while(ij&bi.key=p.key)i+;bj=bi;bi=

9、p;output();returni;voidoutput()for(inti=0;in;i+)coutsetw(4)bi.key;coutendl;private:sqlistb;intn;voidmain()coutkuaisu1.cpp运行结果:n;sqlista1;inti,n=MAXI,low=0,high=9;srand(time(0);for(i=0;in;i+)a1i.key=rand()%80;kuaisupx(a1,n);cout数组排序过程演示:n;px.quicksort(low,high);coutP(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量

10、大小，而x(1:n)是解向量realP(1:n)，W(1:n)，X(1:n)，M，cu;integeri，n;X-0/将解向量初始化为零cuMcu是背包剩余容量fori-1tondoifW(i)cuthenexitendifX(i)-1cu-cu-W(i)repeatifinthenX(i)-cu/W(i)endifendGREEDY-KNAPSACKprocedureprim(G,)status-“unseen”/Tstatus1-“treenode”/foreachedge(1,w)dostatusw-“fringe”/dadw-1;/wdistw-weight(1,w)/wrepeatw

11、hilestatust丰“treenode”dopickafringeuwithmindistw/statusu-“treenode”为空将1放入T找到T的邻接点通过1与T建立联系到T的距离选取到T最近的节点foreachedge(u,w)do修改w和T的关系repeatrepeat2.Prim算法PrimMST(G，T，r)/求图G的以r为根的MST结果放在T=(U,TE)中InitCandidateSet();/初始化：设置初始的轻边候选集，并for(k=0;kn-1;k+)/求T的n-1条树边T=(r,C)(u,v)=SelectLiShtEdge();/选取轻边(u,v);TjTU(u

12、,v);/扩充T,即(u,v)涂红加入TE,蓝点v并人红点集UModifyCandidateSet();/根据新红点v调整候选轻边集程序代码1.背包问题贪心算法#includestructgoodinfofloatp;/物品效益floatw;/物品重量floatX;/物品该放的数量intflag;/物品编号;/物品信息结构体voidInsertionsort(goodinfogoods,intn)intj,i;for(j=2;jgoodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0;/按物品效益,重量比值做升序排列voidbag(goodinfogoods,fl

13、oatM,intn)floatcu;inti,j;for(i=1;i=n;i+)goodsi.X=0;cu=M;/背包剩余容量for(i=1;icu)/当该物品重量大与剩余容量跳出break;goodsi.X=1;cu=cu-goodsi.w;/确定背包新的剩余容量if(i=n)goodsi.X=cu/goodsi.w;/该物品所要放的量for(j=2;j=n;j+)goods0=goodsj;i=j-1;while(goods0.flaggoodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;cout最优解为:endl;for(i=1;i=n;i+)co

14、ut第i件物品要放:;coutgoodsi.Xendl;voidmain()cout|运用贪心法解背包问题|endl;cout|endl;intj;intn;floatM;goodinfo*goods;/定义一个指针while(j)coutn;goods=newstructgoodinfon+1;/coutM;coutendl;inti;for(i=1;i=n;i+)goodsi.flag=i;cout请输入第igoodsi.w;cout请输入第igoodsi.p;goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比coutendl;Insertionsort(goo

15、ds,n);bag(goods,M,n);coutpresstorunagianendl;coutpresstoexitj;Prim算法#include#include#include#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefintVRType;typedefintInfoType;typedefcharVerTexType;typedefstructArcCellVRTypeadj;InfoType*info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructVe

16、rTexTypevexsMAX_VERTEX_NUM;AdjMatrixarcs;intvexnum,arcnum;MGraph;typedefstructVerTexTypeadjvex;VRTypelowcost;closedgeMAX_VERTEX_NUM;voidCreateGraph(MGraph&G);voidMiniSpanTree_PRIM(MGraphG,VerTexTypeu);intLocateVex(MGraphG,VerTexTypeu);intminimum(closedgeclose);voidmain(void)inti,j;MGraphG;CreateGrap

17、h(G);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)coutG.arcsij.adj;cout;coutendl;MiniSpanTree_PRIM(G,a);voidCreateGraph(MGraph&G)intweigh;inti,j=0,k=0;charhand,tide;coutG.vexnumG.arcnum;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)G.arcsij.adj=88;coutendl;coutinputG.vexnumcharforvexs:;for(i=0;iG.vexsi;cou

18、tendl;coutinputG.arcnumarc(char,char,weigh):endl;j=0;k=0;for(i=0;iG.arcnum;i+)coutihand;cintide;cinweigh;while(hand!=G.vexsj)j+;while(tide!=G.vexsk)k+;G.arcsjk.adj=weigh;G.arcskj.adj=weigh;j=0;k=0;coutendl;voidMiniSpanTree_PRIM(MGraphG,VerTexTypeu)inti,j,k=0;closedgeclose;k=LocateVex(G,u);for(j=0;jG

19、.vexnum;j+)if(j!=k)closej.adjvex=G.vexsk;closej.lowcost=G.arcskj.adj;closej.lowcost=88;closej.adjvex=0;closek.lowcost=0;closek.adjvex=u;for(i=1;iG.vexnum;i+)k=minimum(close);coutclosek.adjvex;cout;coutG.vexsk;coutclosek.lowcostendl;closek.lowcost=0;for(j=0;jG.vexnum;j+)if(G.arcskj.adjclosej1.lowcost

20、&closej1.lowcost!=0)client=closej1.lowcost;j2=jl；j1+；returnj2;实验结果1.背包问题贪心算法瞬飆i鵜藍翳潮鬻驀:;0要要要要要tt弘品品品品品1012345ee=0：L：1=0.75：1runAgianexit2.Prim算法实验三动态规划实验要求理解最优子结构的问题。有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼(RichardBellman)等人提出了解决这类问题的“最优化原理”，从而创建了最优化问

21、题的一种新的算法设计方法动态规划。对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。理解分段决策Bellman方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。us0,ujmiinjuiwij.Us初始值，Uj第j段的最优值。一般方法找出最优解的性质，并刻画其结构特征；递归地定义最优值

22、(写出动态规划方程)；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造一个最优解。步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。实验内容编程实现多段图的最短路径问题的动态规划算法。图的数据结构采用邻接表。要求用文件装入5个多段图数据，编写从文件到邻接表的函数。验证算法的时间复杂性。核心算法多段图算法procedureFGRAPH(E，k，n，P)/输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c(i,j)是边的成本。P(

23、1：k)是最小成本路径。/realCOST(n)，integerD(n一1)，P(k)，r，j，k，nCOST(n)0forjn-1to1by1do/计算COST(j)/设r是一个这样的结点，(j,r)?E且使c(j,r)+COST(r)取最小值COST(j)c(j，r)+COST(r)D(j)rrepeat/向前对j-1进行决策/P(1)1；P(k)n；forj2tok-1do/找路径上的第j个节点/P(j)D(P(j-1)repeatendFGRAPH程序代码多段图问题#include#include#include#defineMAX_VERTEX_NUM50typedefstructA

24、rcNodeintadjvex;/该弧所指向的顶点的位置intvalue;/该结点与邻接结点间的代价structArcNode*nextarc;/指向下一条弧的指针ArcNode,*node;typedefstructVNodeintdata;/顶点信息ArcNode*firstArc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedefstructGraphAdjListvertices;intvexnum,arcnum;/图的当前顶点数和弧数*ALGraph;intbuild_adList(ALGraphG,intn,inta)/建立邻接表

25、intv,m,i,t,h;nodep,q;if(nvexnum=n;/图的顶点数if(aarcnum=a;/图的弧数for(m=0;mverticesm.data=m;G-verticesm.firstArc=NULL;for(m=1;madjvex=h;p-value=v;p-nextarc=NULL;while(G-verticesi.data!=t)i+;/转到下一个结点if(!G-verticesi.firstArc)/终点G-verticesi.firstArc=p;else/若当前结点有后继节点则后移for(q=G-verticesi.firstArc;q-nextarc;q=q-

26、nextarc);q-nextarc=p;/新开辟结点returnv;voidprint_Graph(ALGraphG)/打印邻接表ArcNode*p=(ArcNode*)malloc(sizeof(ArcNode);inti;for(i=1;ivexnum;i+)p=G-verticesi.firstArc;printf(%d,i);while(p)printf(-%d,%d,p-adjvex,p-value);/第i个结点的邻接结点信息p=p-nextarc;printf(n);voidfgraph(ALGraphG,intk,intn)/多段图ALGraphG,n为结点数，k为图的段数/

27、输入是按段的顺序给结点编号intcost100;intd100;intpath100;intj,r,i,min,w,value;nodep;costn=0;for(j=n-1;j=1;j-)/向前处理结点p=G-verticesj.firstArc;min=p-value+costp-adjvex;/初始化路径最小代价r=p-adjvex;value=p-value;while(p!=NULL)/r是一个的这样的结点，权值c(j,r)+costr取最小值if(p-value+costp-adjvex)value+costp-adjvex;/p-value=c(j,r)r=p-adjvex;va

28、lue=p-value;p=p-nextarc;costj=value+costr;/当前节点的代价值dj=r;/决策阶段，各结点到终点最小代价路径上前方顶点的编号path1=1;pathk=n;for(i=2;i=k-1;i+)/找出最小代价路径上的结点pathi=dpathi-1;printf(最小成本为:%dn,cost1);printf(最小成本路径为:);for(w=1;w,pathw);voidmain()ALGraphg;intn,a,k;g=(ALGraph)malloc(sizeof(ALGraph);printf(请输入多段图节点数目:);scanf(%d,&n);prin

29、tf(请输入多段图边的数目:);scanf(%d,&a);printf(请输入多段图的段数:);scanf(%d,&k);printf(输入多段图的弧的信息(弧头，弧尾，权值)n);build_adList(g,n,a);printf(多段图的邻接表为:n);print_Graph(g);fgraph(g,k,n);getch();实验结果多段图问题弧尾，权值）头弧rx一目目:3息毀数数住庶的2,3Z4.5,S5为4节边的弧1,1,2,3.4.春5-田E的m瓜瓜瓜呱肌接3.翟a?X08458615:*57-2-10为:1径为路的/,6,1盯本本八入入图2555成成|1|2|3冒蠶实验四深度优先

30、搜索.实验要求1理解深度优先搜索策略：深度优先搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点v,如果边（v,w）是还未探测的边，贝U沿（v,w）继续搜索下去。当所有的边（v,w）都己被探寻过，搜索将回溯到发现结点v的顶点。这一过程一直进行到回到源点为止。如果还存在未被发现的顶点，贝选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。2理解深度优先搜索过程中顶点的三种状态：还未到达的顶点，当前路径上经过的顶点，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，当其邻接表被完全检索之后又被置成黑色。.实

31、验内容1编程实现深度优先搜索算法。2修改算法使之可以找出图的所有树。3修改算法使之可以判断图是否为一棵树。4修改算法使之可以判断图是否存在一个环。procedureDFS(G);for每个顶点uGdocoloruJWhite;repeatfor每个顶点uGdoifcoloru=WhitethenDFS_Visit(G,u);end;procedureDFS_Visit(u);coloruJGray;for(u,w)Edo/探寻边(u,w)ifcolorw=WhitethenDFS_Visit(w);/完成后置u为黑色repeatcoloruJBlack;end;四.程序代码#include#d

32、efineMAX50/能够处理的最多顶点数charcolorMAX;/保存每个点的颜色标记intn,AMAXMAX;/顶点数和矩阵intloop=0;/标记环并记录其个数inttree=0;/标记树并记录其个数voidDFS(inti)intk;colori=G;/已访问顶点记为灰色for(k=1;k=n;k+)if(Aik=1)if(colork=G|colork=B)/当该点的邻接点中有已被访问的点时存在环loop+;if(colork=W)DFS(k);/访问邻接点中一个没有被访问的点colori=B;/当点为死结点时记为黑色voidmain()inti,j,k,m;coutn;coutm;for(i=1;i=n;i+)for(j=1;j=n;j+)Aij=0;/将矩阵初始化为0colori=W;/所有顶点颜色初始化为白色for(k=1;k=m;k+)couti;coutj;Aij=1;/有边的赋值为1for(i=1;i=n;i+)if(colori=W)DFS(i);for(i=1;i=n;i+)for(j=1;jn;j+)if(!(Aij&Aji)tree+;if(loop=0)cout该图中无环!end