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

算法设计与分析实验报告一实验名称统计数字问题评分实验日期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次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。四.程序代码#includeiostream.hints[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(n10){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;it;i++)m=m*10;a[t]=t*m;}intzero=1;for(inti=0;il;i++){zero*=10;}//求出输入数为10的n次方intyushu=n%zero;//求出最高位以后的数intzuigao=n/zero;//求出最高位zuigaofor(i=0;izuigao;i++){s[i]+=zero;}//求出0~zuigao-1位的数的出现次数for(i=0;i10;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输入数字要查询的数字:;cinN;cout'\n';n=N;for(i=0;n=10;i++){n/=10;}//求出N的位数n-1l=i;sum(N,l,1);for(i=0;i10;i++){cout数字i出现了:s[i]次'\n';}}五.程序调试中的问题调试过程，页码出现报错。六.实验结果算法设计与分析实验报告二实验名称分治法实现归并排序算法评分实验日期2014年11月26日指导教师姓名专业班级学号一.实验要求1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1k≤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mqreturnCombine(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；iflowhigh；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+1repeatifhmidthenfork←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];ifpqthenj=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由右向左移//ifipthencallINTERCHANGE(A(i)，A(p))//A(i)和A(p)换位//elseexitendifrepeatA(m)←A(p)；A(p)←v//划分元素在位置p//EndPARTITION四.程序代码1.归并排序#includeiostream.h#includeiomanip.h#includestdlib.h#includetime.h#defineM11typedefintKeyType;typedefintElemType;structrec{KeyTypekey;ElemTypedata;};typedefrecsqlist[M];classguibing{public:guibing(sqlistb){for(inti=0;iM;i++)r[i]=b[i];}voidoutput(sqlistr,intn){for(inti=0;in;i++)coutsetw(4)r[i].key;coutendl;}voidxuanze(sqlistb,intm,intn){inti,j,k;for(i=m;in-1;i++){k=i;for(j=i;jn;j++)if(b[k].keyb[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;im&&jh;k++){if(r[i].key=r[j].key){r2[k]=r[i];i++;}else{r2[k]=r[j];j++;}output(r2,M);}while(jh){r2[k]=r[j];j++;k++;}while(i=m){r2[k]=r[i];i++;k++;}output(r2,M);}private:sqlistr;};voidmain(){coutguibingfa1运行结果:\n;sqlista,b;inti,j=0,k=M/2,n=M;srand(time(0));for(i=0;iM;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();}2.快速排序#includeiostream.h#includeiomanip.h#includestdlib.h#includetime.h#defineMAXI10typedefintKeyType;typedefintElemType;structrec{KeyTypekey;ElemTypedata;};typedefrecsqlist[MAXI];classkuaisu{public:kuaisu(sqlista,intm):n(m){for(inti=0;in;i++)b[i]=a[i];}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=b[s];while(ij){while(ij&&b[j].key=p.key)j--;b[i]=b[j];while(ij&&b[i].key=p.key)i++;b[j]=b[i];}b[i]=p;output();returni;}voidoutput(){for(inti=0;in;i++)coutsetw(4)b[i].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++)a1[i].key=rand()%80;kuaisupx(a1,n);cout数组排序过程演示:\n;px.quicksort(low,high);cout排序后数组:\n;px.output();cin.get();}五.程序调试中的问题调试过程中，在排序方面有问题。六.实验结果1.归并排序2.快速排序算法设计与分析实验报告三实验名称动态规划算法实现多段图的最短路径问题评分实验日期2014年11月26日指导教师姓名专业班级学号一.实验要求