算法设计与分析实验报告格式.doc

算法设计与分析实验报告一实验名称 统计数字问题 评分 实验日期 年 月 日 指导教师 刘长松 姓名 刘飞初 专业班级 计算机0901 学号 10 一.实验要求1、掌握算法的计算复杂性概念。2、掌握算法渐近复杂性的数学表述。3、掌握用C+语言描述算法的方法。4实现具体的编程与上机实验，验证算法的时间复杂性函数。二.实验内容 统计数字问题1、问题描述一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1， 2，9。2、编程任务给定表示书的总页码的10 进制整数n (1n109) 。编程计算书的全部页码中分别用到多少次数字0，1，2，9。三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个19作为个位数，余数代表有1余数本身这么多个数作为剩余的个位数，此外，商还代表1商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。四.程序代码#includeint s10; /记录09出现的次数int a10; /ai记录n位数的规律void sum(int n,int l,int m) if(m=1)int zero=1; for(int i=0;i=l;i+) /去除前缀0 s0-=zero; zero*=10; if(n10) for(int i=0;i=n;i+) si+=1; return; /位数为1位时,出现次数加1/位数大于1时的出现次数 for(int t=1;t=l;t+)/计算规律f(n)=n*10(n-1)m=1;int i;for(i=1;it;i+)m=m*10;at=t*m;int zero=1; for(int i=0;il;i+) zero*= 10; /求出输入数为10的n次方 int yushu=n%zero; /求出最高位以后的数 int zuigao=n/zero; /求出最高位zuigao for(i=0;izuigao;i+) si+=zero; /求出0zuigao-1位的数的出现次数 for(i=0;iyushu) i+; s0+=i*(yushu+1);/补回因作模操作丢失的0 szuigao+=(yushu+1);/补回最高位丢失的数目 sum(yushu,l-i-1,m+1);/处理余位数void main() int i,m,n,N,l;coutN;cout=10;i+) n/=10; /求出N的位数n-1 l=i; sum(N,l,1); for(i=0; i10;i+) cout 数字i出现了:si次n; 五.程序调试中的问题调试过程中总是有这样那样的问题，通过一步步的修改，最终得以实现。六.实验结果算法设计与分析实验报告二实验名称 分治法实现归并排序算法 评分 实验日期 年 月 日 指导教师 刘长松 姓名 刘飞初 专业班级 计算机0901 学号 10 一.实验要求1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2.掌握分治法的一般控制流程。DanC(p,q) global n，A1:n; integer m,p,q; / 1pqn if Small(p,q) then return G(p,q); else m=Divide(p,q); / pmq return Combine(DanC(p,m),DanC(m+1,q); endifend DanC3实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。二.实验内容1.编程实现归并排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。2.输入10组相同的数据，验证排序结果和完成排序的比较次数。3.与复杂性函数所计算的比较次数比较。4.用表格列出比较结果。5.给出文字分析。三.程序算法1. 归并排序算法procedure MERGESORT(low，high) /A(low；high)是一个全程数组，它含有high-low+10个待排序的元素/ integer low，high； if lowmid then for kj to high do /处理剩余的元素/ B(i) A(k)；ii+1 repeat else for kh to mid do B(i) A(k)；ii+1 repeat endif 将已归并的集合复制到A end MERGE2. 快速排序算法QuickSort(p,q) /将数组A1:n中的元素 Ap, Ap+1, , Aq按不降次序排列， 并假定An+1是一个确定的、且大于 A1:n中所有的数。/ int p,q; global n, A1:n; if pq then j=Partition(p, q+1); / 划分后j成为划分元素的位置 QuickSort(p,j-1); QuickSort(j+1,q); endif end QuickSortprocedure PARTITION(m，p) /退出过程时，p带着划分元素所在的下标位置。/ integer m，p，i；global A(m：p-1) vA(m)；im /A(m)是划分元素/ loop loop ii+1 until A(i)v repeat /i由左向右移/ loop pp-1 until A(p)v repeat /p由右向左移/ if ip then call INTERCHANGE(A(i)，A(p) /A(i)和A(p)换位/ else exit endif repeat A(m) A(p)；A(p) v /划分元素在位置p/ End PARTITION四.程序代码归并排序#include#include#include#include#define M 11typedef int KeyType;typedef int ElemType;struct recKeyType key;ElemType data; ;typedef 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,sqlist 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;i+)ai.key=rand()%80;bi.key=0;guibing gx(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#define MAXI 10typedef int KeyType;typedef int ElemType;struct recKeyType key;ElemType data; ;typedef rec sqlistMAXI;class kuaisupublic:kuaisu(sqlist a,int 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=p.key)j-;bi=bj;while(ij&bi.key=p.key)i+;bj=bi;bi=p;output();return i;void output()for(int i=0;in;i+)coutsetw(4)bi.key;coutendl;private:sqlist b;int n;void main()coutkuaisu1.cpp运行结果: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;px.quicksort(low,high);cout排序后数组:n;px.output();cin.get(); 五.程序调试中的问题1. 归并排序2. 快速排序算法设计与分析实验报告三实验名称 动态规划算法实现多段图的最短路径问题 评分 实验日期 年 月 日 指导教师 刘长松 姓名 刘飞初 专业班级 计算机0901 学号 10 一.实验要求1. 理解最优子结构的问题。有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法动态规划。对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。2.理解分段决策Bellman方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。Us 初始值，uj第j段的最优值。3.一般方法1） 找出最优解的性质，并刻画其结构特征；2） 递归地定义最优值（写出动态规划方程）；3） 以自底向上的方式计算出最优值；4） 根据计算最优值时得到的信息，构造一个最优解。步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。二.实验内容1.编程实现多段图的最短路径问题的动态规划算法。2.图的数据结构采用邻接表。3.要求用文件装入5个多段图数据，编写从文件到邻接表的函数。4.验证算法的时间复杂性。三.程序算法多段图算法procedure FGRAPH(E，k，n，P) /输入是按段的顺序给结点编号的，有n个结点 的k段图。E是边集，c(i，j)是边的成本。 P(1：k)是最小成本路径。/ real COST(n)，integerD(n一1)，P(k)，r，j，k，n COST(n) 0 for jn-1to 1by1do /计算COST(j)/ 设r是一个这样的结点，(j，r)E且使c(j，r)+COST(r)取最小值 COST(j)c(j，r)+COST(r) D(j)r repeat /向前对j-1进行决策/ P(1)1；P(k)n； for j2 to k-1 do /找路径上的第j个节点/ P(j)D ( P(j-1) ) repeat end FGRAPH四.程序代码多段图问题#include#include#include#define MAX_VERTEX_NUM 50typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置int value; /该结点与邻接结点间的代价struct ArcNode *nextarc; /指向下一条弧的指针ArcNode, *node;typedef struct VNodeint data; /顶点信息 ArcNode *firstArc; /指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef struct GraphAdjList vertices;int vexnum,arcnum; /图的当前顶点数和弧数*ALGraph;int build_adList(ALGraph G,int n,int a) /建立邻接表int v, m, i, t, h;node p, q;if(n vexnum = n; /图的顶点数if(a arcnum = a; /图的弧数for(m = 0; m verticesm.data = m; G-verticesm.firstArc = NULL;for(m = 1; m adjvex = 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-nextarc); q-nextarc = p; /新开辟结点return v;void print_Graph(ALGraph G) /打印邻接表ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode);int i;for(i = 1; i vexnum; i+)p = G-verticesi.firstArc;printf(%d,i);while(p)printf(-%d,%d,p-adjvex,p-value);/第i个结点的邻接结点信息p = p-nextarc;printf(n);void fgraph(ALGraph G ,int k,int n) /多段图ALGraph G，n为结点数，k为图的段数 /输入是按段的顺序给结点编号int cost100; int d100;int path100; int j, r, i, min, w, value; node p;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;value = 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);void main()ALGraph g; int n,a,k;g = (ALGraph)malloc(sizeof(ALGraph); printf(请输入多段图节点数目:); scanf(%d, &n);printf(请输入多段图边的数目:); scanf(%d, &a);printf(请输入多段图的段数:);scanf(%d, &k); printf(输入多段图的弧的信息（弧头，弧尾，权值）n);build_adList(g, n, a); printf(多段图的邻接表为:n);print_Graph(g); fgraph(g, k, n); getch();五.实验结果多段图问题算法设计与分析实验报告四实验名称 贪心算法实现背包问题 评分 实验日期 年 月 日 指导教师 刘长松 姓名 刘飞初 专业班级 计算机0901 学号 10 一.实验要求1. 优化问题 有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。2.贪心法求优化问题算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedy criterion）。3.一般方法1）根据题意，选取一种量度标准。2）按这种量度标准对这n个输入排序3）依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。procedure GREEDY(A，n) /*贪心法一般控制流程*/ /A(1：n)包含n个输入/ solutions /将解向量solution初始化为空 for i1 to n do xSELECT(A) if FEASIBLE(solution，x) then solutionsUNION(solution，x) endif repeat return(solution)end GREEDY4. 实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。二.实验内容1. 编程实现背包问题贪心算法。通过具体算法理解如何通过局部最优实现全局最优，并验证算法的时间复杂性。2.输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句。3.将统计数与复杂性函数所计算的比较次数比较，用表格列出比较结果，给出文字分析。三.程序算法1. 背包问题的贪心算法 procedure KNAPSACK(P，W，M，X，n) /P(1：n)和W(1；n)分别含有按 P(i)/W(i)P(i+1)/W(i+1)排序的n件物品的效益值 和重量。M是背包的容量大小，而x(1：n)是解向量 real P(1：n)，W(1：n)，X(1：n)，M，cu； integer i，n；X0 /将解向量初始化为零 cuM /cu是背包剩余容量 for i1 to n do if W(i)cu then exit endif X(i) 1 cucu-W(i) repeat if in then X(i) cu/ W(i) endif end GREEDY-KNAPSACKprocedure prim(G,)status“unseen” / T为空 status1“tree node” / 将1放入Tfor each edge(1,w) do statusw“fringe” / 找到T的邻接点 dadw 1; /w通过1与T建立联系 distw weight(1,w) /w到T的距离 repeatwhile statust “tree node” do pick a fringe u with min distw / 选取到T最近的节点 statusu“tree node” for each edge(u,w) do 修改w和T的关系 repeatrepeat2. Prim算法PrimMST(G，T，r) /求图G的以r为根的MST，结果放在T=(U，TE)中 InitCandidateSet()；/初始化：设置初始的轻边候选集，并置T=(r，) for(k=0；kn-1；k+) /求T的n-1条树边 (u，v)=SelectLiShtEdge()；/选取轻边(u，v)； TT(u，v)；/扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U ModifyCandidateSet()； /根据新红点v调整候选轻边集 1. 背包问题贪心算法#include struct goodinfo float p; /物品效益 float w; /物品重量 float X; /物品该放的数量 int flag; /物品编号;/物品信息结构体void Insertionsort(goodinfo goods,int n) int j,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列void bag(goodinfo goods,float M,int n) float cu; int i,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+) cout第i件物品要放:; coutgoodsi.Xendl; void main() cout|-运用贪心法解背包问题-|endl; cout|-|endl; int j; int n; float M; goodinfo *goods;/定义一个指针 while(j) coutn; goods=new struct goodinfo n+1;/ coutM; coutendl; int i; for(i=1;i=n;i+) goodsi.flag=i; cout请输入第igoodsi.w; cout请输入第igoodsi.p; goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比 coutendl; Insertionsort(goods,n); bag(goods,M,n); coutpress to run agianendl; coutpress to exitj; 2. Prim算法#include #include #include #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef int VRType;typedef int InfoType;typedef char VerTexType;typedef struct ArcCell VRType adj; InfoType *info; ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VerTexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum, arcnum; MGraph;typedef struct VerTexType adjvex; VRType lowcost;closedgeMAX_VERTEX_NUM;void CreateGraph(MGraph &G);void MiniSpanTree_PRIM(MGraph G, VerTexType u);int LocateVex(MGraph G, VerTexType u);int minimum(closedge close);void main( void ) int i, j; MGraph G; CreateGraph(G