算法设计与分析实验报告

1、算法设计与分析实验报告指导老师：沙莎学院：信息科学与工程学院班级：计科0508姓名：戚婕学号：10完成日期：2007年12月 TOC o 1-5 h z HYPERLINK l bookmark7 o Current Document 实验一分治法2实验要求2 HYPERLINK l bookmark1 o Current Document 实验内容 2核心算法2 HYPERLINK l bookmark25 o Current Document 程序代码4实验结果 8 HYPERLINK l bookmark34 o Current Document 实验二贪心法10实验要求10 HYPER

2、LINK l bookmark47 o Current Document 实验内容 10核心算法10 HYPERLINK l bookmark56 o Current Document 程序代码12实验结果 18 HYPERLINK l bookmark66 o Current Document 实验三动态规划20实验要求20实验内容20核心算法20 HYPERLINK l bookmark95 o Current Document 程序代码21实验结果 24 HYPERLINK l bookmark98 o Current Document 实验四深度优先搜索26实验要求26实验内容26核心

3、算法26程序代码 27实验结果 28 HYPERLINK l bookmark119 o Current Document 实验五回溯法30实验要求30实验内容30核心算法30程序代码31实验结果 33实验一分治法实验要求了解用分治法求解的问题：当要求解一个输入规模为n,且n的取值相当大的问题时， 如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kWn,而 且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类 问题分治法是十分有效的。掌握分治法的一般控制流程。DanC (p,q)global n， A1:ninteger m,p,q;验内容编程

4、实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排 序结果和比较次数。输入10组相同的数据，验证排序结果和完成排序的比较次数。与复杂性函数所计算的比较次数比较。用表格列出比较结果。给出文字分析。三.程序算法归并排序算法procedure MERGESORT(low, high)快速排序算法QuickSort(p,q)序代码1. 归并排序#include#include#include#include#define M 11typedef int KeyType;typedef int ElemType;struct recKeyType key;ElemType data;t

