《算法设计与分析实验报告三篇.doc》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告三篇.doc（17页珍藏版）》请在三一办公上搜索。
1、精选优质文档-倾情为你奉上算法设计与分析实验报告一实验名称 统计数字问题 评分 实验日期 2014 年 11 月 15 日 指导教师 姓名 专业班级 学号 一.实验要求1、掌握算法的计算复杂性概念。2、掌握算法渐近复杂性的数学表述。3、掌握用C+语言描述算法的方法。4实现具体的编程与上机实验，验证算法的时间复杂性函数。二.实验内容 统计数字问题1、问题描述一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0
2、，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; f
3、or(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; /求出最
4、高位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; 五.程序调试中的问题调试过程，页码出现
5、报错。六.实验结果算法设计与分析实验报告二实验名称 分治法实现归并排序算法 评分 实验日期 2014 年 11 月 26 日 指导教师 姓名 专业班级 学号 一.实验要求1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2.掌握分治法的一般控制流程。DanC(p,q) global n，A1:n; integer m,p,q; / 1pqn if Small(p,q) then ret
6、urn 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)是一个全程数
7、组，它含有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
8、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 INTERC
9、HANGE(A(i)，A(p) /A(i)和A(p)换位/ else exit endif repeat A(m) A(p)；A(p) v /划分元素在位置p/ End PARTITION四.程序代码1. 归并排序#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;i
10、M;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(
11、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);
12、cout数组排序过程演示:n;gx.merge(j,k,n,b);cout排序后数组:n;gx.output(b,M);cin.get();2. 快速排序#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; vo
13、id 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:sqlis
14、t 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. 快速排序算法设计与分析实验报告三实验名称 动态规划算法实现多段图的最短路径问题 评分 实验日
15、期 2014 年 11 月 26 日 指导教师 姓名 专业班级 学号 一.实验要求1. 理解最优子结构的问题有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。2.理解分段决策Bellman方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。Us 初始值，uj第j段的最优值。3.一般方法1） 找出最优解的性
16、质，并刻画其结构特征；2） 递归地定义最优值（写出动态规划方程）；3） 以自底向上的方式计算出最优值；4） 根据计算最优值时得到的信息，构造一个最优解。二.实验内容1.编程实现多段图的最短路径问题的动态规划算法。2.图的数据结构采用邻接表。3.要求用文件装入5个多段图数据，编写从文件到邻接表的函数。4.验证算法的时间复杂性。三.程序算法多段图算法：Procedure FGRAPH（E,k,n,P）/输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c（i，j）是边的成本。P（1：k）是最小成本路径。/real COST(n),integer(n-1),P(k),r,j,k,nCOST
17、(n)-0for j-n-1 to 1 by -1 do /计算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 j-2 to k-1 do / 找路径上的第j个节点/ P（j）-D(P(j-1);repeat;end FGRAPH1234567811100912973281111653552464421112* 程序中的数据以此图为标准7四.程序代码#include #include #include #includ
18、e #define MAX 100 #define n 12 /*顶点数*/#define k 5 /*段数*/int cnn;void init(int cost) /初始化图int i,j;for(i=0;i13;i+)for(j=0;j13;j+)cij=MAX;c12=9;c13=7;c14=3;c15=2;c26=4;c27=2;c28=1;c36=2;c37=7;c48=11;c57=11;c58=8;c69=6;c610=5;c79=4;c710=3;c810=5;c811=6;c912=4;c1012=2;c1112=5;void fgraph(int cost,int pat
19、h,int d) /使用向前递推算法求多段图的最短路径int r,j,temp,min;for(j=0;j=1;j-)temp=0;min=cjtemp+costtemp; /初始化最小值for(r=0;r=n;r+) if(cjr!=MAX) if(cjr+costr)min) /找到最小的rmin=cjr+costr;temp=r;costj=cjtemp+costtemp;dj=temp;path1=1;pathk=n;for(j=2;jk;j+)pathj=dpathj-1;void bgraph(int bcost,int path1,int d)/使用向后递推算法求多段图的最短路径
20、int r,j,temp,min;for(j=0;j=n;j+)bcostj=0;for(j=2;j=n;j+)temp=12;min=ctempj+bcosttemp; /初始化最小值for(r=0;r=n;r+) if(crj!=MAX) if(crj+bcostr)=2;i-)path1i=dpath1i+1;void main() int cur=-1;int cost13,d12,bcost13;int pathk; int path1k;coutttt动态规划解多段图问题endl;coutnn; init(cost); fgraph(cost,path,d); cout输出使用向前
21、递推算法后的最短路径:nn;for(int i=1;i=5;i+)coutpathi ; coutn;coutendl最短路径为长度:cost1endl;coutn; coutn输出使用向后递推算法后的最短路径:nn;bgraph(bcost,path1,d);for(i=1;i=5;i+)coutpath1i ; coutn;coutendl最短路径为长度:bcost12endl;coutn;五.程序调试中的问题动态规划的思想很容易理解，但当用程序代码实现起来的时候又觉得有点困难，经过我反复的调试操作，发现对于邻接表的程序表达不是很好。六.实验结果算法设计与分析实验报告四实验名称 贪心算法实
22、现背包问题 评分 实验日期 2014 年 11 月 26 日 指导教师 姓名 专业班级 学号 一.实验要求1. 优化问题 有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。2.贪心法求优化问题算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedy criterion）。3.一般方法1）根据题意，选取一种量度标准。2）按这种量
23、度标准对这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. 实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。二.实
24、验内容1. 编程实现背包问题贪心算法。通过具体算法理解如何通过局部最优实现全局最优，并验证算法的时间复杂性。2.输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句。3.将统计数与复杂性函数所计算的比较次数比较，用表格列出比较结果，给出文字分析。三.程序算法 计算每种物品单位重量的价值，将可能多的单位重量价值最高的物品装入背包，如果单位重量价值最高的物品全部装入背包后，背包的总重量小于C，则选择单位重量次高的物品并尽可能多的装入背包，依次进行下去，直到背包装满为止。四.程序代码#includestdio.hvoid main(void)int C=6;/背包容量6int
25、n=5;/5个物品int w=3,2,1,4,5;/物品重量int v=25,20,15,40,50;/物品价值int x=0,0,0,0,0;/单位价值初始化int q5;int m,i,j,p,vx,wx,k,ii;int V=0;/总价值初始化/计算单位价值printf(单位价值为：n);for(m=0;m5;m+)qm=m;xm=vm/wm;printf(x%d=%dt,m,xm);/冒泡排序for(i=0;i4;i+)for(j=0;j4-i;j+)if(xjxj+1)/交换单位价值p=xj;xj=xj+1;xj+1=p;/交换价值对应位置vx=vj;vj=vj+1;vj+1=vx;
26、 /交换重量对应位置wx=wj;wj=wj+1;wj+1=wx;/交换商品编号m=qj;qj=qj+1;qj+1=m;printf(n单位价值降序为：n);for(i=0;i5;i+)printf(x%d=%dt,i,xi);/装入背包for(i=0;in&wiC;i+)if(wi=C) V+=vi;C=C-wi;k=i;if(C!=0)V+=vi*C/wi;C=0;for(ii=0;ii=k;ii+)printf(n放入第%d个物品：n物品的重量为：%dn物品的价值为：%dn背包剩余容量为：%dn,qii+1,wii,vii,C);printf(n总价值为：%dt,V);五. 程序调试中的问题 在调试时，装入背包过程如何保证装入不完整物品，即背包剩余容量不能满足完全放入下一个物品。六.实验结果专心-专注-专业
