算法设计与分析实验报告三篇

算法设计与分析实验报告一实验名称统计数字问题评分实验日期2014年11月15日指导教师姓名专业班级学号一.实验要求1、掌握算法的计算复杂性概念。2、掌握算法渐近复杂性的数学表述。3、掌握用C++语言描述算法的方法。4．实现具体的编程与上机实验，验证算法的时间复杂性函数。二.实验内容统计数字问题1、问题描述一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。2、编程任务给定表示书的总页码的10进制整数n(1≤n≤109)。编程计算书的全部页码中分别用到多少次数字0，1，2，…，9。三.程序算法将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。四.程序代码#include<iostream.h>ints[10];//记录0~9出现的次数inta[10];//a[i]记录n位数的规律voidsum(intn,intl,intm){if(m==1){intzero=1;for(inti=0;i<=l;i++)//去除前缀0{s[0]-=zero;zero*=10;}}if(n<10){for(inti=0;i<=n;i++){s[i]+=1;}return;}//位数为1位时,出现次数加1//位数大于1时的出现次数for(intt=1;t<=l;t++)//计算规律f(n)=n*10^(n-1){m=1;inti;for(i=1;i<t;i++)m=m*10;a[t]=t*m;}intzero=1;for(inti=0;i<l;i++){zero*=10;}//求出输入数为10的n次方intyushu=n%zero;//求出最高位以后的数intzuigao=n/zero;//求出最高位zuigaofor(i=0;i<zuigao;i++){s[i]+=zero;}//求出0~zuigao-1位的数的出现次数for(i=0;i<10;i++){s[i]+=zuigao*a[l];}//求出与余数位数相同的0~zuigao-1位中0~9出现的次数//如果余数是0,则程序可结束,不为0则补上所缺的0数,和最高位对应所缺的数if(yushu==0)//补上所缺的0数,并且最高位加1{s[zuigao]++;s[0]+=l;}else{i=0;while((zero/=10)>yushu){i++;}s[0]+=i*(yushu+1);//补回因作模操作丢失的0s[zuigao]+=(yushu+1);//补回最高位丢失的数目sum(yushu,l-i-1,m+1);//处理余位数}}voidmain(){inti,m,n,N,l;cout<<"输入数字要查询的数字:";cin>>N;cout<<'\n';n=N;for(i=0;n>=10;i++){n/=10;}//求出N的位数n-1l=i;sum(N,l,1);for(i=0;i<10;i++){cout<<"数字"<<i<<"出现了:"<<s[i]<<"次"<<'\n';}}五.程序调试中的问题调试过程，页码出现报错。六.实验结果算法设计与分析实验报告二实验名称分治法实现归并排序算法评分实验日期2014年11月26日指导教师姓名专业班级学号一.实验要求1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2.掌握分治法的一般控制流程。DanC(p,q)globaln，A[1:n];integerm,p,q;//1£p£q£nifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);//p£m<qreturnCombine(DanC(p,m),DanC(m+1,q));endifendDanC3．实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。二.实验内容1.编程实现归并排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。2.输入10组相同的数据，验证排序结果和完成排序的比较次数。3.与复杂性函数所计算的比较次数比较。4.用表格列出比较结果。5.给出文字分析。三.程序算法1.归并排序算法procedureMERGESORT(low，high)//A(low；high)是一个全程数组，它含有high-low+1≥0个待排序的元素//integerlow，high；iflow<high；thenmid←，//求这个集合的分割点//callMERGESORT(low，mid)//将一个子集合排序//callMERGESORT(mid+1，high)//将另一个子集合排序callMERGE(low，mid，high)//归并两个已排序的子集合//endifendMERGESORT归并两个已排序的集合procedureMERGE(low，mid，high)//A(low：high)是一个全程数组////辅助数组B(low；high)//integerh，i，j，k；h←low；i←low；j←mid+1；whileh≤midandj≤highdo//当两个集合都没取尽时//ifA(h)≤A(j)thenB(i)←A(h)；h←h+1elseB(i)←A(j)；j←j+1endifi←i+1repeatifh>midthenfork←jtohighdo//处理剩余的元素//B(i)←A(k)；i←i+1repeatelsefork←htomiddoB(i)←A(k)；i←i+1repeatendif将已归并的集合复制到AendMERGE2.快速排序算法QuickSort(p,q)//将数组A[1:n]中的元素A[p],A[p+1],¼,A[q]按不降次序排列，并假定A[n+1]是一个确定的、且大于A[1:n]中所有的数。//intp,q;globaln,A[1:n];ifp<qthenj=Partition(p,q+1);//划分后j成为划分元素的位置QuickSort(p,j-1);QuickSort(j+1,q);endifendQuickSortprocedurePARTITION(m，p)//退出过程时，p带着划分元素所在的下标位置。//integerm，p，i；globalA(m：p-1)v←A(m)；i←m//A(m)是划分元素//looploopi←i+1untilA(i)≥vrepeat//i由左向右移//loopp←p-1untilA(p)≤vrepeat//p由右向左移//ifi<pthencallINTERCHANGE(A(i)，A(p))//A(i)和A(p)换位//elseexitendifrepeatA(m)←A(p)；A(p)←v//划分元素在位置p//EndPARTITION四.程序代码归并排序#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<time.h>#defineM11typedefintKeyType;typedefintElemType;structrec{ KeyTypekey; ElemTypedata;};typedefrecsqlist[M];classguibing{public: guibing(sqlistb) { for(inti=0;i<M;i++) r[i]=b[i]; } voidoutput(sqlistr,intn) { for(inti=0;i<n;i++) cout<<setw(4)<<r[i].key; cout<<endl; } voidxuanze(sqlistb,intm,intn) { inti,j,k; for(i=m;i<n-1;i++) { k=i; for(j=i;j<n;j++) if(b[k].key>b[j].key)k=j; if(k!=i) { rectemp=b[k]; b[k]=b[i]; b[i]=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;i<m&&j<h;k++) { if(r[i].key<=r[j].key) { r2[k]=r[i]; i++; } else { r2[k]=r[j]; j++; } output(r2,M); } while(j<h) { r2[k]=r[j]; j++; k++; } while(i<=m) { r2[k]=r[i]; i++; k++; } output(r2,M); }private: sqlistr; }; voidmain() { cout<<"guibingfa1运行结果:\n"; sqlista,b; inti,j=0,k=M/2,n=M; srand(time(0)); for(i=0;i<M;i++) { a[i].key=rand()%80;b[i].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<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<time.h>#defineMAXI10typedefintKeyType;typedefintElemType;structrec{ KeyTypekey; ElemTypedata;};typedefrecsqlist[MAXI];classkuaisu{public: kuaisu(sqlista,intm):n(m) { for(inti=0;i<n;i++)b[i]=a[i]; } voidquicksort(ints,intt) { inti; if(s<t){ i=part(s,t); quicksort(s,i-1); quicksort(i+1,t); } elsereturn; } intpart(ints,intt) { inti,j; recp; i=s;j=t;p=b[s]; while(i<j) { while(i<j&&b[j].key>=p.key)j--; b[i]=b[j]; while(i<j&&b[i].key<=p.key)i++; b[j]=b[i]; } b[i]=p; output(); returni; } voidoutput() { for(inti=0;i<n;i++) cout<<setw(4)<<b[i].key; cout<<endl; }private: sqlistb; intn;};voidmain(){ cout<<"kuaisu1.cpp运行结果:\n"; sqlista1; inti,n=MAXI,low=0,high=9; srand(time(0)); for(i=0;i<n;i++) a1[i].key=rand()%80; kuaisupx(a1,n); cout<<"数组排序过程演示:\n"; px.quicksort(low,high); cout<<"排序后数组:\n"; px.output(); cin.get();}五.程序调试中的问题调试过程中，在排序方面有问题。六.实验结果归并排序快速排序算法设计与分析实验报告三实验名称动态规划算法实现多段图的最短路径问题评分实验日期2014年11月26日指导教师姓名专业班级学号一.实验要求1.理解最优子结构的问题有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。2.理解分段决策Bellman方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。Us初始值，uj第j段的最优值。3.一般方法找出最优解的性质，并刻画其结构特征；递归地定义最优值（写出动态规划方程）；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造一个最优解。二.实验内容1.编程实现多段图的最短路径问题的动态规划算法。2.图的数据结构采用邻接表。3.要求用文件装入5个多段图数据，编写从文件到邻接表的函数。4.验证算法的时间复杂性。三.程序算法多段图算法：ProcedureFGRAPH（E,k,n,P）//输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c（i，j）是边<i，j>的成本。P（1：k）是最小成本路径。//realCOST(n),integer(n-1),P(k),r,j,k,nCOST(n)<-0forj<-n-1to1by-1do//计算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;forj<-2tok-1do//找路径上的第j个节点//P（j）<-D(P(j-1));repeat;endFGRAPH11234567811100912973281111653552464421112*程序中的数据以此图为标准7四.程序代码#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<iostream.h>#defineMAX100#definen12/*顶点数*/#definek5/*段数*/intc[n][n];voidinit(intcost[])//初始化图{ inti,j; for(i=0;i<13;i++) { for(j=0;j<13;j++) { c[i][j]=MAX; } } c[1][2]=9; c[1][3]=7; c[1][4]=3; c[1][5]=2; c[2][6]=4; c[2][7]=2; c[2][8]=1; c[3][6]=2; c[3][7]=7; c[4][8]=11; c[5][7]=11; c[5][8]=8; c[6][9]=6; c[6][10]=5; c[7][9]=4; c[7][10]=3; c[8][10]=5; c[8][11]=6; c[9][12]=4; c[10][12]=2;c[11][12]=5;}voidfgraph(intcost[],intpath[],intd[])//使用向前递推算法求多段图的最短路径{ intr,j,temp,min; for(j=0;j<=n;j++) cost[j]=0; for(j=n-1;j>=1;j--) { temp=0; min=c[j][temp]+cost[temp];//初始化最小值 for(r=0;r<=n;r++) {if(c[j][r]!=MAX) {if((c[j][r]+cost[r])<min)//找到最小的r { min=c[j][r]+cost[r]; temp=r; } } } cost[j]=c[j][temp]+cost[temp]; d[j]=temp; } path[1]=1; path[k]=n; for(j=2;j<k;j++) path[j]=d[path[j-1]];}voidbgraph(intbcost[],intpath1[],intd[])//使用向后递推算法求多段图的最短路径{ intr,j,temp,min; for(j=0;j<=n;j++) bcost[j]=0; for(j=2;j<=n;j++) { temp=12; min=c[temp][j]+bcost[temp];//初始化最小值 for(r=0;r<=n;r++) {if(c[r][j]!=MAX) {if((c[r][j]+bcost[r])<min)//找到最小的r { min=c[r][j]+bcost[r]; temp=r; } } } bcost[j]=c[temp][j]+bcost[temp]; d[j]=temp; } path1[1]=1; path1[k]=n; for(inti=4;i>=2;i--) { path1[i]=d[path1[i+1]]; }}voidmain(){intcur=-1; intcost[13],d[12],bcost[13]; intpath[k];intpath1[k]; cout<<"\t\t\t动态规划解多段图问题"<<endl; cout<<"\n\n";init(cost);fgraph(cost,path,d);cout<<"输出使用向前递推算法后的最短路径:\n\n"; for(inti=1;i<=5;i++) { cout<<path[i]<<""; } cout<<"\n"; cout<<endl<<"最短路径为长度:"<<cost[1]<<endl; cout<<"\n";cout<<"\n输出使用向后递推算法后的最短路径:\n\n"; bgraph(bcost,path1,d); for(i=1;i<=5;i++) { cout<<path1[i]<<""; } cout<<"\n"; cout<<endl<<"最短路径为长度:"<<bcost[12]<<endl; cout<<"\n";}五.程序调试中的问题动态规划的思想很容易理解，但当用程序代码实现起来的时候又觉得有点困难，经过我反复的调试操作，发现对于邻接表的程序表达不是很好。六.实验结果算法设计与分析实验报告四实验名称贪心算法实现背包问题评分实验日期2014年11月26日指导教师姓名专业班级学号一.实验要求1.优化问题有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。2.贪心法求优化问题算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedycriterion）。3.一般方法1）根据题意，选取一种量度标准。2）按这种量度标准对这n个输入排序3）依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。procedureGREEDY(A，n)/*贪心法一般控制流程*///A(1：n)包含n个输入//solutions←φ//将解向量solution初始化为空／fori←1tondox←SELECT(A)ifFEASIBLE(solution，x)thensolutions←UNION(solution，x)endifrepeatreturn(solution)endGREEDY4.实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。二.实验内容1.编程实现背包问题贪心算法。通过具体算法理解如何通过局部最优实现全局最优，并验证算法的时间复杂性。2.输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句。3.将统计数与复杂性函数所计