5、ypedef rec sqlistM;class guibingpublic:guibing(sqlist b)for(int i=0;iM;i+)ri=bi;void output(sqlist r,int n)for(int i=0;in;i+)coutsetw(4)ri.key;coutendl;void xuanze(sqlist b,int m,int n)int i,j,k;for(i=m;in-1;i+)k=i;for(j=i;jbj.key) k=j;if(k!=i)rec temp=bk;bk=bi;bi=temp;void merge(int l,int m,int h,s

6、qlist r2)xuanze(r,l,m);xuanze(r,m,h);output(r,M);int i,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:sqlist r;void main()coutguibingfa1 运行结果:n”;sqlist a,b;int i,j=0,k=M/2,n=M;srand(time(0);for(i=0;iM

7、;i+)ai.key=rand()%80;bi.key=0;guibing gx(a);cout排序前数组:n”;(a,M);cout数组排序过程演示:n;(j,k,n,b);cout排序后数组:n”;(b,M);();快速排序#include#include#include#include#define MAXI 10typedef int KeyType;typedef int ElemType;struct recKeyType key;ElemType data;typedef rec sqlistMAXI;class kuaisupublic:kuaisu(sqlist a,int

8、m):n(m)for(int i=0;in;i+) bi=ai;void quicksort(int s,int t)int i;if(st)i=part(s,t);quicksort(s,i-1);quicksort(i+1,t);else return;int part(int s,int t)int i,j;rec p;i=s;j=t;p=bs;while(ij)while(i=j;bi=bj;while(ij&bi.key=i+;bj=bi;bi=p;output();return i;void output()for(int i=0;in;i+)coutsetw(4)bi.key;c

9、outendl;private:sqlist b;int n;void main()cout运行结果：n”;sqlist a1;int i,n=MAXI,low=0,high=9;srand(time(0);for(i=0;in;i+)a1i.key=rand()%80;kuaisu px(a1,n);cout数组排序过程演示:n”;(low,high);cout排序后数组：n；();();五.实验结果归并排序e *F:、算错卖验I分治法Debugguibingf a 1 - esegu il)in gf M 运行结果； 就序前数组；23 22 71 23数组排序过总演示二1364214123

10、6321322232371221234163642000000000021300000000021321000000002132122000000021321222300000021321222323000002132122232323aaaa213212223232341aaa213212223232341G3aa213212223232341G3G4a213212223232341G3G471排序后数组，213212223232341G3G471快速排序g *F八算法卖验、分治法.Debug：.kuaisufal. exe kii此gud. - cpp运行结果二险组批序过程演示二39222

11、241637764747556222239416377647475弱222239416377G47475弱22223941弱63G47475?22223941粕63647475?2222394156636474757722223941566364747577腓序后数组二22223941566364747577实验二贪心法实验要求优化问题有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些 使目标函数取极值（极大或极小）的可行解，称为最优解。贪心法求优化问题算法思想：在贪心算法中采用逐步构造最优解的方

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

13、和边数的语句。将统计数与复杂性函数所计算的比较次数比较，用表格列出比较结果，给出文字分 析。三.程序算法1.背包问题的贪心算法procedure KNAPSACK(P, W, M, X, n)序代码1. 背包问题贪心算法#include struct goodinfofloat p; goodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0;=0;cu=M; cu)=1;cu=cu-goodsi.w;=cu/goodsi.w;laggoodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;cout最优解为:endl;for(i=

14、1;i=n;i+)cout第i件物品要放:；coutgoodsi.Xendl;void main()cout|运用贪心法解背包问题|endl;cout|endl;int j；int n;float M;goodinfo *goods;lag=i;cout请输入第igoodsi.w;cout请输入第igoodsi.p;goodsi.p=goodsi.p/goodsi.w;dj;cout;coutendl;MiniSpanTree_PRIM(G, a);void CreateGraph(MGraph &G)int weigh;int i, j = 0, k = 0;char hand, tide;

15、cout;for(i = 0; i ; i+)for(j = 0; j ; j+)j.adj = 88;coutendl;coutinputchar for vexs:;for(i=0; i i;coutendl;coutinput”arc(char,char,weigh):endl;j = 0;k = 0;for(i=0; i ; i+)coutihand;cintide;cinweigh;while (hand != j)j+;while (tide != k)k+;jk.adj = weigh;kj.adj = weigh;j = 0;k = 0;coutendl;void MiniSp

16、anTree_PRIM(MGraph G,VerTexType u)int i, j, k = 0;closedge close;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;closek.lowcost = 0;closek.adjvex = u;for (i = 1; i ; i+)k = minimum(close);coutclosek.adjvex;cout;co

17、utk;coutclosek.lowcostendl;closek.lowcost = 0;for (j=0; j; j+)if kj.adj closej1.lowcost & closej1.lowcost != 0) client = closej1.lowcost;j2 = j1;j1+；return j2;五.实验结果背包问题贪心算法* F:算法卖验、贪心法DetnigKirapmc匕exe运用贪心法解背包问题隋逾入物品的总数量M 睛幕入背包的最大容量，20请:请:1件物品的重量以4 1神物品的效益湖请:请:2件物品的重量=32神物品的效益名请:请:4件物品的重量泅4律物品的效益二5

18、请请5件物品的重量25律物品的效益次请请0 1 1 0 1 U X bos bos bos bos bos .方一.方一.方一.方一.方-o O 要要要要要11 狭品品品品品10 臂物物物物； 01 2 3 4 5 e e 最WWW皿皿2. Prim算法实验三动态规划实验要求理解最优子结构的问题。有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段 的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决 策过程。在50年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最优化原理”， 从而创建了最优化问题的一种新的算法设计方法

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

20、地定义最优值（写出动态规划方程）；3）以自底向上的方式计算出最优值；4）根据计算最优值时得到的信息，构造一个最优解。步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略， 步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4,步 骤3中记录的信息必须足够多以便构造最优解。实验内容编程实现多段图的最短路径问题的动态规划算法。图的数据结构采用邻接表。要求用文件装入5个多段图数据，编写从文件到邻接表的函数。验证算法的时间复杂性。核心算法多段图算法procedure FGRAPH(E, k, n, P)序代码多段图问题#include#include#incl

21、ude#define MAX_VERTEX_NUM 50typedef struct ArcNodeint adjvex; ata = m;G-verticesm.firstArc = NULL;for(m = 1; m adjvex = h;p-value = v;p-nextarc = NULL;while(G-verticesi.data != t) i+; irstArc) irstArc = p; else irstArc; q-nextarc; q = q-nextarc);q-nextarc = p; irstArc;printf(%d”,i);while(p)printf(-%

22、d,%d”,p-adjvex,p-value);irstArc;min = p-value+costp-adjvex; 验结果多段图问题g -FZ算实验动态规切I吨trn叭多段囹实现.eze艾入图25 llAlAlAlAlAlA段- la弧尾，权值）实验四深度优先搜索实验要求理解深度优先搜索策略：深度优先搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的 顶点V,如果边(v,w)是还未探测的边，则沿(v,w)继续搜索下去。当所有的边(v,w)都己 被探寻过，搜索将回溯到发现结点V的顶点。这一过程一直进行到回到源点为止。如果 还存在未被发现的顶点，则选择其中一个作为源结点并重复以上

23、过程，整个进程反复进 行直到所有结点都被发现为止。理解深度优先搜索过程中顶点的三种状态：还未到达的顶点，当前路径上经过的顶点，深度优先在搜索过程中也为结点着色以 表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，当其邻接表被完 全检索之后又被置成黑色。实验内容编程实现深度优先搜索算法。修改算法使之可以找出图的所有树。修改算法使之可以判断图是否为一棵树。修改算法使之可以判断图是否存在一个环。核心算法procedure DFS(G);for每个顶点uEG docoloruj White;repeatfor每个顶点uEG doif coloru=Whitethen DFS_Visit(G,u);end;procedure DFS_Visit(u);coloruGray;for (u,w)EE do序代码#include#define MAX 50 验结果e八算法卖登、注度优先搜耋ID停Im叭判评 em有一 y 其指其指其指其指其捐其指共是an JAJAJAJAJAJAJAJAJAJAJAJA s 请&请请请请请请请请请